By Gerald, 8 years ago, translation,

Good day, Codeforces!

Today at 19:00 the Round 1 of the Open Moscow Programming Championship By CROC will start.

This is usual two-hour Codeforces round with hacks and decreasing values of problems. Everybody, who passed Qualification Round and registered for today’s round, has advanced to Round 1. The remain participants are allowed to participate in this Round out of competition. Round will be rated for everyone as usual. Contestants who gain a score equal to the 300-th place finisher score or greater will advance to the Round 2 (also you need to gain positive score).

You will find a few problems, roughly ordered by the increasing complexity. Score distribution is standard (500-1000-1500-2000-2500). During the Round the problems are judged only on pretests and system testing will take place after the end of the Round. The pretests do not cover all possible cases of input data, test your programs carefully!

Before the end of the round it is strictly forbidden to publish the problem statements/solutions/any thoughts and ideas about them elsewhere. It is forbidden to talk about the problems, discuss the statements and so on. Be honest and let the best men make it into Round 2. When the Round is over, you can discuss the problems and solutions.

It seems that this Round could be a bit hard for Div2 participants. Don’t forget that rating will be calculated only for participants, who make at least one submit.

In today’s round preparation take part: Ripatti, havaliza, HamedSaleh, RAD, Gerald, MikeMirzayanov, Delinur. A huge thank you to all of them for their work!

Good round to everybody!

Announcement of Croc Champ 2012 - Round 1

• +181

 » 8 years ago, # |   +1 Admin plz look in to it. I received a mail that I qualified for round 1 and I also registered for round 1 as usual but now I am trying to submit solutions but it gives me access denied what is the problem admin plz look into it asap.
•  » » 8 years ago, # ^ |   +1 I am too receiving the same problem ...
•  » » 8 years ago, # ^ | ← Rev. 2 →   +9 Now I had "access denied" too, but using the "Submit" tab (rather than submitting from problem page) helped.
•  » » 8 years ago, # ^ |   +1 Same here!
 » 8 years ago, # | ← Rev. 2 →   +12 The problems were quite tricky. I've hacked someone at every problem I've solved (A,B,C) :-)
•  » » 8 years ago, # ^ |   -6 what kind of tests?
•  » » » 8 years ago, # ^ |   +26 ...the largest possible!
•  » » 8 years ago, # ^ |   0 What's the corner case for A? I saw a lot of hacking.
•  » » 8 years ago, # ^ |   +22 I don't tnink it shows that problems are tricky. Just somebody can't understand that naive algos are slow enough.
 » 8 years ago, # |   +8 I will comeback next time！
•  » » 8 years ago, # ^ |   +2 me too :)
•  » » » 8 years ago, # ^ |   -7 Nice to meet you！
 » 8 years ago, # |   0 Is there going to be any wild card round like we saw in VK cup??
•  » » 8 years ago, # ^ | ← Rev. 2 →   +12 Have you read the Announcement?
•  » » » 8 years ago, # ^ |   +3 ya... no mention about any wildcard round... but was still hoping :)
•  » » » » 8 years ago, # ^ |   +19 No mention = no round
 » 8 years ago, # |   -9 For problem B, if using DFS, what's the time and space complexity?
•  » » 8 years ago, # ^ |   +8 Can you explain how do you find shortest path with dfs?
•  » » » 8 years ago, # ^ |   +6 You would need to include the distance in the state. This makes the time and space complexity quite large for this problem, but I guess that if in another problem, you really wanted to do it, you can do it.
•  » » » » 8 years ago, # ^ | ← Rev. 2 →   +3 For this problem, I guess the risk is not high time complexity but stack overflow?If someone thought it can be solved by DFS, please let me know.
•  » » » » » 8 years ago, # ^ |   0 It is both, I think the maximum result for the distance is around 2000 , so 2000*1000*1000 sounds slow even if you deal with the stack overflow.
•  » » » » » » 8 years ago, # ^ | ← Rev. 2 →   0 How did you get 2000*1000*1000? What's about BFS when the result is 2000?
•  » » » » » » » 8 years ago, # ^ |   +3 Talking about DFS, and since you need to include the distance in the state, and the maximum distance is 2000, and there are 1000x1000 cells, then a very sloppy estimation is 2000*1000*1000 (I bet it is much smaller with cropping, but still).In BFS (Actually a Dijkstra variation), the distance is not part of the state, so this is not a problem.
•  » » » » » » » » 8 years ago, # ^ |   +3 Let the function prototype be dfs(x,y,dist,dir). The stop condition of the recurrence is x == n-1 or y == m-1. So param dist is not a decisive factor of time complexity but only stack usage.
•  » » » » » » » » » 8 years ago, # ^ |   0 In a DFS, You can visit different (x,y,dir)s with different distance values.
•  » » » » » » » » » 8 years ago, # ^ | ← Rev. 5 →   0 That's right. But I still thought 2000*1000*1000 is a wrong way to estimate although I agree DFS might be slow. I will try to implement a DFS version which passed systest or failed due to TLE. We may discuss further via private messages then. Thanks.
•  » » 8 years ago, # ^ |   -18 For problem B, unsuccessful solution was Dijkstra with O(n^2 + m). On 1000 1000 with all #: n = 10^6, m = 2 * 10^9. 2 * 10^9 + 10^6 is TL.DFS was even a more stupid idea, i think.
•  » » » 8 years ago, # ^ |   +5 Depends on how you build graph
•  » » » » 8 years ago, # ^ |   -10 Yes, but I wrote this to show the solution which passes pre-tests, but is not correct
•  » » » » » 8 years ago, # ^ |   0 you can make every point in a number. It only cost 20 long long to represent a line. so the build graph time is O(n*m*20)
 » 8 years ago, # | ← Rev. 3 →   0 Is the result of the last query in the sample case of Problem E right?n = 5, k = 1, r's and a's are given as (1 5 4 1 2) and (4 4 3 2 2), respectively, and the last query asks if the 1st and the 4th members can be together in a group. But their age difference is 2, which exceed k(= 1), so they cannot be in the same group.My misunderstanding or what?
•  » » 8 years ago, # ^ |   0 Condition on ages doesn't look like "no 2 members have ages with difference greater than k", but like "each age of the member of the group should have difference no greater than k with group leader".
•  » » » 8 years ago, # ^ |   0 I see, but the problem also requires that one of the two members given in the query be the leader, doesn't it?
•  » » » » 8 years ago, # ^ |   0 "It's possible for x or y to be the group leader.", not required.
•  » » » » » 8 years ago, # ^ |   0 Wow, I was completely mistaken. That part must be what makes the problem the most difficult one! Thank you.
 » 8 years ago, # |   +23 Overly long explanations for Problems A, B and CI liked this contest, wish I didn't fail so much in problem A so I could have tried D.
•  » » 8 years ago, # ^ |   0 nice blog :)
•  » » 8 years ago, # ^ | ← Rev. 2 →   +8 One cute way of solving C without using the "shape" array is to define a spiral of size 1 as simply a single square. The recurrence then follows quite naturally for larger spirals.
 » 8 years ago, # |   -7 I don't remember when I was so lucky as in this contest, watching the system test was too exciting... (I fell to place 300)
 » 8 years ago, # |   +28 why there is no practice after the contest? and the problems are not available in problemset also.
 » 8 years ago, # |   +7 Why is Dijsktra for B too slow? 1000 * 1000 * lg(1000000) * 4 = 80 million, which should be doable in 2 seconds. Unless the server is very slow today ... :(
•  » » 8 years ago, # ^ |   -19 True story
•  » » 8 years ago, # ^ |   +13 It's kind of pointless to use Dijkstra when your graph only contains edges of weight 1. ;)
•  » » » 8 years ago, # ^ |   0 0 and 1.But BFS is enough, throught
•  » » » » 8 years ago, # ^ |   +5 BFS when weights are 0 or 1 is Dijkstra, just optimized for such low edge weights.
•  » » » » » 8 years ago, # ^ | ← Rev. 3 →   +21 Use deque and it's still BFS.
•  » » » » » » 8 years ago, # ^ |   +23 Yes. Boundaries between these algorithms are not so crispy. A BFS when weights are 0 or 1 is both a BFS and Dijkstra :)Even with normal BFS using a single queue, if you use it to find the shortest path, you are applying Dijkstra's idea. The original Dijkstra algorithm didn't use a heap. It was just the concept to expand the current shortest path first. When you do a BFS to calculate the minimum path, you do exactly that. Specially if you use a deque, you are no longer just doing a search, you are already following the same algo but with a deque instead of a heap.So, Dijkstra works in this algorithm, just use a Deque instead of a heap.
•  » » » » » » » 8 years ago, # ^ |   0 Can you please share how you use to a deque to make it work?
•  » » » » » » » » 8 years ago, # ^ |   +9 Some edges have cost 0 and some edges have cost 1.Normally, you have a queue and push all edges to the back of the queue.If you have a deque, you can push edges that do not increase the current distance (edges of cost 0) to the front of the deque. And edges that increase the distance, cost 1 to the back of the deque. Afterwards, it is the same as a BFS.It works because it guarantees the node with the shortest distance is always at the front of the deque.
•  » » 8 years ago, # ^ |   0 There was no need to write Dijkstra, especially with heap. Didn't you think about any simpler solution?
•  » » 8 years ago, # ^ | ← Rev. 3 →   0 The complexity of Dijkstra with a heap is O( log(|V|) x (|V| + |E|) ) I think that the usual Dijkstra solution has |E| around 4x4x1000x1000 and |V|=4x1000x1000 (There is a node for each pair between each cell and each of the 4 directions. And for each of those nodes, there are 4 edges towards other nodes in case the cell it is a column). Your complexity estimation seems to be |V|x log(number of cells), quite smaller. O( log(|V|) x (|V| + |E|) ) is 5 times larger and yields 9 digits.
•  » » » 8 years ago, # ^ |   0 I see, I missed out the number of edges. So I need around 400 million operations in the worst case.Still, that is on the order of 100 million operations, so it should pass? =D
•  » » » » 8 years ago, # ^ |   0 Set has a high constant (as compared to others algo like bfs..), so it would not pass
 » 8 years ago, # |   0 Thanks for the great contest . There was lots of div 2 participants in the contest so please prepare more problems for div 2 like the VK 2 contest .
 » 8 years ago, # |   +40 I got about +10 hacks in A by using this case 2000000000 R R These hacks saved my score after failing A and B. I was so lucky. Nice contest, by the way! :)
 » 8 years ago, # |   +21 +0 rating change. This is the second time it happened to me!
•  » » 8 years ago, # ^ | ← Rev. 2 →   +3 +0? You're an optimist;) I have simply 0, without plus..)
 » 8 years ago, # |   0 Can someonw tell me whats wrong in the submission(for Prob B)..Solution...
 » 8 years ago, # |   0 There's inconsistency in final standings and rank in member's profiles, take Petr for example, he finished 3rd, but on his profile page the graph shows Rank: 4
•  » » 8 years ago, # ^ |   +7 There is one unofficial participant above Petr
•  » » » 8 years ago, # ^ |   0 thanks for reply, I think usually official rank is displayed
•  » » » » 8 years ago, # ^ |   +10 Rank shown in profile should be the rank used to calculate rating, which includes unofficial participants in this contest
 » 8 years ago, # |   0 Please can someone point out the error in my solution of Problem B.
 » 8 years ago, # |   0 Since the editorial doesn't seem to be coming, could someone share the ideas of their solutions to D and E?
•  » » 8 years ago, # ^ |   +8 You can try to get something from the editorial in russian.
•  » » » 8 years ago, # ^ |   0 I didn't see that, thanks.
•  » » 8 years ago, # ^ |   +5 It looks like the author has been translating the editorial as we speak. It's now ready in English too: http://codeforces.com/blog/entry/4289