Sammarize's blog

Codeforces Beta Round 94
By Sammarize, 13 years ago, translation, In English

Hello everyone!

I am glad to welcome you on Codeforces Beta Round 94. I hope, some more early time of start will not have bad effect on you results =) 

I'm author of today problems. I'm a graduated student of SPbSU, Valery Samojlov. This is my second round. I hope, today nobody will be sorry of his participation. I want to say very big thanks to RAD, who rend me very big support with preparation of problems. Also thanks to Maria Belova, who has translate statements to English.

Please, don't be startled of unusually cost of problems:

Div-1: 1000 - 1500 - 1500 - 2000 - 2500

Div-2: 500 - 1000 - 2000 - 2500 - 2500


  • Vote: I like it
  • +160
  • Vote: I do not like it

Comments Comments (76)
| Write comment?
13 years ago, # |
← Rev. 2   Vote: I like it +20 Vote: I do not like it

It's a comfortable time for me, 2PM in China.

→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Looking forward~~~~~~~~
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
That's all right.
→ Reply
13 years ago, # |
  Vote: I like it +3 Vote: I do not like it
comfortable 100% 7AM :)
→ Reply
13 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

Delayed 10 minutes?!

I have college after it ends with 30 minutes, now it become 20 minutes :\ Hope I could make it on time!

→ Reply
13 years ago, # |
  Vote: I like it +32 Vote: I do not like it
4AM in Brazil. Not so comfortable.. but here we are! :D
→ Reply
13 years ago, # |
  Vote: I like it +34 Vote: I do not like it
6AM here. You are teaching me to live a more healthy life.
→ Reply
13 years ago, # |
  Vote: I like it +13 Vote: I do not like it
It is 9:30 AM in Iran. But it's interesting that today is holiday :)
→ Reply
13 years ago, # |
← Rev. 2   Vote: I like it -9 Vote: I do not like it

Very nice problems!

→ Reply
13 years ago, # |
  Vote: I like it -10 Vote: I do not like it
Nice problem set.
My mind is fully shaken. :)
→ Reply
13 years ago, # |
  Vote: I like it +8 Vote: I do not like it
Very nice problem set... Just 20 seconds more and would have submitted E as well. Took me a whole while to realize answer is simply (n - 1) choose (2 * k) * (m - 1) choose (2 * k)
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    Your idea is cool! It's, choose k pairs of brackets from the n-1 gaps, C(n-1, 2*k). Nice solution with Python.
    → Reply
13 years ago, # |
← Rev. 2   Vote: I like it +15 Vote: I do not like it

A good point of the contest was brief problem statements.

→ Reply
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it
I really need to learn that suffix-array thing. n^2*logn didn't play well with n=10^5 :-)
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Bruteforce can pass it.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Please elaborate , i thought nothing other than something like suffix array can solve it .
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Use priority_queue. Very easy idea, wish I had thought of it when I was coding on the competition. Instead I wrote something similar but got WA10.

        http://mirror.codeforces.com/contest/128/submission/870700
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it
          Have you tried 100000 numbers of a and 100000 as input?I find the input data of System Test is not strong enough....
          → Reply
          • 13 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            Yes I have. It took 0.533000s on my PC to finish. If you think about it it isn't very hard test case. I will put all strings of length 1 in the priority_queue and then I will remove all of them and insert all strings of length 2. That is O ( K * log2 ( N ) ).
            → Reply
            • 13 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it
              My priority_queue size is always N ( when I pop front element I push some element on the priority_queue ) and I perform K operations on it. So my solution have time O ( K * log2 ( N ) ) on every test case.
              → Reply
              • 13 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it
                You only have O(K*logN) if your comparisons run in constant time.
                That's why it is difficult to analyze.
                → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Idea is to use a priority queue. For example

        abc, 5. You will do the following:

        Push ("a", 0), ("b", 1), ("c", 2) on the heap. You will then pop the first element ("a", 0). Because 0 + 1 < size (3), you now push ("ab", 1) on the heap, and so on.

        Do this k-1 times and the top most element of the heap is the sought after substring.

        This gets AC. I'm not sure if you can construct a test case in which the comparison for the heap will make it too slow. I tried with aabbbbb...b and 10000, which should be very bad because all comparisons will be strings like aabbbbb and aabbbbbb, but it ran way fast enough.

        → Reply
        • 13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          And now I read that it should be k < 10^5. It still runs within time, but it's somewhat close :P
          → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Arg, you are right. That's only k*log(n).
      I hate when I overthink problems :-)
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Hm, times the length of the longest considered substring. I'm not sure how to get a good bound on that.
        → Reply
13 years ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it

Any ideas in problem D?
My approach is greedy. First, create a circle min, min+1, min+2,...,max,max-1,max-2...,min+1. Then check if it's possible to pair the rest numbers such that every pair consists of consecutive numbers since these pairs can be consistently added into the initial circle.

→ Reply
  • 13 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    I liked this problem enough to write a blog post about it: http://mirror.codeforces.com/blog/entry/3196. It has a "proof" for a greedy solution similar to what you describe. Hope you find it useful!

    → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Look at the histograms.  For a circle "min, min+1, min+2,...,max,max-1,max-2...,min+1", the histogram is 1 2 2.... 2 2 1.

    There's a solution if the histogram is a sum of histograms of overlapping circles.

    You can modify the circles greedily until each one is empty:  Pick one the circles on the left side.  Remove two pieces of the circle so that the min value is increased by one.  In the histogram, it means removing 1 to the two leftmost bins.  That's implemented in this solution .
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My gredy solution works as follows:

    let a1, a2 be the value of the biggest and second biggest value (without duplicates). Let c1, c2 be their associated counts. If c2 >= 2 we can "merge" an a1 with two a2s creating a segment: a2, a1, a2. This can now be seen as one a2, so we decrease c1 and c2 by one.

    The base case is when a2 is is also the smallest value (only two values). In this case c1 must be equal to c2.

    At all points we must have a1 - a2 = 1.

    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Very nice problem set. :)
→ Reply
13 years ago, # |
← Rev. 4   Vote: I like it +1 Vote: I do not like it

The Div 2 D.string
I use STL heap.

This is my code,it got TLE

if (P.top().pos<=len) P.push(Node(P.top().pos+1,P.top().s+S[P.top().pos]));



If turn to this can AC

Node tmp=P.top();
if (tmp.pos<=len) tmp.s+=S[tmp.pos++],P.push(tmp);


it really have big difference？
Is construct function make it slow,or access top()，or else？
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    For test abbbbb....b and k = 100000, it will create strings of total size k2 / 2. 
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Yes.But I tested this case,it work out in 2S???
      → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    There are weak tests, try to run your solution on test abbb...(50 000 times letter "b")....abbbbbbbbb...  (40 000 times letter "b"). your solution is wrong anyway, it must got TLE.
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
can anyone explain solution of "String" using suffix array? I solved it with suffix automata, but have no idean about array. Thx in advance


// лучше по-русски
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    This solution do not use any suffix strcture at all
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      What's the time complexity of that algorithm?
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        O(n + k)
        → Reply
        • 10 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I know this is an ancient comment but could you tell me how is it O(n+k)?

          for a test case like "aaaaaa..." wont it run in O(n^2)

          → Reply
13 years ago, # |
  Vote: I like it +5 Vote: I do not like it
Can someone explain the solution for Problem C (Div 1) in detail?
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    First, note that the two dimensions are independent, so we can reduce this to a 1-dimensional problem. So we start with some value n and want to pick k intervals each of which is strictly contained in the previous one. The number of ways to do this is just C(n - 2, 2k) because for any choice of 2k values in the range [1, n - 1] we can take the min/max to be the first interval, next min/max to be the second interval, and so on.
    → Reply
    • 13 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I still don't understand your explanation, can you make it more clearly? First, why the two dimensions are independent. Second, why is C(n-2,2k), where comes the 2k?


      By the way, your rating diagram is really fantasitc!
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it
        Sure. We can think of them as independent due to the following argument. Let's say we have two sequences, one for each dimension, e.g.

        [0, n], [1, n - 1], ...
        [0, m], [2, m - 1], ...

        which represent the left/right bounds and top/bottom bounds of the box at each of the k steps, respectively. So the first box is obviously (0, 0) to (n, m) and the second is (1, 2) to (n - 1, m - 1). We observe that for any two sequences of the left/right bounds and top/bottom bounds we get exactly one sequence of boxes. It suffices then to count the number of such sequences and multiply them together.

        To count the sequences, we look at just one of the sequences above, e.g. [0, n], [1, n - 1], [3, n - 2], ... and rewrite it "in order" like this: 0, 1, 3, ..., n - 2, n - 1, n. We know that 0 is always at the start and n is always at the end and there are exactly 2k values from 1 to n - 1 (two for each of the k intervals). Moreover, for any 2k values in [1, n - 1] we can uniquely construct the k intervals by taking the outermost values to be the first interval, then the next outermost to be the second, etc. For example: 0, 3, 4, ..., n - 3, n - 2, n becomes [0, n], [3, n - 2], [4, n - 3], ....

        Thus we have a one-to-one correspondence between such sequences and sets of 2k values in the interval [1, n - 1] of which there are C(n - 2, 2k).
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Thank you for your explanation, that's really amazing, I understand and finally get an AC ^_^. Now I solved all the problems in #94 div 2. It feels good.
          → Reply
    • 6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      There's just a slight mistake in your formula. It is supposed to be C(n - 1, 2k) since there are n - 1 different values in the interval [1, n - 1].

      → Reply
13 years ago, # |
  Vote: I like it +2 Vote: I do not like it
It was a standard problem set. Nice. Waiting for editorials. Thank you
→ Reply
13 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Tourist's solution on div1 problem A?


He wrote a non-recursive solution on this problem?

Can somebody explain the algorithm?


→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    Apparently he is checking where M can be after several moves.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it
      thx,  why did he use i+it-1 and i+it?


        xk:=i+it-1;
                yk:=j;
                if (xk > 0) and (yk > 0) and (xk < 9) and (yk < 9) then ncan[xk,yk]:=False;
                xk:=i+it;
                yk:=j;
                if (xk > 0) and (yk > 0) and (xk < 9) and (yk < 9) then ncan[xk,yk]:=False;
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        I think he checked whether the statue would be in certain position on this or next move.
        → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can use DP with state x, y, #moves.

    You win iff you can survive 8 moves.

    Then for each mem[x][y][cmove] you need to check if there's a rock in the cmove places above (it would move on you, so you die) or if there's a rock cmove-1 places above (it would be there when you tried to move, so invalid move).

    → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Obviously, it's not necessary to check whether you can reach Ann, the only thing to do is to check is any state reachable after 8 moves as all statues disappear after 8 moves.
    So, you can calculate isreachable(step, x, y) the following way: if now we are at step S and in point (x, y)  your simply check if the point (x + dx[i], y + dy[i]) is free of statues and no statue will move there after this step ( can be calculated in O(1). After all, if any isreachable(8, i, j) is true, you win, otherwise you lose.
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
How can I download a complete test case? I need to know what is test case 50 in problem B DIV1.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Seems like you cant. But someone have problems with 50 test and he solved it with using int64 to calc string count.
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I had WA50 because i kept total number of strings beginning with certain letter in int. Changing to long long solved this problem.
    Looking at your code, i see suspicious line int xx = sum[t][i]. May be problem is there.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Yes it's. :( I wrote this line to debug something, but the sum array itself is long long. :(
      → Reply
13 years ago, # |
  Vote: I like it +18 Vote: I do not like it
Can anybody tell me how to solve the problem E in div 1?

many thanks.
→ Reply
  • 13 years ago, # ^ |
    ← Rev. 3   Vote: I like it +58 Vote: I do not like it

    If there were only one banana, then the answer would be 1 + K * (K+1) / 2  (it's easy to construct such a placement of lines, where each line intersects all previous, and all intersection points are different).

    Now suppose we have several bananas.

    If there is a line that intersects all bananas (intersects, but not touches), then the answer is 1 + K * (K+1) / 2 + (K + 1) * (N - 1). This formula means that we take an answer for one banana, and we cut all the remaining bananas by K lines into K+1 parts (because all intersection points are situated in the first banana). Why is it optimal to put all intersection points into one banana? Because each intersection point adds +1 to answer, so we've already achieved theoretically maximum possible value.


    So, the problem is in reality the following: given N circles, determine, how many of them can be intersected using one line. I've solved it in O (N^2 log N) in the following manner: we suppose that the line touches one of the circles (we iterate over all N of them), so the position of the line can be described as polar angle. So any other circle can be described as an interval [angle1; angle2), where angle1 and angle 2 are the angles, when our line touches this circle. (We exclude the right end of the segment, because we don't want to find an answer, were a line touches several circles, but can't be made to intersect all of them.)

    So, the algorithm now is to find the point with maximum number of intervals covering it, which can be done in O (N log N).

    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it

when will the editorials come out.Waiting for it desperately.....
→ Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
can anyone help me in finding the editorial of this contest 94..
→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Some hint for Problem B Div 1 with Suffix Array? I am dead!

→ Reply