### Sammarize's blog

By Sammarize, 11 years ago, translation,

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

• +160

 11 years ago, # | ← Rev. 2 →   +20 It's a comfortable time for me, 2PM in China.
•  11 years ago, # ^ |   +17 For me too, it's 1PM in Russia ^_^
•  11 years ago, # ^ |   +21 comfortable time here too at 1AM in the USA. I code better at night.  =D
•  11 years ago, # ^ |   0 lucky you ... I have no milk for my coffee ! And it's far too late to get one in TimHortons/Starbucks (
•  11 years ago, # ^ |   0 You really geek ^_^
•  11 years ago, # ^ |   +1 Coding at night? It's hardcore =)
•  11 years ago, # ^ |   0 soamI &&soIam
•  11 years ago, # ^ |   +8 Every night,my school will cut down the power at 23:30.
•  11 years ago, # ^ |   +8 My school will cut down the power at 23:00.I always take the contests in the dark.
•  11 years ago, # ^ |   0 I shut down my power at 0:00, I can't join the contests at night:）
 11 years ago, # |   0 Looking forward~~~~~~~~
 11 years ago, # |   0 That's all right.
 11 years ago, # |   +3 comfortable 100% 7AM :)
 11 years ago, # | ← Rev. 2 →   +13 Delayed 10 minutes?!I have college after it ends with 30 minutes, now it become 20 minutes :\ Hope I could make it on time!
 11 years ago, # |   +32 4AM in Brazil. Not so comfortable.. but here we are! :D
 11 years ago, # |   -6 11:30 AM here in India :)
 11 years ago, # |   +34 6AM here. You are teaching me to live a more healthy life.
 11 years ago, # |   +13 It is 9:30 AM in Iran. But it's interesting that today is holiday :)
 11 years ago, # | ← Rev. 2 →   -9 Very nice problems!
 11 years ago, # |   -10 Nice problem set.My mind is fully shaken. :)
 11 years ago, # |   +8 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)
•  11 years ago, # ^ |   +3 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.
 11 years ago, # | ← Rev. 2 →   +15 A good point of the contest was brief problem statements.
 11 years ago, # |   +1 I really need to learn that suffix-array thing. n^2*logn didn't play well with n=10^5 :-)
•  11 years ago, # ^ |   0 Bruteforce can pass it.
•  11 years ago, # ^ |   0 Please elaborate , i thought nothing other than something like suffix array can solve it .
•  11 years ago, # ^ |   0 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://codeforces.com/contest/128/submission/870700
•  11 years ago, # ^ |   +1 Have you tried 100000 numbers of a and 100000 as input?I find the input data of System Test is not strong enough....
•  11 years ago, # ^ |   0 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 ) ).
•  11 years ago, # ^ |   0 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.
•  11 years ago, # ^ |   0 You only have O(K*logN) if your comparisons run in constant time.That's why it is difficult to analyze.
•  11 years ago, # ^ | ← Rev. 2 →   0 I agree.
•  11 years ago, # ^ |   0 nice.You have done well.I like your style because I dont know how to solve it by suffix-array ^_^
•  11 years ago, # ^ |   0 Thank you. :)
•  11 years ago, # ^ |   0 Idea is to use a priority queue. For exampleabc, 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.
•  11 years ago, # ^ |   0 And now I read that it should be k < 10^5. It still runs within time, but it's somewhat close :P
•  11 years ago, # ^ |   0 Arg, you are right. That's only k*log(n).I hate when I overthink problems :-)
•  11 years ago, # ^ |   0 Hm, times the length of the longest considered substring. I'm not sure how to get a good bound on that.
 11 years ago, # | ← Rev. 3 →   +5 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.
•  11 years ago, # ^ | ← Rev. 3 →   0 I liked this problem enough to write a blog post about it: http://codeforces.com/blog/entry/3196. It has a "proof" for a greedy solution similar to what you describe. Hope you find it useful!
•  11 years ago, # ^ |   0 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 .
•  11 years ago, # ^ |   0 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.
 11 years ago, # |   0 Very nice problem set. :)
 11 years ago, # | ← Rev. 4 →   +1 The Div 2 D.stringI use STL heap.This is my code,it got TLEif (P.top().pos<=len) P.push(Node(P.top().pos+1,P.top().s+S[P.top().pos]));If turn to this can ACNode 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？
•  11 years ago, # ^ |   +1 For test abbbbb....b and k = 100000, it will create strings of total size k2 / 2.
•  11 years ago, # ^ |   0 Yes.But I tested this case,it work out in 2S???
•  11 years ago, # ^ |   0 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.
 11 years ago, # |   0 can anyone explain solution of "String" using suffix array? I solved it with suffix automata, but have no idean about array. Thx in advance// лучше по-русски
•  11 years ago, # ^ |   +3 This solution do not use any suffix strcture at all
•  11 years ago, # ^ |   0 What's the time complexity of that algorithm?
•  11 years ago, # ^ |   0 O(n + k)
•  7 years ago, # ^ |   0 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)
 11 years ago, # |   +5 Can someone explain the solution for Problem C (Div 1) in detail?
•  11 years ago, # ^ |   +3 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.
•  11 years ago, # ^ | ← Rev. 2 →   0 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!
•  11 years ago, # ^ |   +5 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).
•  11 years ago, # ^ |   0 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.
•  4 years ago, # ^ |   0 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].
 11 years ago, # | ← Rev. 3 →   0 I've submitted the same code for problem D Div.2 with both MS C++ and GNU C++. First one gets TLE, while the second one is accepted! Is there a point I'm missing here?http://codeforces.com/contest/129/submission/871316http://codeforces.com/contest/129/submission/871321
 11 years ago, # |   +2 It was a standard problem set. Nice. Waiting for editorials. Thank you
 11 years ago, # | ← Rev. 2 →   0 Tourist's solution on div1 problem A?He wrote a non-recursive solution on this problem?Can somebody explain the algorithm?
•  11 years ago, # ^ |   +5 Apparently he is checking where M can be after several moves.
•  11 years ago, # ^ |   +5 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;
•  11 years ago, # ^ |   0 I think he checked whether the statue would be in certain position on this or next move.
•  11 years ago, # ^ |   0 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).
•  11 years ago, # ^ |   0 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.
 11 years ago, # |   0 How can I download a complete test case? I need to know what is test case 50 in problem B DIV1.
•  11 years ago, # ^ |   0 Seems like you cant. But someone have problems with 50 test and he solved it with using int64 to calc string count.
•  11 years ago, # ^ |   0 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.
•  11 years ago, # ^ |   0 Yes it's. :( I wrote this line to debug something, but the sum array itself is long long. :(
 11 years ago, # |   +18 Can anybody tell me how to solve the problem E in div 1?many thanks.
•  11 years ago, # ^ | ← Rev. 3 →   +58 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).
 11 years ago, # |   0 when will the editorials come out.Waiting for it desperately.....
 » 10 years ago, # |   0 can anyone help me in finding the editorial of this contest 94..
•  » » 10 years ago, # ^ |   0 It hasn't been created by problem author yet.
•  » » 10 years ago, # ^ | ← Rev. 3 →   0 in russian, it is there -  http://codeforces.ru/blog/entry/3219
 » 6 years ago, # |   0 Some hint for Problem B Div 1 with Suffix Array? I am dead!
•  » » 15 months ago, # ^ |   +8
 » 2 years ago, # |   0 Solution for Div1 B, please?