Ripatti's blog

By Ripatti, 13 years ago, translation, In English
A. In this problem you can just do what is written in the statement. Let read all words. For each of them compute its length L, its the first and the last letter. If L > 10, output word without any changes, otherwise output the first letter, next L - 2 and finally the last letter.

B. At first, compute . It equals mnk / 100⌋, where x is rounding down. Next we fill first z / k squares with a saturation k. (⌊ z / k⌋ + 1)-th square (if it exists) we fill in a saturation z - ⌊ z / kk. All other squares we leave with a saturation 0.

C. Define an good polygon as a regular polygon which has a knight in a good mood in every of its vertex. Side of polygon we will measure in arcs which is obtained by dividing border of round table with knights.

Freeze the length of the side. Let this length equals k. Observe that the regular polygon with such length of side exists only if k divides n. We have exactly k of such polygons. Every of them has exactly n / k vertices. Check every of the polygons for goodness by review all of its vertices.

If sum of vertices with knight in a good mood equals to n / k, this polygon is good. Checking of all polygons with some frozen length of side works in an O(n).

Now observe that n has of divisors. Really, all divisors (may be except only one) we can divide into pairs (for i corresponds n / i, for i = n / i there is no pair). One of divisors in every pair less than . It means thah number of pairs no more than and number of divisors no more than .

It gives solution - iterate over all divisors of n and for every of them check existence of good polygon with length side equals this divisor. Solution has an time.

In reality for big n is has divisors. So solution actually has O(n4 / 3)-complexity. For all numbers less than 105 maximal number of divisors is 128.

UPD. There was found an solution by some participants. This solution uses following idea. If we have a good polygon with xy vertices, we also have a good polygon with x vertices. So we can check only prime divisors of n (except 2 - here we must check 4).

D. This problem can be divided into some subproblems.
 Author's solution means following ones:

1. Check validness of square 3 × 3. Square is valid if all cards in it has equal suit or different rank. You may not check equal suit because equal suits imply different ranks.

2. Find 2 valid noninetsect squares 3 × 3 or return thah there are no ones. You can check all pairs of squares for inetsection. If some pair has no intersections check them with solution of subproblem 1.

3. Build set of cards which can be replaced with jokers. Generate full deck without jokers and drop from it all cards which in rectangle n × m are present.

4. Find number of jokers and its positions in rectangle.

5. Main subproblem. At first, solve subproblems 3 and 4. Now replace jokers in rectangle with cards from deck from subproblem 3 by all possible ways. For every replace solve subproblem 2. Arter all of variants of replacement just output answer.

There are O(n2m2) solution with small constant.

E. At first, you can use some search engine for find periodic table in some printable form. Next use copy-paste (one or several times) and format it by deleting all excess. It is mechanical work for no more than 5 minutes. Also some parser may be written. Note than author's solution does not mean write 100 symbols by hand from a picture. Next build some functions which transform symbols into numbers and vice versa.

So, we have some set of numbers. We need summarize some from them and get some another set of numbers. We will use dymanic programming over subsets.

Compute the first dp dp1[mask]->sum. For each subset calculate sum of numbers of all atoms in this subset. It can be done in O(2nn).

Now compute the second dp dp2[mask]->length. The "length" is a length of some prefix of result sequence of atoms which can be obtained by subset mask. If length -1, it means that it is impossible to get any prefix from this subset.

The second dp we can calculate in O(3n). Iterate over all masks and if dp2[mask]!=-1, iterate all its subsets of remained atoms (invert mask and get all its submasks). If some subset has sum of numbers which equals number of (dp2[маска]+1)-th atom from result set, recalculate dp2[mask XOR submask]=dp2[mask]+1.

At end, if dp2[2n - 1]=k, there are solution.

There are O(3n + 2nn) solution.

In this problem some brutforce solutions are passed because it is difficult to pick up some counterexample.

UPD. SkorKNURE found a solution in O(2nn). This solution is some modification of the author's solution.

Instead of dp2 calculate dp dp2'[mask]->(i,j), where i is a length of prefix which mask covers and j is part of number of (i+1)-th atom which mask covers.

Iterate over all masks. For each mask iterate over all its 0-bits (they are atoms which cover nothing from the finish set). We try to cover with this 0-bit a remainder of number of the (i+1)-th atom from the finish set. Let atomic number of an atom for current 0-bit is p and this atom is q-th in the start set. If we cover with this atom only part of the remainder of number of the (i+1)-th atom, dp2'[mask XOR (1<<q)]=(i,j+p). If we cover with this atom the remainder fully (and exactly this remainder, no more!), dp2'[mask XOR (1<<q)]=(i+1,0).

Now dp1 is useless. If at end dp2'[2n - 1]=(k,0), solution exists (it is easy to restore it), otherwise there is no solution.
  • Vote: I like it
  • +47
  • Vote: I do not like it

| Write comment?
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it
system testing took very long time.. and on the middle of contest, server down once.. what happened here?
13 years ago, # |
  Vote: I like it +4 Vote: I do not like it
bd
  • 13 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    cool. I understand you. Its great!
    • 13 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      I can't understand , tell me what is bd?
      • 13 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it
        looks like "thumbs up"
        (I feel proud of myself for this guess :))
      • 13 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it
        It's ....Just like ORZ....
13 years ago, # |
  Vote: I like it +7 Vote: I do not like it
In problem C we can consider only _prime_ divisors of n (at most 6 :), as number of vertices. But there is one tricky case that i've missed, unfortunately.
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
In problem E, can you explain what is a mask and its submasks ?
13 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
edit: I'm sorry that I didn't notice Lepetrandr's post.

For (C) it suffices to check polygons with a prime number of sides (except for 2, then check 4), that gives O(log n) divisors to check.
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Yes , because if the - polygon with length equal to n -  is regular , we can create another regular polygons which have the length of any prime divisors of n..but this number is not equal to log(n). This is equal to prime divisors of n.
    • 13 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it
      Number of prime divisors is about equal to ln (n) in case of big n.
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it
In the first problem explanation there's a type error:

 If L > 10, output word without any changes, otherwise output the first letter, next L - 2 and finally the last letter.

Should be "If L ≤ 10"
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
In author's solution of problem E,
does dp1 calculation really need dynamic programming?
I think, this part can be done by simple 2 loops.

for(int mask=0;mask<(1<<n);mask++){
  dp1[mask]=0;
  for(int i=0;i<n;i++){
    if(mask&(1<<i)) dp1[mask]+=(weight of i-th atom);
  }
}
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    You are right. It can be calculated by your way. Also it is calculated in this way in the author's solution.
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
can you please explain O(nlog(n)) solution for question C ?
  • 13 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it
    assume n= p1q1 * p2q2 * ... * pmqm, where all the pi is prime.
    then for each i, (1<=i<=m), check if exist good polygyn with exactly pi vertex. if at least one of this question has positive answer then output "YES", otherwise output "NO". because if we have a good polygyn with A*B vertex, then we have a good polygyn with A vertex.
    sorry for my poor english!

    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      sorry, couldn't understand, can you explain with one example ?
      • 13 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it
        assume this good polygyn with A*B vertex:
        S1, S2, ... , SA*B
        now we have subpolygyn which have only A vertex, like this:
        S1*B, S2*B, ... , SA*B.
        now it's obviously that if the circle  has a good polygyn then it has a polygyn with prime vertex. it's algo is O(nlgn) because for each i, pi >=2
        so m<=lgn, and check function is O(n). therefore main algo is O(nlgn). 
13 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Some help for Java users with problem E: http://pastebin.com/ZsDc3P1E

(Yes, I'm a necroposter)
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why do I need to output $$$L - 2$$$?