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, haas, RAD, Gerald, MikeMirzayanov, Delinur. A huge thank you to all of them for their work!
Good round to everybody!
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.
I am too receiving the same problem ...
Now I had "access denied" too, but using the "Submit" tab (rather than submitting from problem page) helped.
The problems were quite tricky. I've hacked someone at every problem I've solved (A,B,C) :-)
what kind of tests?
...the largest possible!
What's the corner case for A? I saw a lot of hacking.
I don't tnink it shows that problems are tricky. Just somebody can't understand that naive algos are slow enough.
I will comeback next time！
me too :)
Is there going to be any wild card round like we saw in VK cup??
Have you read the Announcement?
ya... no mention about any wildcard round... but was still hoping :)
No mention = no round
For problem B, if using DFS, what's the time and space complexity?
Can you explain how do you find shortest path with dfs?
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.
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.
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.
How did you get 2000*1000*1000? What's about BFS when the result is 2000?
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.
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.
In a DFS, You can visit different (x,y,dir)s with different distance values.
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.
For problem B, unsuccessful solution was Dijkstra with O(n^2 + m). On
1000 1000with all
n = 10^6,
m = 2 * 10^9.
2 * 10^9 + 10^6is TL.
DFS was even a more stupid idea, i think.
Depends on how you build graph
Yes, but I wrote this to show the solution which passes pre-tests, but is not correct
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)
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?
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".
I see, but the problem also requires that one of the two members given in the query be the leader, doesn't it?
"It's possible for x or y to be the group leader.", not required.
Overly long explanations for Problems A, B and C
I liked this contest, wish I didn't fail so much in problem A so I could have tried D.
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.
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)
why there is no practice after the contest? and the problems are not available in problemset also.
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 ... :(
It's kind of pointless to use Dijkstra when your graph only contains edges of weight 1. ;)
0 and 1.
But BFS is enough, throught
BFS when weights are 0 or 1 is Dijkstra, just optimized for such low edge weights.
Use deque and it's still BFS.
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.
Can you please share how you use to a deque to make it work?
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.
There was no need to write Dijkstra, especially with heap. Didn't you think about any simpler solution?
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.
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
Set has a high constant (as compared to others algo like bfs..), so it would not pass
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 .
I got about +10 hacks in A by using this case
These hacks saved my score after failing A and B. I was so lucky. Nice contest, by the way! :)
+0 rating change. This is the second time it happened to me!
+0? You're an optimist;) I have simply 0, without plus..)
Can someonw tell me whats wrong in the submission(for Prob B)..Solution...
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
There is one unofficial participant above Petr
thanks for reply, I think usually official rank is displayed
Rank shown in profile should be the rank used to calculate rating, which includes unofficial participants in this contest
Since the editorial doesn't seem to be coming, could someone share the ideas of their solutions to D and E?
You can try to get something from the editorial in russian.
I didn't see that, thanks.
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