### wilcot's blog

By wilcot, history, 7 years ago, translation,

Hello, Codeforces!

My name is Ivan Udovin, and I would like to say, that the Codeforces Round #344 will be held on Thursday (March 3, 2016 at 19:35). This is our first round, but it doesn’t mean that problems will be boring and not interesting. The problemsetters of this round are me (wilcot) and Ilya Kheifets (xfce8888). Thanks a lot to Alex Vistyazh (netman) and unknown person (he don’t want to be added in the announcement) for testing our round. Also I’d like to thank Fedor Korobeynikov (Mediocrity) for his awesome idea for task E.

We thank Gleb Evstropov (GlebsHP) for his help in preparing the contest, Maria Belova (Delinur) for translating the statements into English, and, of course, Codeforces team and Mike Mirzayanov for unique Codeforces and Polygon platforms.

This round consists of five problems. Main heroes of this round: Blake — the owner of the "Blake Technologies" company, and Chris — an employee of this company, and others.

Scoring distribution: 500, 1000, 1500, 2000, 2500.

Good luck, have fun.

PPS. Congratulations to the winners:

Div. 2:

Div. 1:

• +246

 » 7 years ago, # |   -16 I miss a normal codeforces round. I think this one will be interesting. Good luck to everyone.
 » 7 years ago, # |   +9 There is a small typo in the article — while the article says Wednesday, the actual round takes place on Thursday. Could you fix it please?
•  » » 7 years ago, # ^ |   +10 Thank you.
 » 7 years ago, # |   +23 A new round, and an new hope to become expert ^_^
•  » » 7 years ago, # ^ |   +42 Or pupil >:)
•  » » » 7 years ago, # ^ |   +9 probably yes :(
•  » » » » 7 years ago, # ^ |   +5 Hope you'll have a good round, though. Good luck!
•  » » » » » 7 years ago, # ^ |   +4 thanks, for you too :D
•  » » » » » » 7 years ago, # ^ |   +8 So finally u became 'Pupil' :D
 » 7 years ago, # | ← Rev. 4 →   -26 and unknown person (he don’t want to be added in the announcement) but it is important to know who tested a round for us. Generally, a round won't be interesting if people see it was tested by a newbie, but higher ratings can draw more attentions, right? So, at least writing the tester's rating can be useful here. Alternatives,Thanks a lot to Alex Vistyazh (netman) and an International Master (who don’t want to be ...
•  » » 7 years ago, # ^ | ← Rev. 2 →   +8 If the tester was someone unrated (or a "newbie") would you refuse to participate?
•  » » » 7 years ago, # ^ |   0 I am not talking about unrated users, but newbies or low rated ones. There are many reasons why tester's rating also matters. see these comments: http://codeforces.com/blog/entry/19849#comment-247087
 » 7 years ago, # |   -20 nice short announcement. waiting for an interesting problem-set and best of luck for your first round.
•  » » 7 years ago, # ^ |   0 thank you my good friend, wish you all the best!!!! may the best coder win
•  » » 7 years ago, # ^ |   +10 why so many downvote on this comment :o
•  » » » 7 years ago, # ^ |   +6 It is inertia. If it happens so that the first person downvotes the comment, the others are inclined to do the same. It is also true if the comment gets upvoted first. This psychological phenomenon clearly manifests itself here and on other internet platforms where people can see how others vote. It is highly exploited in the real life, for example, in advertising or presidential campaigns. By the way, if you are interested, it is one of the many cognitive biases :).
•  » » » » 3 years ago, # ^ |   0 Then I'm upvoting every comment I think should get upvoted.
 » 7 years ago, # |   +22 expert next goal
•  » » 7 years ago, # ^ |   +1 How long did it take you to become a specialist?
•  » » » 7 years ago, # ^ |   +16 you can check his profile if you are interested to know
 » 7 years ago, # |   +39 Codeforces Round #344 (Div. 2) Why do they always add Codeforces before the round? Who doesn't know this much? Or maybe its just a safety measure to stop people from asking questions like Will the round be conducted on Codeforces? In that case, you can change the heading to Rated Codeforces Round #344 (Div. 2)
•  » » 7 years ago, # ^ |   +18 Did Codeforces Round mean conducted on Codeforces? How about previous round such as 8VC Venture Cup 2016? No Codeforces stuff in its round name.
•  » » » 7 years ago, # ^ |   0 Pretty sure about the fact that every Codeforces Round #xxx type of round has been conducted on Codeforces so far, not exclusively though, like 8VC,Manthan,etc.
•  » » » » 7 years ago, # ^ |   +4 Supposedly, it means that the round was mostly concluded with the support of Codeforces staff, than some other company (like VK Cup, AIM Tech, etc.) hence, they add "Codeforces" before the name of the round.And by support of Codeforces staff, I don't mean just the Polygon system, I mean the help of translators (Delinur) and other outside help (Zlobober RIP GlebsHP)
•  » » » » » 7 years ago, # ^ |   0 How did you cross out the word? I used MS Word to cross text off, but when I copy paste it here, the cross out gets cancelled.
•  » » » » » » 7 years ago, # ^ |   0 your text herepower of html
•  » » » » » » » 7 years ago, # ^ |   +11 Thanks
•  » » » » » » » » 7 years ago, # ^ |   0 I'm an idiot
•  » » » » » » » » » 7 years ago, # ^ | ← Rev. 2 →   0 Well this might mean, I'm not really stating I'm an idiot :D
•  » » » » » » » » » 7 years ago, # ^ |   0 Are you...heisenberg?
•  » » » » » » 7 years ago, # ^ |   0 Editor input: Totally Krossed OutResult: Totally Krossed Out
•  » » » » » » » 7 years ago, # ^ |   -6 Let me try that
•  » » » » » » » » 7 years ago, # ^ |   0 There's also a "preview option" for these matters...
•  » » » » » » » » » 7 years ago, # ^ |   0 Let me try that
•  » » » » » 7 years ago, # ^ |   +19 Thank you for burying me, though it seems like I am still alive.
 » 7 years ago, # |   +44
•  » » 7 years ago, # ^ |   +2 nice pp
•  » » 7 years ago, # ^ |   +24
•  » » » 7 years ago, # ^ |   -18 So what?
 » 7 years ago, # |   -11 "Main heroes of this round: Blake — the owner of the "Blake Technologies" company, and Chris — an employee of this company, and others." I think there is tree problem :3 , the root of the tree is Blake and Chris is one of the leafs :D . it will be so interesting if that's true :D .
•  » » 7 years ago, # ^ |   0 What is the theory behind this?
•  » » 7 years ago, # ^ |   +3 Problems will be like As Blake is the CEO, he doesn't have time to solve this problem because he has bigger problems to solve, so he asks Chris
 » 7 years ago, # |   0 No dynamic scoring please -_- Hope to see some interesting problems with good problem statement :D
•  » » 7 years ago, # ^ |   +9 Don't worry, usually standard CF rounds don't use dynamic scoring.
•  » » » 7 years ago, # ^ |   0 Thanks :)
 » 7 years ago, # |   -16 Ufff.... seems I forgot to register on time. Solved the first task and found that cannot sumbit it. Can you please let me register still?...
 » 7 years ago, # |   +8 Only in my device Google Chrome didn't open or brake Codeforses(last 30 minute)?
 » 7 years ago, # |   +6 I might be the only contestant who got hacked on A. RIP :D
•  » » 7 years ago, # ^ |   +3 Don't worry. Many got hacked!
•  » » 7 years ago, # ^ |   +23 you have your friends...
•  » » » 7 years ago, # ^ |   0 2nd hacked aswell. motivation--
•  » » » 7 years ago, # ^ |   0 How can you see hacks of different people?
•  » » » » 7 years ago, # ^ |   0 Go to status tab and filter out hacked solutions (in right)
•  » » » 7 years ago, # ^ |   +9 Mom, got a camera, i am in a television!!!
 » 7 years ago, # |   +9 Interesting problemset!Can someone describe me solution for the fifth task ?
•  » » 7 years ago, # ^ |   +3 All I've came to:You need to maximize value sum(A[j], A[j + 1], ..., A[i — 1]) — A[j](i — j) if i > j. Or value A[i] * (j — i) — sum(A[i + 1], A[i + 2], ..., A[j]) if i < j.And print initialy characteristic + (diff > 0 ? diff : 0)How to do this faster than O(n^2) I can't get:D
•  » » » 7 years ago, # ^ |   0 Then I supposed we will iterate over all i and find index j with maximum value j*A[i]-sum[j] where sum[j] denoting sum of first j elements for j>i. Similar way for i
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   +3 Yep, that's right. Here you can find how to do that in time with O(n) preprocessing time.
•  » » » » » 7 years ago, # ^ |   0 lol, some time ago I've tried understand this, but without success. Maybe now I'll come to success. Thanks for link)
•  » » » » » 7 years ago, # ^ |   0 Thanks. I heard for it normally, but I have never used it. I must learn several optimisations :)
•  » » 7 years ago, # ^ | ← Rev. 10 →   0 We iterate the array. For ith index we will find the best position j, left to the i (it could be right instead of left, but we will compute the right in another iteration), which maximizes (this equals to change of the value of the array when we move jth element to ith position). As I said before we do the same thing (almost the same thing, equations are little different of course) for right. Then, the answer is the value of the original array + max(0, max of all changes).To find the best j for a particular i, we need to fiddle with the equations a little and represent every element as a linear line:ps[0] =  - ar[0]ps[i] = ps[i - 1] - ar[i]max1 ≤ j < i{ps[i] - ps[j] - ar[j] * j + ar[j] * i} = ps[i] + max1 ≤ j < i{( - ps[j] - ar[j] * j) + ar[j] * i}Now we can represent ith element as a linear line. ith line equals to y = ar[i] * x + ( - ps[i] - ar[i] * i).We first add the line 1. We then start iterating from index 2. When we're done with i (computed the result for it), we add the line i to our structure.(To find the result for that position) When we're at a new position, let's again call it as i, we find the line which has the highest value for x = i. We also need to increase this value by ps[i].To find the best line, we can use the convex hull trick on a segment tree, since slopes aren't non-decreasing like in the case of traditional convex hull trick.Time complexity: O(NlogN)
 » 7 years ago, # |   +6 I swear, in next few CF rounds I will not hack! :(How to solve C? I guess we have to sort three values i, ti and ri according to ri? How to do the same?
•  » » 7 years ago, # ^ |   0 I did it with segment tree+two pointer. Phew! Lot of confusing code
•  » » » 7 years ago, # ^ |   0 I thought of solving the problem like this. Find maximum value of ri and it's position in input. Then all sortings done before this input will be useless. After this input, check for next largest value of ri and repeat this process. Obviously after finding ri we have to do something in array(I still need to find out more).
•  » » » » 7 years ago, # ^ |   0 I thought along the same lines but this would fail for worst case as in: 1 10 2 9 1 8 2 7 1 6 
•  » » » » » 7 years ago, # ^ |   0 Yea i thought of that case too but i think we can do something between finding next ri. Like if we say for t1=1, r1=10 and t2=2, r2=8 then we can say from 1 to 8 array is descending and from n=9 to 10 array is ascending. Now we choose numbers in array. I think it can be done nikitosoleil method(two arrays). I am not sure.
•  » » » 7 years ago, # ^ | ← Rev. 7 →   0 My solution is much more easier. I have two sorted arrays (increasing and decreasing order) and taking a look only at elements, that had changed their position. For every position I store will it be sorted at last time int dec or inc order. In first case I am placing in this position first unused element from dec array, in another case first from inc arr. You can take a look at my submission: 16494098 for better understading me. Hope that this will work. P.S. It was the first time when I have submitted three problems less than in one hour :) UPD: Failed. UPD2: Bugged code, but right idea. Some little changes and AC: 16501782
•  » » » » 7 years ago, # ^ |   0 Damn! Ofcourse! Since we are only looking on right side of the segment for maximum, I could've simply done a suffix-sum calculation in O(M) lol
•  » » » » 7 years ago, # ^ |   0 No wonder you were expert. :) Sometimes contest go bad, very bad. :(
•  » » » » » 7 years ago, # ^ |   +1 In this and two contests before I have done stupid mistakes in one problem, but on the previous contest I have done stupid mistakes in all problems)
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 What I did:Found the maximum number of sorted elements from all queries, from 0 to xSorted [0,x]Then from that query looped to the end of the queires reversing the array from 0 to query's length, keeping track of what order was used last time. If the order changed, then reversed the array, otherwise did nothing.
•  » » » 7 years ago, # ^ | ← Rev. 4 →   +4 I think your solutions fails for this test : inI have hacked a similar solution with this test. N = 200000 K = 200000 print N, K for i in xrange(N): print i + 1, print for i in xrange(K): if(i % 2 == 0): print 1, N — i else: print 2, N — i 
•  » » » » 7 years ago, # ^ |   0 What is your test? I can not see it.
•  » » » » » 7 years ago, # ^ | ← Rev. 2 →   0 Sorry, now check again
•  » » » 7 years ago, # ^ | ← Rev. 3 →   0 I won't know until system tests are over, but I did the following: EDIT: Failed on test 13. I think the main idea is correct though, so check the last paragraph. If there are n numbers, create an array of size n (orderings) of integers, initialized at 0. Read input numbers and put them in a linked list. Create empty stack too. Read managers. For each manager, set orderings[r] = t (1 or 2). Set sorted = false. For i = n — 1 until 0: 4.1. if (ordering[i] != 0 && !sorted) list.sort(), sorted = true;4.2. if ordering[i] == 1: pop from the left of the list and push to stack.4.3. else: pop from the right and push to stack. Pop from the stack and print until empty. It's not exactly that, because when ordering is 0 you have to look at the last order, unless no sort has been performed yet.I'm not sure about whether it's right or left for orderings 1 or 2, because I don't remember which one was nonascending/descending, nor the default order of list.sort(). But when ordering is 0 you always pop from the right (if no sort has been done yet, else you follow the previous left-right rule).The idea is that if the largest sort is n — k elements, the last k are in the initial order. From there, the n — k — 1 indexed element is the biggest/smallest number left (depending on the direction of the last sort of that size), the list is reduced in each step this way, until you get to the empty string.
•  » » 7 years ago, # ^ |   0 I simply took maximums of type_1 query and type_2 query except for the last query, if in case last query is for type_1 then i first sorted max(type_2) in non-descending order and then sorted max(type_1) in non ascending order,and vice versa for the type_2 query in the last query. hope it works... :)
 » 7 years ago, # |   0 Somebody know why KMP on problem D might give WA14? And how did you solve that problem? I thought of KMP, but now I see that I could use hashing also.
•  » » 7 years ago, # ^ |   +3 Check for overflow in your solution. Test 14 is a big one.
•  » » 7 years ago, # ^ |   +6 I used Z-function
 » 7 years ago, # |   0 Wow C has 1k submissions!! It took me lot of time to code C
•  » » 7 years ago, # ^ |   0 I think a lot of them would fail System Test
•  » » 7 years ago, # ^ |   0 From your earlier comment it seems that your solution is more complicated that it needs to be.
•  » » » 7 years ago, # ^ |   0 Yeah, prefix/suffix sums mostly ditch me in contests because I always end up coding segment tree
 » 7 years ago, # |   +3 So, what was the hack cases for A and B?
•  » » 7 years ago, # ^ |   0 I tried to hack for int overflow in A. But I am stupid there will be no int overflow. In B, I tried hacking TLE submissions but i failed! :(
•  » » » 7 years ago, # ^ |   -15 There can be overflow Input 1 536870911 536870911
•  » » » » 7 years ago, # ^ |   0 Only if you've used short int datatype, or char, or bool ;)
•  » » » » 7 years ago, # ^ | ← Rev. 3 →   0 Answer is 1,073,741,822.Answer fits in int.There will be no overflow because input is restricted till 2^29 and if we 'OR' all powers of 2 from 1 to 2^29 we will get 2^30 — 1. Then adding we will get 2^31 — 2 which fits in int range.
•  » » » » 7 years ago, # ^ |   0 536870911 + 536870911 is almost twice less than 231.
•  » » 7 years ago, # ^ | ← Rev. 2 →   +3 B: If you update the grid after each operation, worst-case complexity is O(k * max(n, m)).
•  » » » 7 years ago, # ^ |   0 Ah I see. I thought there is some tricky case...
 » 7 years ago, # |   +12 Second problem with O(k*n) k = 100000 n = 5000 failed in hacking. So fast...
•  » » 7 years ago, # ^ |   +3 Same there:D
•  » » 7 years ago, # ^ |   0 i was able to hack with this test case cout << 5000 << ' ' << 20 << ' ' << 100000 << endl; forall(i,0,100000){ cout << 2 << ' ' << 2 << ' ' << 2 << endl; } 
•  » » » 7 years ago, # ^ |   +9 WHAT ? :|  long long int n, k, d, i, j, ans, currA, currB; cout << "5000 1 100000\n"; for (i = 0; i < 100000; i++) { cout << "2 1 10\n"; } This gave me unsuccessful hacking attempt :\
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   +6 cout << 20 << " " << 5000 << " " << 100000 << endl; for(int i = 0 ; i < 100000; i++){ cout << 1 << " " << 1 << " " << 1 << endl; } why is this unsuccessful on bruteforce
•  » » » » » 7 years ago, # ^ |   +11 Operation 1 is much faster than 2. (memory access time)
•  » » » » » » 7 years ago, # ^ | ← Rev. 2 →   0 Even operation 2 doesn't seems to work atleast for me. Here's the solution i was trying to hack: http://codeforces.com/contest/631/submission/16492474
•  » » » » » » » 7 years ago, # ^ |   +6 The submission used long long int b[n][m]; so the memory is contiguous. (especially you specified m = 1)Had it be b[5000][5000] your hack would be successful.
•  » » » » » » » » 7 years ago, # ^ |   0 Yes i think you are right. Others are doing this with m=5000 n=20 to fit into n*m <= 10**5
•  » » » » 7 years ago, # ^ |   0 codeforces' server is very fast
•  » » » » 7 years ago, # ^ |   0 Same here, I didn't get it. Wasted 30 min learning how to hack with generated input and trying to understand why it didn't work, and I in the end I just got some negative points.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 I did exactly the same except of thiscout << 2 << ' ' << 2 << ' ' << 2 << endl;I wrotecout << 1 << ' ' << 1 << ' ' << 2 << endl;`But if i remember correctly for k=100000, it gave input data size was too large.So i used k=10000
•  » » » » 7 years ago, # ^ |   0 i choose 2 so that there will be cache problems with array
•  » » » » » 7 years ago, # ^ |   0 How was your input size less than 256bytes for k=100000?
•  » » » » » » 7 years ago, # ^ |   0 You should use generator program for test case for large inputs.
•  » » » » » » 7 years ago, # ^ |   +3 You can write a generator program instead of manual input. That's the second tab of the pop up window after you click the "Hack" button"
•  » » » » » » » 7 years ago, # ^ |   0 Facepalm! I could have hacked atleast 2-3 submissions in my room.
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 I hacked 8 solution in n=5000 k = 100000 case :)
•  » » » 7 years ago, # ^ |   0 In my case it was not accepting n=5000 k=100000 due to large input size!
•  » » » » 7 years ago, # ^ |   0 I used generator. :)
•  » » 7 years ago, # ^ |   +4 Good estimation is 10^9 ops per second (from my experience).
•  » » » 7 years ago, # ^ |   0 for Python also?
•  » » » » 7 years ago, # ^ |   0 No, python is much slower (from my testing 40 times slower) and I don't recommend it as a programming language for contests.10^9 is a good estimation for C++, C# and Java.
 » 7 years ago, # |   +14 noticed my solution for B is wrong after locking it , so hacked 10 people :p
•  » » 7 years ago, # ^ |   0 What's that special test case that failed 10 solutions?? o.O
•  » » » 7 years ago, # ^ |   0 TLE probably. I did an analysis sometime back, and I concluded that codeforces can compute approx 2.7x10^8 trivial instructions(assignment,increment, arithmetic +/-,stuff like) that in 1 sec. Anything more than that is TLE, and if somebody had 10^9 instructions/sec pass then compiler probably optimized something.
 » 7 years ago, # |   0 I wonder what was test 7 for problem D. I really can't figure out what was wrong in my solution... anyway, if A, B, and C all pass, it will still be a good result. :)
•  » » 7 years ago, # ^ |   0 May be something like this:3 3 3-a 2-b 3-a 1-a 2-b 2-a
•  » » » 7 years ago, # ^ |   0 Is the answer 1 ? I guess so...
•  » » » 7 years ago, # ^ |   0 I saw the test. Actually, my implementation of KMP algorithm was wrong. :'(
 » 7 years ago, # |   +9 How to solve C?
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 Let's assume we have instruction 1-n. Everything before that instruction doesn't matter. So let's find the last instruction 1/2 — n. If that doesn't exist the number stays the same, if it does we have to take the smallest or the largest number in the array. After that we search for 1/2 (n-1) that is after our previous instruction and do the same process, but we also have to remember what was the last instruction that was made(if it was 1 or 2 so we know what number do we have to search for). We can sort the instructions and also use the set to get maximum/minimum and to remove elements(after we have used them already) so the complexity is O( (n+m) (log n + log m))
•  » » » 7 years ago, # ^ |   0 What if there are consecutive instructions like for n = 10 1 10 2 9 1 8 2 7 1 6 2 5 1 4 2 3 1 2 1 1 this will sort the array 10 times right?
•  » » » » 7 years ago, # ^ |   0 After the first instruction we know, that result[10] is equal to biggest number in array, and it won't change, after the second one we know that result[9] is equal to smallest number in array without the biggest number — so smallest number, after third we know, that result[8] is equal to the biggest number in array without biggest and smallest number etc, you don't need to sort it every time
•  » » » » » 7 years ago, # ^ |   0 My submission is failing for test case #14 Can you check it? http://codeforces.com/contest/631/submission/16502485
 » 7 years ago, # |   +51 At first I read OR as XOR in A. Anybody else coded for XOR lol
•  » » 7 years ago, # ^ | ← Rev. 2 →   +10 Give me five!) It taken 10 minutes to understand why WA2
•  » » » 7 years ago, # ^ |   +3 I was confident about my code so I immediately went to check the problem statement. Wasted 8 minutes coding for XOR lol.
•  » » » » 7 years ago, # ^ |   +4 I've got sillier case: coded for 1-2 minutes, but couldn't get my mistake for 10 minutes)
•  » » » » 7 years ago, # ^ |   +3 Same here! Although I didn't wasted 8 minutes coding for XOR because then I just changed XOR to OR. I let it be O(n*n) rather than changing to O(n).
•  » » » » » 7 years ago, # ^ |   0 I changed it to O(n) by simply commenting the n^2 code.
•  » » 7 years ago, # ^ |   0 Me too :)
•  » » 7 years ago, # ^ |   0 I did it initially. But soon I could realize when sample test cases didn't pass on my local machine
•  » » 7 years ago, # ^ |   0
•  » » 7 years ago, # ^ |   0 Lol same here. i even submitted the solution with an O(n**2) solution, but luckily it failed in pretest 1 only :P
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 My XOR even passed first five tests. No idea why. I got -50 because of this. :( Here's my solution Link
•  » » » » 7 years ago, # ^ |   0 Ohh, now i recall that what i stated above happened to me on problem 2. The first one gave me ans as 42 with xor which i spotted before submitting. Yours passed pretests 2 too because you are taking max sum of xor of (A[i..j] + B[l..k]) where [i..j] may or may not be equal to [l..k]. It had to be equal according to problem statement.
•  » » 7 years ago, # ^ |   +6 Yes. I even asked an official clarification question so everybody can permanently see in the problem history how dumb I was.Official answer was "There is no XOR. There is only OR. You are a fool."(Part of it was not written but clearly implied).
•  » » » 7 years ago, # ^ |   0 I didn't know this problem history feature until you mentioned it.
•  » » » 7 years ago, # ^ |   +9 What?
•  » » » » 7 years ago, # ^ |   +6 Oh dear I didn't mean to insult the problem setters, I was totally joking!Your message was of course not rude at all. But my question DESERVED a rude reply, that's what my "joke" meant. I sure hope you at least THOUGHT it was a dumb question, because it was. :-)Anyway, I loved the problem set. A and B were perfect difficulty but even after solving them the editorial showed a much better solution for A by thinking a little bit about the data instead of blindly coding, so it was a great lesson. And C was very doable, another excellent learning problem. Thank you!
•  » » 7 years ago, # ^ |   0 Same!
 » 7 years ago, # |   +6 problem A can't hack in n^3
 » 7 years ago, # |   +9 I hope there will be me many TLE on problem A and B after system testing.
•  » » 7 years ago, # ^ |   +5 My hopes are broken(((
 » 7 years ago, # | ← Rev. 3 →   +15 So, maybe authors could comment why they picked so tight input limits on problem B? Basically what I don't like about this — brute-force solution wasn't cut.
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 I too was disappointed. May be n.m <= 100000 should be alright. Why n,m <= 5000?
•  » » 7 years ago, # ^ |   +3 This was done to ensure that the solution should pass on a Python.
 » 7 years ago, # |   +4 very nice problems and I enjoyed... I understood u love optimizing algorithms a lot :)) tanQ guys :)
 » 7 years ago, # |   +8 wanted to act like an expert and went for C first without even looking at A and B. Spent too much time on C and could not submit B :v Looks like my being blue was just a fluke. I am not ready yet :v And , as a result, today I will go back down to my rightful place. How the heck people solve problem like C in 20 minutes -_- . My brain feels dizzy after 1:15 hours of non-stop storming on C :/
•  » » 7 years ago, # ^ |   +6 I don't think it is a good idea to go for C+ right away if you are below like red or something.But it is a good idea after solving first easy tasks (A, B and sometimes C) to read all others.
•  » » » 7 years ago, # ^ |   0 no, I know it takes something special to start right away from D or E. But C is kinda different to me. To solve C, you only need to be proficient in some basic algos. Whereas D and E often requires expertise on some special algos too. (Of course, we have seen exceptions in past contests where C was quite hard too, but i am just expressing the general scenario)
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 I only read C first in rounds which have both div 1 and div 2. For rounds with div 2 only like this, C is usually harder.
•  » » » 7 years ago, # ^ |   +3 Isn't it the other way round?
•  » » » » 7 years ago, # ^ |   0 By "rounds which have both div 1 and div 2" I mean rounds that have 2 separate contests, one for div 1 and the other for div 2 :P
•  » » » 7 years ago, # ^ |   0 so according to you today's C was hard? :v That's kinda good to know. If I heard I had wasted 90 mins to solve an easy problem, it would be devastating
•  » » 7 years ago, # ^ |   0 and after the system test, a lot of people failed on C which I passed. If only my brain worked 1 min faster :/ I just had to submit B (even the code was complete) :/
 » 7 years ago, # |   +19 I thought 5*10^8 operations can be done in 1 sec :(
•  » » 7 years ago, # ^ |   0 The tight input limit is somehow silly, why they didn't make it something like 1<=n, m<= 10^5 ,If they want a better algorithm.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 http://codeforces.com/contest/631/submission/16492693 My solution with 5*10^8 operations passed
 » 7 years ago, # |   0 codeforce i want to say thank you !!!! such a interesting question and help full for improve my coding skills. again thank you.
•  » » 7 years ago, # ^ |   +7 without submitting a solution?
 » 7 years ago, # |   +23 absolutely loved this contest, waiting for the next contest from wilcot and xfce8888
 » 7 years ago, # |   0 Wow i thought i flunked this contest but rank went from 1.8k to 1.3k. I guess my rating will go down by only few points.
 » 7 years ago, # | ← Rev. 2 →   +3 It feels bad when you fail something you spent 1:20 hrs on ;_;Curse of the tourist. Never make fun of tourist ;_;
 » 7 years ago, # |   0 TLE in PyPy (16491742) and AC in Python (16500293) with exact same code. :|Isn't PyPy supposed to be faster? Also, aren't Python/PyPy time limits supposed to be 5x that of default time limits?
•  » » 7 years ago, # ^ |   0 As I know on codeforces time limits are the same for all programming languages.
 » 7 years ago, # |   +3 Oh :-( Overflow... :-(Overflow doesn't allow me to get AC from all of the problems of this contest. :-(
•  » » 7 years ago, # ^ | ← Rev. 2 →   +6 define int long long It's the future.
 » 7 years ago, # |   +1 When will we see the rating change?
•  » » 7 years ago, # ^ |   0 In very short time after the system test. :P
 » 7 years ago, # |   0 Auto comment: topic has been updated by wilcot (previous revision, new revision, compare).
 » 7 years ago, # |   0 Can the Div. 2 D be solved using KMP? My approach was like I would compress multiple characters to single character and form a string. Then I'd use KMP to find the matching between the two. I keep tract of (l, c) pairs. I know their frequency and where they match. With this much information please help me find the answer. My code : http://ideone.com/yb5JCWThanks in advance.
•  » » 7 years ago, # ^ |   0 I did the same, but I got WA7 because I made a mistake when implementing the KMP Algorithm... >< But honestly, I still believe it works. Maybe I should try again now.
•  » » 7 years ago, # ^ |   0 i made a kmp too, searching for a match with the second text without first and last( they can have size smaller than in the first string ) and got WA 9 http://codeforces.com/contest/631/submission/16501632
•  » » 7 years ago, # ^ |   0
 » 7 years ago, # | ← Rev. 2 →   +3 It was a really nice problemset. Thanks!
 » 7 years ago, # |   +9 I think there is a little problem. I solved two problems, you can check it in the standings (465th).
•  » » 7 years ago, # ^ |   0 BUG！
 » 7 years ago, # |   0 10 days without contests?
•  » » 7 years ago, # ^ |   0 New contests could be announced in between.
 » 7 years ago, # |   0 Congratulations..contest was be very interesting. especially the last question is very interesting :) but I can not solve this in contest )
•  » » 7 years ago, # ^ |   +12 Thank you. We tried our best :)
 » 7 years ago, # |   0 How to sort 2d array according to first column? I know how to do it for 2 columns(using pairs) but how to do it when columns are more than 2?
•  » » 7 years ago, # ^ |   0 Creating a custom struct/tuples with custom sort function or pair< int, pair > should work
•  » » 7 years ago, # ^ |   +9 you can use vector of vectors :-)
 » 7 years ago, # |   0 My submission for C is failing for test case #14. Can someone check it? http://codeforces.com/contest/631/submission/16502485
 » 7 years ago, # |   +9 how many operations the codeforces server do in one second? ◉_◉
•  » » 7 years ago, # ^ |   +9 What the hell man? Why did you stole my pic?
•  » » » 7 years ago, # ^ |   +14 I think that you stole my pic
•  » » » » 7 years ago, # ^ |   +14 I think that you both are liers. It's my face on your avatars. Please ban.
»
7 years ago, # |
Rev. 2   -6

anyone on how to solve c? i sorted queries on basis of ri>rj and implemented sorts while skipping ones with ri<r(i-1)&& i<j. some people solved it with segment tress . please explain it?