Blog infoarena

Combinatorics shortlist

Cosmin
Cosmin Negruseri
10 decembrie 2012

Short lists are often used in math camps to cover some subject by going through a bunch of problems. I've thought of doing the same for programming contests. The first list is related to combinatorics.

Discuss the solutions in the comment section.

  1. (10th grade math course) How many different strings of length 9 are there which contain 3 'a's, 3 'b's and 3 'c's.
  2. How many ways are there to climb a n level staircase if at each step you can climb one or two levels.
  3. (olimpiada online 2001) Given n points on a circle. Draw all possible n(n-1)/2 chords. What’s the maximum number of triangles one can see. Example: With n = 4 there are 8 triangles (4 with 3 of the 4 circle points and 4 with 2 circle points and 1 the intersection of the diagonal).
  4. (4, agora scholarships 2001, infoarena) What is the maximum number of regions the plane can be split into by n lines. (Same problem for n circles, n planes, n spheres) Example: For n = 3 we can get 7 regions.
  5. (1) What is the maximum product for collection of natural numbers that sum up to n.
  6. (1, romanian national olympiad, 10th grade, 2000) How many ways can you tile a 3xn rectangle with dominoes.
  7. (romanian IOI selection, 1999)
    for i1 = 1,n
    _for i2 = i1,n
    __for i3 = i2,n
    ____…
    _____for ik = ik - 1,n
    ______print ‘*’
    How many stars will be printed for a given n and k.
  8. (5, acm.sgu.ru) Count the number of ways k rooks can be placed on a nxn chessboard so that they don’t attack each other.
  9. (1, romanian county olympiad, 11th grade 2000, acm.sgu.ru) Count the number of length n permutations with no fixed points. A fixed point in a permutation p is p(i) = i
  10. (1, county level olympiad, 1994) Count the number of correct bracket sequences of length 2n.
  11. (10th grade math course) Count the number of paths on a grid going from 1,1 to n, m. At each step you can either increase your x coordinate or increase your y coordinate.
  12. Given a permutation of numbers 1 to n, what's the minimum number of swaps one can use to get to the identity permutation.
  13. Count the number of size n permutations such that p^2(i) = i for all i in {1..n}.
  14. (1, infoarena) Given a permutation p what's the minimum k so that p^k(i) = i for all i in {1..n}.
  15. (romanian IOI selection 99, topcoder 2004, infoarena) Find a permutation p of n elements which maximizes k so that p^k(i) = i for all i in {1..n}.
  16. (1) 6 people are at a party. Each two persons can be either friends or enemies. Prove that there is at least a group of three mutual friends or a group of three mutual enemies.
  17. (acm.sgu.ru) Count the number of circular black/white necklaces of length n. (babb is the same with bbab because the first necklace can be rotated to align with the second one)

Some math books useful for programming competition enthusiasts:
1 Ioan Tomescu "Probleme de combinatorica si teoria grafurilor"
Every year during my highschool there was at least one problem in the national olympiad or in the IOI team selection tests from this book.
2 Ioan Cuculescu "Olimpiadele Internationale de Matematica ale Elevilor"
3 E. A. Morozova, I. S. Petracov, V. A. Skvortov "Olimpiade internationale de matematica"
4 "Probleme de matematica traduse din revista sovietica KVANT"
5 A. M. Iaglom, I. M. Iaglom "Probleme neelementare tratate elementar"
6 Mathematics for computer science

 Comentarii (21)

Categorii:

Algoritmiada 2013

ada_s
Ada-Mihaela Solcan
25 noiembrie 2012

Infoarena revine cu cea de-a cincea ediţie a concursului Algoritmiada . Algoritmiada este un concurs unic în România care reuneşte pasionaţi de informatică de toate vârstele, începând cu elevi de gimnaziu şi până la persoane care au terminat de mulţi ani facultatea. Participanţii sunt împărţiti în patru grupe : clasele 5-9, clasa a 10-a, clasele 11-12 si Open. Concursul se desfăşoară anual sub forma a 3-4 runde de calificare online, iar primii clasaţi sunt la invitaţi să participe la finala onsite. În paralel cu finala onsite se desfăşoară şi o variantă online a finalei pentru cei care nu au reuşit să se califice.

Algoritmiada este seria de concursuri infoarena care a impresionat nu doar prin calitatea problemelor, dar şi prin organizarea ireproşabilă a rundelor. Acest fapt se datorează unei echipe tehnice şi ştiinţifice extrem de valoroase din punct de vedere academic. Şi în acest an coordonatorii ştiinţifici ai fiecărei runde vor fi foşti olimpici internaţionali sau membrii ai lotului naţional de informatică. Finala Algoritmiada este considerată cel mai important concurs naţional din România, iar acest statut i-a adus colaborări cu diverşi sponsori.

Ediţiile din anii trecuţi

Prima ediţie a concursului Algoritmiada s-a desfăşurat în 2009. La concurs puteau participa atât elevi, cât şi studenţi, fiind primul concurs naţional de acest tip. Au existat 3 runde de calificare, iar cei mai buni concurenţi au fost invitaţi la finala ce s-a desfăşurat la Braşov.

La ediţia din 2010 concurenţii au avut 4 runde de calificare, iar cei cu cele mai bune rezultate au participat la finala de la Iasi. Concursul a fost organizat în parteneriat cu Amazon România şi Adobe România.

Începând cu anul 2011, la cea de a treia ediţie, categoria "studenţi" a fost înlocuită cu "open", astfel la concurs putând participa oricine, indiferent de vârstă. Runda finală a acestei ediţii s-a desfăşurat în Timişoara. Concursul a fost organizat în parteneriat cu Google şi Adobe România.

Anul trecut, Algoritmiada a fost realizată în parteneriat cu Adobe România, Reea, Ixia, uberVU şi MB Telecom. Câştigătorii rundei finale de la Târgu Mureş au fost : Rares Buhai (clasele 5-9), Daniel Constantin Anghel (clasa a 10-a), Gavrila Vlad (clasele 11-12) şi Mugurel-Ionut Andreica (open).

Prima runda Algoritmiada 2013

Prima rundă a ediţiei de anul acesta a concursului Algoritmiada va avea loc pe 8 decembrie 2012. Concursul o să urmeze formatul ediţiei de anul trecut, având patru grupe valorice: clasele 5-9, clasa a 10-a, clasele 11-12 şi open. Participanţii vor avea la dispoziţie 4-5 ore pentru a rezolva 3-4 probleme de natură algoritmică. Aceasta este una din rundele cu rol de calificare pentru finală, aşa că participă şi dovedeşte-ţi talentul şi cunoştiinţele!

 Comentarii (4)

Categorii:

Infoarena și-a ales noua conducere

ada_s
Ada-Mihaela Solcan
13 noiembrie 2012

Infoarena şi-a ales noua conducere. Este vorba despre :

Andrei Grigorean a intrat pentru prima oară pe infoarena la sfârşitul clasei a X-a, după ONI 2005, iar din clasa a XI-a a început să lucreze serios pe site. Din 2007, după ce a termniat liceul, a intrat în echipă. Ca membru al echipei, a propus peste 50 de probleme, a făcut parte din comisiile ştiinţifice de la aproape toate concursurile infoarena şi a lucrat puţin şi la development. A fost preşedinte al primei ediţii a concursului Algoritmiada, în 2009, şi al ediţiei din 2012, iar împreună cu Mihai Duşmanu, a iniţiat concursul Infoarena Monthly. A mai ocupat anterior funcţia de preşedinte infoarena în 2010/2011.

Ca preşedinte, munca lui va fi mai mult una de coordonare şi îi va ajuta pe cei trei vicepreşedinţi să-şi atingă obiectivele pe care şi le-au propus. Îşi doreşte în continuare creşterea echipei infoarena şi apropierea membrilor echipei de comunitate. Va încerca să menţină un contact mai strâns cu sponsorii şi să găsescă noi persoane care vor să se implice pe partea de development. De asemenea, va monitoriza atent activitatea de pe site şi va încerca să cunoască cât mai mulţi utilizatori noi.

Serban Andrei Stan consideră infoarena principalul site de pe care s-a pregătit pentru olimpiade şi concursuri pe parcursul liceului. Datorită acestui fapt, a rezolvat aproape jumatate din problemele din arhivă şi astfel a ajuns extrem de familiar cu site-ul. A organizat, în calitate de membru al comunităţii, concursul .com 2009, alături de Cezar Mocan, Radu Zernoveanu şi alţi utilizatori. Anul trecut, când a fost invitat în cadrul echipei a acceptat cu mult entuziasm. În 2012 a ajutat la organizarea rundelor de Algoritmiada şi Infoarena Cup.

Obiectivele sale pentru următorul an, ca vicepreşedinte responsabil pentru Algoritmiada 2013, sunt păstrarea bunei organizări a concursului, asigurarea unor seturi de probleme care să surprindă nu prin dimensiunea sursei, ci plin originalitatea soluţiei, şi organizarea unei finale mai reuşite decât în anii precedenţi. Pentru fiecare rundă coordonatorii ştiinţifici vor fi foşti olimpici internaţionali ori membri ai lotului naţional de informatică. În plus, finala Algoritmiada este cel mai important concurs naţional din România. Acest statut i-a adus pe parcursului timpului colaborări cu diverşi sponsori, şi sperăm că anul acesta va fi unul rodnic în acest sens.

Îşi propune ca şi Infoarena Cup, care este doar la a doua ediţie, să îşi caştige statutul de "concurs international". Anul trecut, pe lânga concurenţii români a participat şi echipa naţională a Elveţiei. Feedback-ul lor a fost pozitiv, şi prin prisma acestui fapt s-a hotarat ca anul acesta sa se organizeze o ediţie cu mai mulţi participanţi internaţionali. Doreşte ca demersurile de intrare în contact cu reprezentanţii echipelor naţionale de liceu din Europa să fie încununate de succes. În plus, un alt scop îl constituie găsirea unui set de probleme potrivit pentru un concurs de un asemena calibru.

Adrian Budau a intrat anul trecut în echipa infoarena şi a devenit în scurt timp principalul om pe partea de development. Împreună cu Bogdan Tătăroiu, se ocupă de asigurarea unei bune funcţionări a site-ului. Ca membru s-a implicat şi în alte activităţi, cum ar fi: comisiile de la concursurile Algoritmiada şi Infoarena Monthly, dar şi în discuţii cu anumiţi sponsori. De asemenea, în cadrul finalei Algorimiada de anul trecut, s-a ocupat de pregătirea calculatoarelor concurenţilor.

Obiectivul său principal pentru următorul an, ca vicepreşedinte responsabil cu partea de development, este să sa găsească o echipă împreună cu care să lucreze la infoarena 3. Aceasta ar presupune un site multilingv, un design nou, un forum îmbunătăţit, existenţa unor grupuri pentru utilizatori, dar şi a concursurilor create de către useri. De asemenea, îşi propune sa ajute şi să supervizeze pe cei care doresc să se implice la partea de development din cadrul infoarena pe hackers.infoarena.ro.

Dumitran Adrian Marius este implicat de mai mulţi ani în Infoarena, mai ales pentru a facilita comunicarea dintre echipă şi Facultatea de Matematică şi Informatică, atât cu studenţii şi asociaţia studenţilor, cât şi cu profesorii şi conducerea facultăţii. De asemenea, s-a implicat şi în organizare concursurilor Algoritmiada şi Infoarena Cup şi în întreţirea relaţiilor cu sponsorii.

Obiectivul principal al său pentru următorul an este aducerea unor companii puternice alături de infoarena ca parteneri stabili şi nu doar pentru anumite proiecte. Este de părere că ideală ar fi atragerea unei fundaţii importante alături de echipă. Un alt obiectiv îl constituie strângerea legăturilor cu ROSEdu şi Politehnica, unde în acest moment nu mai există membri activi în cadrul infoarena. Importantă este şi o mediatizare mai puternică a brandului infoarena, iar o bună ocazie o constituie organizarea Infoarena Cup la Bucureşti. Pentru a işi atinge aceste obiective doreşte extinderea echipei infoarena şi pe partea de PR.

 Comentarii (1)

Categorii:

Haideti sa imbunatatim Infoarena impreuna!

marius135
Dumitran Adrian Marius
05 noiembrie 2012

Infoarena merge inainte, si chiar daca infoarena 3 este departe, vom incerca sa adaugam noi functionalitati in urmatoarea perioada. Scriem acest mic post pentru ca vrem sa stim ce doriti voi, utilizatorii, sa adaugam la site. Vom incerca sa analizam toate ideile voastre si sa alegem o parte dintre ele pentru a le implementa in urmatoarea perioada. Daca ati avut momente in care v-ati gandit ca siteul are nevoie de x sau de y, acum e momentul vostru. Asteptam cu mare drag ideile voastre.

 Comentarii (73)

Categorii:

Rolling hash, Rabin Karp, palindromes, rsync and others

Cosmin
Cosmin Negruseri
30 octombrie 2012

Rolling hash is a neat idea found in the Rabin-Karp string matching algorithm which is easy to grasp and useful in quite a few different contexts.

As before, the most interesting part of the article is the problem section. Discuss them in the comment section, but first let's go through a few applications.

The Rabin-Karp algorithm

Given a string P of length n and a string S of length m find out all the occurrences of P within S

The algorithm works by building a fingerprint for each substring of S of length n. It checks if any of them match the fingerprint of P. Implementing this directly leads to a O(n*m) solution which isn't faster than the naive matching algorithm (in fact it may be slower).

The insight is that you can efficiently compute the hash value of a substring using the hash value of previous substring if you use the right hash function. A polynomial with the string characters as coefficients works well. Let H(c)=c[0]a^{n-1} + c[1]a^{n-2}+...+c[n-1] be the hash function for the string c.
All the operations are done modulo a prime number so that we don’t have to deal with large integers.

Let’s see what happens when we go from H(S[i..i+n-1]) to H(S[i+1..i+n]):


H(S[i+1..i+n])= S[i+1]a^{n-1}+S[i+2]a^{n-2}+.. + S[i+n]

Adding and substracting S[i]a^n we get


a(S[i]a^{n-1}+S[i+1]a^{n-2}+ S[i+2]a^{n-3}+ .. + S[i+n -1])+S[i+n]-S[i]a^{n} =

aH(S[i..i+n-1])-S[i]a^{n}+S[i+n]

Deleting a character and appending another one corresponds to adding a number and subtracting a number in our hashing algorithm. The complexity of the algorithm is O(n).

If S and P are strings of digits and a is 10, our problem maps to finding numbers in a string of digits.
Let's go through an example.

Let P = 53424, S = 3249753424234837 and a = 10
3249753424234837
32497
 24975 = 10 * 32497 - 3 * 10000 + 5  
  49753 = 10 * 24975 - 2 * 10000 + 3
   97534 = 10 * 49753 - 4 * 10000 + 4 
     ...
     53424 // match
      ...

Here's some code:

an = 1
  rolling_hash = 0
  for i in range(0, n):
    rolling_hash = (rolling_hash * a + S[i]) % MOD
    an = (an * a) % MOD
  if rolling_hash == hash_p:
    print "match"
  for i in range(1, m - n + 1):
    rolling_hash = (rolling_hash * a + S[i + n - 1] - an * S[i - 1]) % MOD
    if rolling_hash == hash_p:
        print "match"

Longest common substring

Given two strings A and B, compute their longest common substring.

Let's solve a simpler problem: Given two strings A and B, and a number X find if they have a common sequence of length X. We use the rolling hash technique to find the hash codes for all X length substrings of A and B. Then we check if there is any common hash code between the two sets, this means A and B share a sequence of length X. We then use binary search to find the largest X.
The complexity of this algorithm is O(n log n).

rsync

The linux utility is used to keep two copies of the same file in sync by copying around deltas. Instead of replicating the whole changed file, rsync segments the file into fixed size chunks, computes a rolling hash for each chunk. On the client side computes rolling hashes for all chunks of the target file including overlapping ones. Then it checks which chunks are already there, which chunks need to be deleted and which chunks need to be copied over. This improves the transfer speed as you only copy over deltas and some chunk fingerprints. Here's a better description from wikipedia.

Largest palindrome

Given a string of length n, find out its largest palindromic substring.

The naive solution is O(n3). For every possible substring it tests in linear time if it's a palindrome.

A smarter solution tries every position in the original string as the center of a palindrome and extends to the left and to the right as long as the corresponding characters match. This solution takes O(n2) time.

There's a O(n log n) solution that involves rolling hash. Given X we can test if there is any substring S' of S of length 2X such that H(S') == H(reverse(S')). The identity means that S contains a palindromic sequence of length at least 2X. What is left is to find out the maximum such X. We can use binary search to do that efficiently. The overall complexity is O(n log n).

Substrings of variable length

The polynomial function can be used to compute hashes for substrings of varying length

Let’s choose H(S[i..j]) = S[i]+S[i+1]a+S[i+2]a{2}+...+S[j]a^{j-i} Then we compute the array h which contains cummulative hashes: h[k]=S[0]+S[1]a+S[2]a^{2}+...+S[k]a^{k}. It’s easy to see that H(S[i..j])=(h[j]-h[i-1])/a^i

After spending O(n) time on preprocessing h, we have an efficient way to compute the hash code for any substring of S.

The division operation modulo a prime needs some number theory insight. You can do it using Fermat's little theorem or using the Extended Euclidean Algorithm. If you need to process a lot of sub strings it's useful to pre process all the values for a^{-i} \bmod{p}.

Caveats

Hashing collisions are a problem. One way to deal with them is to check for a match when two fingerprints are equal, but this makes the solution inefficient if there are lots of matches. Another way is to use more hashing functions to decrease the collision probability.

Alternatives

Suffix trees or suffix arrays are very good tools to tackle string matching problems. I prefer hashing as the code is usually simpler.

Additional problems

  1. Given a string of length n, count the number of palindromic substring of S. Solve better than O(n2).
  2. Given a string of length n, find the longest substring that is repeated at least k times. Solve in O(n log n)
  3. Given a bitmap, find out the largest square that’s repeated in the bitmap.
  4. Given a string S figure out if the string is periodic. (there is a p such that for any i we have that s[i] == s[i + p]) For example abcabcab is periodic with p = 3. O(n log n)
  5. Given two equal length strings, figure out if one is a rotation of the other. O(n)
  6. Given two polygons find out if they are similar polygons. O(n)
  7. Given a string, find it's longest periodic prefix. O(n log n) For aaabaaabcde the answer is aaabaaab
  8. Given a tree T with character labeled nodes and a given string P count how many downward paths match P. O(n)

 Comentarii (9)

Categorii:

Count (distinct) problem

Cosmin
Cosmin Negruseri
24 octombrie 2012

Here's a neat problem from Alexandru Andoni:

You're given a 1GB file containing 64 bit integers.
Come up with an algorithm which estimates the number of distinct integers in the file. You're allowed to use 1024 bytes of memory and you can read the file only once.
How good is your estimation?

 Comentarii (8)

Categorii:

Infoarena lovește din nou!

wefgef
Andrei Grigorean
13 octombrie 2012

Sîmbătă, 13 octombrie 2012, a avut loc faza regională a concursului ACM ICPC, regiunea sud-est europeană. Au participat 78 de echipe de la 47 de universităţi, provenind din 8 ţări diferite. Experienţa ultimilor ani ne învaţă că regiunea noastră este una dintre cele mai puternice din lume, concurenţa fiind foarte mare, în special din partea echipelor din Ucraina. La fel ca la ultima ediţie, concursul s-a desfăşurat în două locuri diferite: la Universitatea Politehnică din Bucureşti şi în Vinnytsia, Ucraina. Pentru evaluare s-a folosit sistemul Ejudge, iar concurenţii trebuiau să submiteze sursele online.

Consideraţi de mulţi principalii candidaţi români pentru calificare, echipa Universităţii din Bucureşti, BigDawgs, a reuşit un rezultat remarcabil. Toţi cei trei membri ai acestei echipe fac parte şi din echipa infoarena:

Cu 8 din 10 probleme rezolvate şi cu o penalizare de 1003 minute, ei au reuşit să se claseze în final pe treapta a doua a podimiului, poziţie care le garantează un loc la faza finală a celui mai de tradiţie concurs de programare din lume. Merită menţionat că au fost detronaţi de pe prima poziţie cu doar 4 minute înainte de finalul probei, altfel am fi asistat la o victorie românească după foarte mulţi ani.

Celelalte echipe româneşti s-au descurcat şi ele foarte bine, Universitatea din Bucureşti ocupînd de asemenea locurile 9 şi 11, prin echipele Smecheria şi Aproape Oltenia (ambele cu 7 probleme rezolvate). Şi Politehnica s-a descurcat onorabil, Angry Pink Bunnies terminînd pe 18, iar Retired But Dangerous pe 19 (ambele cu 6 probleme rezolvate).

Îi felicităm pe toţi şi le ţinem pumnii celor trei la faza finală care va avea loc în iulie 2013, în Sankt Petersburg!

 Comentarii (9)

Categorii:

Editorial Runda 8

klamathix
Mihai Calancea
14 septembrie 2012

Inaugurăm prin acest blogpost o serie de editoriale care, sperăm noi, îşi vor face apariţia după fiecare rundă a concursului Infoarena Monthly. Scopul lor este de a augmenta latura educativă a concursului prin explicarea detaliată a soluţiilor problemelor propuse. Sperăm de-asemenea ca secţiunea de comentarii să devină o platformă potrivită pentru discuţii şi feedback despre subiecte şi despre formatul concursului în sine. Suntem conştienţi că o asemenea iniţiativă apare destul de târziu, concursul fiind deja în runda cu numărul 8, însă am considerat că o atitudine de tip "Las' ca începem de luni, asa se face treaba" n-ar fi fost foarte inspirata. Avand in vedere ca urmatorul "Luni" al Monthly-ului este practic in 2013. Acestea fiind zise, let s get to work.

Runda 8 a avut 91 de concurenţi înscrişi şi 79 de concurenţi care au submitat cel puţin o sursă. Echipa a subestimat însă dificultatea setului ales, astfel doar 2 concurenţi au terminat concursul având 3 probleme rezolvate, iar una dintre probleme nu a fost rezolvată corect de nimeni. Dacă ar fi să luăm ca referinţă concursurile de tip ACM, se spune că un set de probleme este bun dacă fiecare problemă este rezolvată de către cineva, dar nimeni nu rezolvă toate problemele. We're not quite there yet, dar ne străduim :).

Switch

O primă idee care poate rezolva această problemă este cea de a descrie un graf cu 16 noduri (fiecare matrice posibila) şi 4 arce care ies din fiecare nod (transformarile posibile). Astfel, se poate face un DFS pe acest graf pentru a se afla daca exista conexitate intre matricele date in input. Dacă problema ar fi cerut şi numărul minim de operaţii necesare, soluţia ar fi fost dată de o parcurgere în lăţime.

Însă această problemă are o soluţie mult mai scurtă, pe care mulţi concurenţi au intuit-o şi au implementat-o. Graful are de fapt doar două componente conexe. În prima se află matricele cu număr par de 1, iar în cealaltă cele cu număr impar. Pentru a demonstra acest lucru, observaţi că o operaţie de negare nu schimbă niciodată paritatea numărului de 1 (De ce?). Faptul că din orice matrice pară se poate ajunge in orice altă matrice pară este destul de evident, în special fiindcă multe dintre configuraţii sunt doar oglindiri/rotiri ale celorlalte.

Prima soluţie este mai flexibilă, iar corectitudinea ei nu depinde niciodată de particularităţile transformărilor sau ale matricelor, putând fi folosita şi pentru matrice de N x N. Ea are complexitate O(2 ^ N * M), unde M este numărul de transformări posibile. Cea de a doua soluţie are însă complexitate O(1) şi se scrie in 2 rânduri.

Cifre3

Această problemă avea în primă fază alt enunţ, iar cele 2 surse oficiale au la baza ideea problemei iniţiale. Astfel, marea majoritate a concurenţilor a ajuns să aiba o soluţie mult mai scurtă şi mai eficientă. Soluţia noastră se folosea de faptul ca numărul produselor posibile nu este foarte mare, din 2 motive.

1. Toate numerele trebuie să aibă ca factori primi doar numere din mulţimea 2 , 3 , 5 , 7, deoarece acestea sunt singurele cifre care sunt numere prime.
2. Având în vedere că numărul de cifre este limitat de 20, puterea maxima a lui 2 este limitată de 60 (numărul format din 20 de cifre de 8), cea a lui 3 de 40 , iar cele ale lui 5 si 7 chiar de catre 20.

Deci există maxim 60 * 40 * 20 * 20 = 960 000 de produse posibile. Observaţi că această margine superioară este o supraestimare destul de puternică, având în vedere că exponentul maxim nu poate fi atins de fiecare cifră în acelaşi timp.

Astfel, am putea să variem exponentii pentru fiecare dintre cele 4 cifre prime şi apoi să hotărâm pentru fiecare configuraţie daca se poate obţine dintr-un număr cu lungime între A şi B. Pentru a simplifica problema, observăm că dacă Lmin ar fi numărul minim de cifre necesar pentru a obţine numărul X, atunci pentru orice lungime L mai mare sau egală decât Lmin există un număr de lungime L care îl poate produce pe X. Adăugăm L - Lmin 1-uri in coadă. Pretty simple huh?. Numărul A devine astfel irelevant. Tot ce trebuie sa verificăm pentru un anumit număr X este dacă Lmin(X) este mai mic sau egal cu B.

Acest lucru se poate face printr-o abordare de tip greedy, ilustrată în fragmentul de cod de mai jos, extras din sursa lui Rareş Buhai, primul concurent care a rezolvat problema în timp de concurs.

int getNum(int x)
{	
	int result = 0;
	if (x != 1) ++result;
	for (int c2 = 0; c2 <= 3 * x; ++c2)
		for (int c3 = 0; c3 <= 2 * x; ++c3)
			for (int c5 = 0; c5 <= x; ++c5)
				for (int c7 = 0; c7 <= x; ++c7)
				{
					int minneed = c5 + c7, addmin = 100000;
					for (int k = 0; k <= min(1, min(c2, c3)); ++k)
						addmin = min(addmin, k + (c2 - k) / 3 + (c3 - k) / 2 + ((c2 - k) % 3 != 0) + ((c3 - k) % 2 != 0));
					minneed += addmin;
					
					if (minneed <= x)
						++result;
				}
	return result;
}

Acestea fiind zise, vă prezentăm soluţia lui Mihai Popa, a doua submisie corectă în timp de concurs.

int p = 3,add = 3;
	for ( int i = 2 ; i <= b ; ++i ){
		p += add;
		++add;
	}
	
	fprintf(g,"%d\n",p*p+1);

Demonstraţia o lăsăm ca tema acasă. Extindeţi raţionamentul de mai sus, potrivit căruia numerele de lungime L produc aceleasi produse ca numerele de lungime L - 1 şi, pe lângă acestea, unele noi pe baza celor vechi.
De notat că deşi soluţia lui Rareş (ca şi cea a comisiei..) este mai complexă şi mai greu de codat, are avantajul că necesită un timp scurt de gândire, fiindca este practic un brut. Alegerea unei soluţii nu neaparat eficiente sau scurte, dar care rezolvă problema în restricţiile date este uneori de preferat în dauna unei implementări simple cu idei uşor mai complicate, mai ales într-un concurs de tip Monthly, Codeforces, sau TC SRM.

Culori4

Deci contribuţia problemei ăsteia la concurs a fost o coloană de 0 adaugată în clasament?

Deşi problema pare să ceară fie o dinamică, fie un back optimizat până ajungi să dispreţuiesti autorul ca entitate prezentă pe Pământ, soluţia e de fapt destul de mişto. În general, problemele de colorare în sine sunt NP-complete, i.e se presupune ca nu admit soluţie în timp polinomial. Nu prea bag mâna în foc că acest caz particular este de asemenea NP-Complete*, însă presupun că cel puţin problema de numărare a colorărilor este. (Dacă mă contraziceţi, aş fi chiar entuziasmat :D).

Să rezolvăm o variantă mai simplă a problemei. Să presupunem că nu există două caractere ? alăturate. Astfel, culoarea unui anumit semn de întrebare nu afecteaza colorarea altui semn de întrebare. Putem deci răspunde cu o formula.
ANS = p1 * p2 * p3 * ... pk unde pi este numărul de posibilităţi de a colora al i-lea semn de întrebare.

Dacă ar fi să privim matricea ca o tablă de şah, facem observaţia critică conform căreia celulele albe sunt independente complet de cele negre. Mai precis, toate celulele albe au doar vecini negri iar celulele negre au doar vecini albi. Aşa că presupunând că toate celulele albe sunt fixate (pentru fiecare ? de casuţă albă am ales deja culoarea) putem doar să trecem prin cele negre şi să înmulţim pentru fiecare ? numărul de valori pe care le poate lua semnul de întrebare respectiv, conform formulei precedente. Având în vedere că K, numărul de ?, este mai mic sau egal cu 18, atunci fie numărul de semne de întrebare albe este mai mic sau egal decât 9, fie cel de semne de întrebare negre este mai mic sau egal decat 9. Obţinem astfel o complexitate de timp O(5 ^ (K / 2) * K).

Triangles

Prima soluţie care ne vine în minte are complexitate O(N log N) şi nu se încadrează în timp. Pentru a ajunge la ea, realizăm ca întotdeauna are sens ca numerele alese să formeze o secvenţă continuă în şirul valorilor sortate. Pentru o anume secvenţă din şirul sortat, putem afla dacă toate cele K elemente din ea sunt bune verificând ca v[i] + v[i + 1] >= v[i + K - 1]. Cu alte cuvinte, verificăm ca cele mai mici două numere sa poată forma triunghi cu cel mai mare dintre ele (acesta este practic cazul limită. Daca vreun alt triplet nu îndeplineşte condiţia asta, atunci nici tripletul acesta nu o va îndeplini). Această idee se implementează foarte uşor, însă sortarea necesită timp O(N log N). Poate dacă parsăm? Nope. Radix sort? Nope.

Soluţia bună are o linie in plus faţă de cea descrisă anterior. Ideea este ca de fapt nu o să avem nevoie niciodată de toate cele N numere pentru a găsi o soluţie printre ele. Este suficient să păstrăm doar primele K * log(2, Vmax) numere. Valoare care in cazul de faţă este egală cu 150 000. De ce? Gândiţi-vă ce înseamnă dacă o anumită secventă (i , i + K + 1) nu reprezintă soluţie. Rezultă că v[i + K - 1] > v[i] + v[i + 1]. Deci V[i + K - 1] > 2 * v[i]. Cu alte cuvinte, cât timp nu găsim soluţie, odată la cel mult K numere, valorile se dubleaza. Dar numerele nu pot fi mai mari decat 10 9, deci numărul de dublări este limitat de log(2, 10 ^ 9), care este aproximativ 30. Astfel complexitatea devine O((K log Vmax) log (K log Vmax)), iar linia despre care vorbeam este

n = min(n , 150 * 1000);

 Comentarii (5)

Categorii:

Fox Hunting

Cosmin
Cosmin Negruseri
31 august 2012

A fox hides in one of eleven holes. These holes are placed in a line. Each night the fox moves from its current hole to a neighboring one, left or right. Each morning you can check one hole. Is there a strategy that makes sure you catch the fox?

Fell free to discuss it in the comment section. If you saw it before, please don't spoil it.

 Comentarii (16)

Categorii:

Broken counter

Cosmin
Cosmin Negruseri
23 august 2012

What's the minimum value this Python code can print:

import threading

num_threads = 5
count = 10

counter = 0

def increment(count):
  for i in xrange(0, count):
    global counter
    counter += 1

threads = []

for i in xrange(0, num_threads):
  threads.append(threading.Thread(
                   target=increment,
                   args=(count,)))

for t in threads:
   t.start()

for t in threads:
   t.join()

print counter

The fact that the code is in Python doesn't really matter. Basically you're given 5 threads that each increment an integer variable counter exactly 10 times. The variable isn't guarded by any lock. You can assume that reads and writes to the variable are atomic operations. What's the minimum value the counter can have after all threads finished.

 Comentarii (8)

Categorii:
Vezi pagina: 12345678 910111213... 3637383940 (394 rezultate)