Hello Everyone,
The problem set of 2016 ACM Amman Collegiate Programming Contest will be available in Codeforces Gym on Tuesday, Sep/27/2016 10:00.
The problem set was prepared by Hasan0540, SaMer, and AU.Bahosain.
Thanks to RetiredAmrMahmoud for testing one of the problems (in case he participated), and to Dark for helping me preparing the contest on Polygon.
I hope more orange and red coders will participate than in the last contest I've prepared :(
Good luck!
why we can not see the solution of another users after the contest ? :)
You can only view submissions for the problems you solved in the Gym.
problem was good.. plz upload the editorial :)
The editorial will be available in 10 days as we're busy preparing for another contest.
reminder: 3 months passed
Reminder: 4 years passed
Thanks for the reminder! The tutorial for 8 of the problems was written 4 years ago: https://codeforces.net/blog/entry/49515, so I guess I'll just post those for now.
OK, where is the editorial?
When will the editorial be uploaded ?
Can anyone help with solution for problem I and L?
for problem I you need to notice that the x coordinate and y coordinate of the optimal starting position are chosen independently cuz moving the robot start position horizontally never change how the robot can go out of the bounds vertically and vice versa/
Now to choose the optimal y pos for the robot you can notice that if you place the robot too high it can go out of the table from above and if you place it too low it can go out of the table from the bottom so the optimal is something in the middle so you can run ternary search and find the optimal y pos and you can do the same thing to find the optimal x pos too.
I have noticed that we have to solve independently for X and Y, but didn't know how to find optimal answer for each axis. Thank you! :)
Ternary search somehow passed the testcases. But using ternary here may be wrong. For x-coordinate, let f(x) be the number of skips, then f(x) isn't convex. Sometimes you go to the right, you get more steps to skip on the right, but you will save more steps which was skipped on the left.
Note for problem I (Simple Robot):
it can be solved without ternary search and in a much faster way.
you can assume at the beginning that the optimal position is at point (0,0) (top left of the room). and then start executing the instructions sequentially.
let's talk about what could happen horizontally, if the next instruction you will skip is in < direction, you will consider changing the optimal x position by incrementing it by 1, but to do this you have to make sure of 2 things : that the current assumed optimal x position didn't reach the most right, and that the maximum right position you got to while executing the instructions is not the most right position, for the second condition you must keep track of the most right position you reached, and after incrementing the assumed optimal x position you have to increment the most right position you reached too. therefore this instruction that was to be skipped will not be skipped because you assumed starting at more right position.
but if the next instruction you will skip is either in:
1) > direction
2) < direction (and the current assumed optimal x position reached the most right, or the maximum right position you got to is the most right position)
then at this point the optimal x position doesn't need to be changed anymore and any instructions to be skipped starting from here (including the current instruction) will be skipped actually, so you count them and these will be the minimum horizontally.
for the vertical aspect you can think in the same way. (I solved it this way and it got accepted with time 109 ms.)
I'd like to remind you to write the editorial :)
why i got MLE in test 2 , and what you think the test is?
101102K - Topological Sort
23365501
may someone post tricky test cases and their expected output for problem G Notes ?
Can anyone tell me how to solve problem D?
I can't find any editor of problem K. Can anyone help with solution for problem K, why I got TLE? this my code
In lines 18, 19 you are doing N^2 iterations.
I used dfs on the complement graph to generate the topological sort. same idea from this problem Almost everyone used a solution based on lazy segment Tree.
Can you please explain your approach a bit more. I have been working on it for long and couldn't get any. I have even written a blog on it and yet none replied. I would be very thankful to you if you explain the solution. Link to my blog asking for some hint
A simple dfs can find the topological sort graph in a DAG. you can read this
But now how to stimulate this on the complementary graph?
The idea is to keep a set of unvisited nodes each time we visit a node we erase it from the set.
and we will find the next node and call dfs(next) in this problem, the next node must hold the condition (next > cur_node) and there is no edge from cur_node to next in the list of erased edges. We can check this by a set too.
I invite you to read the editorial of this porblem. It explains why this works on time.
I think this is the intended solution. We can stimulate the Khan's algorithm for topological sorting on the complementary graph with Lazy propagation segment Tree.
Everyone helps me problem D, pls.