### Ripatti's blog

By Ripatti, 10 years ago, translation,

Hello everyone!

I am an author of problems of today round. This round is for both divisions. There will be 7 problems, the first 5 of them are for the second division and the last 5 are for the first one.

About points of problems. Today they are nonstandard:
for div2: 500-1000-1500-2000-2000
for div1: 500-1000-1000-1500-2500
Be careful.

RAD helped me for preparing the round. Delinur translated statements into English.

Good luck ans have fun.

UPD.
winners of the first division
1. peter50216
2. tourist
3. ACRush

winners of the second division
1. iamcs1983
2. zyx3d
3. seanwupi

Editorial.

UPD.
Unfortunately, in author's solution of priblem E some bug was found. We thanks participant LinesPrower for detection of it. Author's solution was updated and all solutions were rejudjed. Ratings will be recalculated for all participants excluding Egor and Jacob. We apologize for this incident.

• +187

 10 years ago, # |   +14 CF #59(Div2) , CF #65(Div2) , CF #68 , CF #70(Div2) and now CF #74Very Nice : Surely will have a good contest :D
 10 years ago, # |   +6 good luck every one
 10 years ago, # |   -8 It was nice contest.... i wanna know a few things as m a newbie...1. What are hacks????2. Is there any penalty for incorrect submissions3. On what basis points are allocated to user who has correctly solved the problem!!
•  10 years ago, # ^ |   +1 you can(and should) read itToday standart points for problems some unusauldiv2: 500-1000-1500-2000-2000div1: 500-1000-1000-1500-2500
•  10 years ago, # ^ | ← Rev. 2 →   0 ... I found that  submissions that didn't pass the pretest ..will not cost penalty ... ;) . This is really helpful ..PS: .. The version of the Ruby compiler isn't clearly ... ... .. which induce me lots of CE && RE submissions more than once .. Maybe the version is 1.9.0 or higher .. cause the String::[] is return a char ...     ... And one more suggestion ... there should be one more language option named .. "Auto" .. ;) .. literal meaning .. auto-distinguish the language according to your suffix name ... ..simply "cpp" stands for GNU CPP .. "pas" stands for "Free Pascall / Delphi "...  which could also be some user-preset perhaps ..
 10 years ago, # | ← Rev. 3 →   +31 E/Div2 At the first time i read the statement , I thought n,m<=5000 ,so i have to look for a O(N*M) solution and It 's really hard to solve , why so many people accepted ? I can only solve it in O((N*M)^2) .  It takes me 50 minutes to notice that n*m<=5000 , it's 1:53:00 , too late . My rating continues to decreases :( . this is the fourth consecutive time
•  10 years ago, # ^ |   0 Argh, I just noticed it now that you mentioned it :S
•  10 years ago, # ^ |   0 wow. didn't notice that. i thought it was n,m <= 5000 too...
•  10 years ago, # ^ |   0 Woah! I didn't notice it either x-(
 10 years ago, # |   0 Hi, I was encounter something strange.In the problem C, I was received two same hacking.I was success defense at the first one, but the second one I got TLE.Is this situation regular?Actually, I can't 100% sure that two hacking are the same.Since I can only see a part of the input：######1 5000 RRRRRRRRRRRR....######But I guess they are same.Thanks.
•  10 years ago, # ^ |   +4 1 5000RRR...RRLLL...L (half of 'R', half of 'L')I think this one makes you TLE.Some brute force algorithm is O(N^3) on it.
•  10 years ago, # ^ |   0 thanks for your reply :)
•  10 years ago, # ^ |   0 How could you see the input used to hack your code?I tried to see the input used to hack my problem A viewing my codeat "my submissions" and by double-clicking the score/points of problem A at the "room" area. But in both cases I just saw the pretest cases, it didn't show the hack input.Thanks.
•  10 years ago, # ^ |   +22 Go to the "HACKS" page.For example, the previous contest's: http://www.codeforces.com/contest/89/hacksClick the "Verdict" column of the corresponding submission you want to see.And you will see the hacking input.
 10 years ago, # |   -6 How can my solution fail for 1 5000 R* when on my local machine it runs in 0.4 secs. Is that CF judge that slow? I thought the complexity of the solution would be R*C ^ 2, with a dfs for every node atleast for that case.
•  10 years ago, # ^ |   0 Thanks cgy4ever.
•  10 years ago, # ^ |   0 try RRR ... LLL (2500 both)
 10 years ago, # |   +1 why I can't see rating graph in my profile page ?
•  10 years ago, # ^ |   0 Some features are temporary unavailable during the contest. Will be restored soon.
 10 years ago, # |   0 it's for all!i think for increase speed of process!
 10 years ago, # |   0 Where are the editorials for this contest??????
 10 years ago, # |   +5 What time analysis will be up???
•  10 years ago, # ^ |   0 tomorrow
 10 years ago, # |   +33 During the contest(hack), the window to view codes was too small and I could not see the entire code when the code contained a long line. The view sometimes collapsed.I hope the UI of current hack window will be improved.
 10 years ago, # | ← Rev. 4 →   0 My solution doesn't produce any output. I submitted many times during the contest. What is wrong with this solution. It works fine in Ide one and locally too.Link.http://www.ideone.com/BcunL.Edit: During the contest my submission ids were:492767492737492505492349492236492131492074492035After contest: 494437494398494274494260494238 494173494293
•  10 years ago, # ^ | ← Rev. 2 →   0 You need System.out.flush() in the endouups, nevermind, you have close
•  10 years ago, # ^ | ← Rev. 3 →   0 System.out.println(res.toString())Edit: The problem with your template in nextLine() try simple main and it will pass.
•  10 years ago, # ^ | ← Rev. 2 →   0 No it does not help. But it works locally and in Ideone. Have you tested it on your system ?
•  10 years ago, # ^ |   0 Yes, I try your solution and it is accepted,check it now.
•  10 years ago, # ^ |   0 Could you paste it in IdeOne ? But what exactly is wrong is what I would like to know. It worked under my system, IdeOne. But why didn't it work in codeforces ?
•  10 years ago, # ^ |   0 http://www.ideone.com/6ESAGI just replace your main with another tested main with the same code in your method solve() and it runs smoothly !! I recommend test your main template before use.
•  10 years ago, # ^ |   0 Thank you. I submitted it and it was accepted.But did it work under your system? I have been using my template for a while now and never had problems. Submitting it many times and getting a wrong answer on Pretest 1 is a bit frustrating. Could you post your observations on what could have gone wrong. .
•  10 years ago, # ^ |   0 I can't recognize the problem in your template, so what about change your template you can try this one It is the same of your template with small changes I remember i took it from Egor
•  10 years ago, # ^ | ← Rev. 2 →   0 But did it run in your system ? My template is similar to Egor's. I will go through it.Edit: Oops, I meant whether my solution ran in your system.
•  10 years ago, # ^ |   0 Yes, Egor's template runs smoothly
•  10 years ago, # ^ |   0 Codeforces's input for the Pretest 1 contains 2 newlines in the end. Where was this mentioned ?http://en.webhex.net/view/c8002611d83e594863797cee7fc5e3c6
•  10 years ago, # ^ |   0 your solution throws RTE exception when taking the newLine it tooks the two Integers but the problem come in nextLine() it reads emptylines
•  10 years ago, # ^ |   0 Thanks for all your effort. After carefully going through Egor's Template, I corrected 2 bugs, both related to reading empty lines.
 10 years ago, # |   0 why my rating doe'snt update?
•  10 years ago, # ^ |   0 same
 10 years ago, # |   0 Hi everyone.C\DIV 2.can anybody explain me why the answer is 0 for the test case like this5 2 94944125484 254 1838 18184 9421
•  10 years ago, # ^ |   +1 Because he can move diamonds only two times between two checks. But he should do at least three operations to steal a diamond.
•  10 years ago, # ^ | ← Rev. 2 →   0 Why does he need to do at least 3 operations? Why can't he move one diamond from 5484 to 254, and then take one from the 1838 for a total of 2 operations and resulting in 5483 255 1837Nevermind, that would change the sums on the later parts of the array. Sorry for the confusion.
•  10 years ago, # ^ |   0 After this operations we have5483 255 1837 18184 9421But it's easy to notice that 1837+18184 is not equal to 1838+18184.
•  10 years ago, # ^ | ← Rev. 3 →   0 Sum 1838+18184 will differ from 1837+18184.
 10 years ago, # |   +8 Good Questions.Specially div2 E.Every -one got tricked very badly.1.Few got tricked that they did not notice n*m <= 5000.2.Few got tricked that, after noticing n*m <= 5000 , they just thought...WoW!!!  5000*5000  will pass,so easy ,  hahaha, I can write this(Didn't Even think for a single minute that this cannot pass, even after having 1 hr at hand.)That was me .   Kill me !!  :(---------------------------------------P.S : Now I notice , it was required to make a graph and re-assignments of left,right,up,down .
•  10 years ago, # ^ | ← Rev. 2 →   0 I have read the answer to this problem above, thanks.
 10 years ago, # |   +5 For problem C:The brute force algorithm has O(N^3) time complexity for some data.Some people use it and get a due TLE.But when I hacked masha_and_beer's code using the data: RR...RRLL..LLIt returns that his code runs about 1000ms and get the correct answer.I think his ideal is just the simulation without any optimization.And I copy his code and run it for the data I hacked him, it runs about 23 sec in my MacBook.But I run it code using Custom Test, it runs in 1sec.Can anyone explain why his magic code runs so fast on the judgement and can Pass? Thanks.
•  10 years ago, # ^ | ← Rev. 3 →   +5 move[dir][opy][opx].x = px;move[dir][opy][opx].y = py;The code is not pure simulation. It does remember something :D(edit: I can't use this editor correctly...)
 10 years ago, # |   0 Thank you, I understand now.I think his ideal is something like Path compression, which I also used to solve this problem.But my approach is union-find sets.
•  10 years ago, # ^ |   0 So, why did it ran for 23 secs on your Mac  And  1000 ms here?Please throw some light.
•  10 years ago, # ^ |   0 Oh, I did't really know why now.I run his code in XCode on the MacOS, it only cost 4 sec.But in Dev-Cpp on WinXP it cost more than 20sec.Can anyone explain it?It happens not once, I noticed that before this time.All the time it happens the code use vector, map or some others in STL.
•  10 years ago, # ^ |   +8 Looks like you compile without optimizations (-O2).
•  10 years ago, # ^ |   0 Oh my god, you are right.I add this optimization and runs in about 1sec.Thank you very much, I had troubled with this several times.
 10 years ago, # |   +2 Can any one tell me where is the editional?
•  10 years ago, # ^ |   +1 it's not prepare , yet!
 10 years ago, # |   0 Lesson: Try to learn all aspects of C++ STL then use themDuring the contest I used a O((R*C)^2 log (R*C)) algorithm for problem C which I thought that would work but surprisingly it got TLE. when I debugged my code after the contest, I found out that copying the "map"s takes too much time...
 10 years ago, # |   -15 peter50216 - это Митричев чтоли? :)
•  10 years ago, # ^ |   +30 Это его китайская копия =)
 10 years ago, # |   0 Chip Play  For every point, starting from it dfs a time to find the length ,whether the complexity is O ((n * m ^ 2)?
•  10 years ago, # ^ |   0 note to this test:1 5000RR..R(2500)LL..L(2500)for this test case, the complexity is O(n3).you can use linked-list for AC , for each cell which has chip, consider four pointer.
•  10 years ago, # ^ |   0  thank you!
 10 years ago, # |   0 When will the editorial will appear?
 10 years ago, # |   0 Can I hack someone's submission  after the contest? If so, and  how? thx for explanation!
•  10 years ago, # ^ |   0 You can only hack someone's submission during the contest.
•  10 years ago, # ^ |   0 Thx a lot!
•  10 years ago, # ^ |   0 Whose solution you wanted to hack :P
•  10 years ago, # ^ |   0 None by now, I just wonder it.
 10 years ago, # |   0 could someone please tell why the loop in the solution of "Problem C - Robbery" has i+=2 , shouldnt it be i++. Why are we ignoring the even numbered terms . I mean why are we considering 0,2,4,6..... and ignoring 1,3,5,7 indexed terms. ???
•  10 years ago, # ^ | ← Rev. 2 →   0 Because there is only one way to steal the diamond: inc all odd cells and dec all even cells.How long can it continue? Of course, min(all(a[i])) where i is even
•  10 years ago, # ^ |   0 Because there's only 1 way of moving diamonds so that Joe can get more diamonds. Consider: a[0], a[1], a[2] ... a[n-1]. Sums are (a[0]+a[1]), (a[1]+a[2]), ... , (a[n-2]+a[n-1]). (n-1) sums mustn't change, and their sum mustn't, either. We can see that a[0] and a[n-1] are counted once, while the others are counted twice. Therefore, if Joe want to get 1 more diamond, he will move 1 diamond from a[0] (or a[n-1])  to the middle, so it will be counted once more, and move 1 diamond from a[n-1] (or a[0]) to his pocket. This is how Joe should move diamonds: Move 1 diamond from a[0] to a[1] -> (a[0]+a[1]) won't change, but (a[1]+a[2]) will increase by 1. So Joe doesn't need to move from a[1], but a[2] to a[3]. And so on ... 0->1 , 2->3 , 4->5, ... , (n-1) -> Joe's pocket. Joe can get more diamonds unless 1 number in a[0],a[2],a[4],...,a[n-1] = 0.
•  10 years ago, # ^ |   0 Wow! Didnt think it that far :(. Thanks for the wonderful explanation. I got it now ....:)
•  10 years ago, # ^ |   0 Where are the solution to the Problems??? plzz reply m a newbie...
•  10 years ago, # ^ |   0 You can read short editorial here.
•  10 years ago, # ^ |   0 Thanks!!But how do we come to know where are the links for the editorials after the contest ends??
•  10 years ago, # ^ |   0 generally the blog entry that announces the contest, posts the link. Like in this case , when the editorial come up . Its link will be provided at the place where it says Editorials will be up tomorrow.if you cant wait then, keep checking the recent actions column on the home page, something related to the contest will show up.Rest do check the bloghttp://codeforces.com/blog/entry/1492Hopefully it will be updated there. :)Have fun learning !!!
 10 years ago, # |   +1 I solved 90C Robbery in div2 only contest, but the time the number of problems I solved in the problemset increased by 1 was when I sovled the same problem(89A Robbery) in div1 contest for practice.Could you make the system to where when I get AC the number of problems I solved in the problemset increase by 1 regardless of where I solve it?
 10 years ago, # |   +6 The top 3 contestants are now the same as in TC:) Things will converge in the last.Of course, this peter is awesome too... He reminds me of what Petr did in TC when he first entered the website years ago.GL, HR & HF Everyone!
•  10 years ago, # ^ | ← Rev. 2 →   0 peter50216 won the div2 of Topcoder too a day before his first codeforces round. sorry: he didn't actually won, i should have checked before posting..
•  10 years ago, # ^ | ← Rev. 2 →   0 whats the handle of peter50216 in tc? he've beaten tourist in his first cf contest in div1,thats amazing.Edit: http://www.topcoder.com/tc?module=MemberProfile&cr=22929522 Thats his handle,participated in only one srm.