Hi all!
The second qualification round of Russian Code Cup 2016 will take place on Sunday, May 29, 2016, at 12-00! We invite everyone who has not qualified yet to take part. Those who would not qualify in the second round are invited to take part in the third round on June 5. Good luck to everyone and see you at the round, don't forget to register for the championship at http://russiancodecup.ru if you haven't done so already.
How many contestants in each qualification round advance to the elimination round? I advanced from the first round, can I take part in the second round?
200 from each round
I finished in top 200 in the first round, can I take part in this round?
After I logged in at 12:00 AM, the web site was showing the tasks of the 1nd qualification round to me. I've clicked "2nd qualification round" in the header and started solving. As it turned out later, this had no effect, so I've wasted some time on tasks from the 1st round. Confused and infuriated, I stopped participating in the round.
Please, move previous rounds to some kind of archive so that it would be impossible to mix those up with the current round.
The same for me. Wasted some time solving task A from the 1st qual.
I wasted 50 minutes solving problems from 1st round. So the contest was during 1:10 for me.
Did we have to register before the round to participate in it? I registered just now and can't submit :(
Yes, same thing happened to me in the 1st qualification round.
will there be system testing after contest or the pretests contain everything?
At first, I started reading a problem from the 1-st round too.
And one other issue. I submitted E and was waiting for feedback. I was chatting with someone and he also was refreshing standings. He saw my WA first and told me about it, but for 1-2 more minutes I wasn't able to see it by myself. I tried refreshing (and hard-refreshing using ctrl+F5) the standings and the page with problems (where I can see my own submissions).
The participants are not allowed to communicate with each other or anybody else regarding any topics related to the tasks. http://www.russiancodecup.ru/en/rules/
Poor-poor Errichto is gonna be disqualified...
Shouldn't you hide this for trolling purpose?
If you think like a troll, maybe you are one of them...
Nice one. So, the question is: is my status (AC/WA) related to the tasks? I would say that it is related indeed ;_;
Nice sorting.
How to solve D. T-shirts ?
Bitmask DP , let dp(mask , turn) denote the remaining tshirt if mask is the bitmask of all removed tshirts . answer is dp(0 , 0) (assuming 0 is player 1) . Now in each turn player chooses to remove an existing tshirt such that the result of dp is up in the ranks of that player .
You don't even need to include turn into DP state, because turn = bitCount(mask) % 3.
In fact, no need for the 'turn' register, the number of remaining tshirts determines the current player.
We can get rid of turn because it will always equal n — number of bits in the mask % 3 :P
Well, you exactly know, whose turn is it now, but it doesn't really matter, of course.
It can be done greedy with the same complexity as input reading (and actually for any number of people in the team). Let's consider all turns people do in the reverse order. Then for every turn the guy currently making turn will have to cross out the t-shirt with lowest priority in his chart. This can be proven by induction, but it is quite intuitive in a sense that his teammates can leave this shirt out knowing the last guy will HAVE to cross is out. Putting down the main part of my code to clarify (turn is in reverse order, so as p (priority)):
How to solve B and E. Btw I found C and D much easier than B.
if current element is a '+' choose the largest value to add . if its a '-' , consider 2 cases , if the minimum value is <= our current money , then take that else if all values are > current money , take the largest value and sacrifise that.
Woow I am really stupid. I did the same thing but firstly I wrote a brute force which was slow. So I decided to see if it will not get TL if I change all ints to shorts. So I did it with "#define int short". It got WA. Then I came up with your solution but didn't realize that the sum of the numbers can overflow short ...
Are shorts faster than ints (more than by ~0.01)? It's a serious question, I don't know the answer.
No
Once I solved a problem on Timus archive and submissions with unsigned shorts were a bit faster than submissions with ints. Link to list of submissions (submissions with ints used about 60 Mb memory, with unsigned shorts — about 33 Mb memory).
Maybe when you copy large arrays.
For B: Sort receive request in descending order and sort send request in ascending order. Then process the value. Then maintain balance and increase balance on receiving and decrease if sending is possible.
Problem E. First, we need to find an intersection of two paths. Its endpoints are found among LCAs of 4 points in the input. If it's empty, the answer is NO. Next, there are 2 cases.
If testers go in the same direction, the answer is YES if abs(e0 — e1) < longest edge in the intersection, where e0 and e1 — times of entrance into the first node of the intersection.
If testers go in different directions, we need to check that their time intervals spent at the intersection have a common point and they don't meet in a graph node.
Everything above can be implemented using binary ascent.
I really can't believe I wrote this code on E without any single bugs, compiled in first time, and got accepted in first time. (I got one WA but I submitted incomplete code for to check my code)
https://ideone.com/bEGBmq
can you explain your logic?
Divide paths two pieces, going up and going down, and check all 4 pairs. When checking one pair,
If they're going same way and if there will be collision, there will be collision on the longest common edge, too. So we can simply check longest common edge.
If they're not going same way, there can be at most one collision, find where it is. If it's on a node, there won't be collision, if it's on edge, there will be collision.
EDIT: By "collision", I mean "both testers were going along that bridge during some non-zero time interval"
I don't get why you "submitted incomplete code for to check your code". What did you expect? You don't know the order of tests so you still can't be sure after getting e.g. TLE (if you were afraid about WA/RTE).
I couldn't believe that I can solve it, there are just 5 minutes, penalty won't be matter, and I'm sure there have to be some bugs so I submitted without checking "collision on node or on edge". Then I submitted it, I realised it's easy to check it, added it to my code and submit again, got accepted. And I got WA on test 5 at first attempt, so I was pretty sure it's because of "collision on node or edge". BTW it's so stupid to do that.
This contest in Gym: 2016 Russian Code Cup (RCC 16), 2nd qualification round.
Ghosts are from 1st qual.
Thanks
, I'll fix it ASAPfixed!How to sort an array of ints (not Integers) in descending order in Java?
I sorted it and reversed then.
First time for me — getting AC on the first attempt at Andrew Stankevich organized contest. All previous ones were 3-4 tries at best :)
A went in smooth, B smooth. On C I stumbled — I've got the idea about largest difficult string being 14 letters long. But I still hesitated thinking that 1000 testcases of the same 14 letters long "AAAAAAAAAAAAAA" might be too much for brute force. It wasn't, but I lost lots of time trying to come up with some suffix array / trie / or something else based solution. Stupid of me. With 5 minutes left I read Problem D and it was the easiest problem of the round (in my perception because I like this type of problems). Again I had great opportunity to qualify and missed it (287 place). This is my ... 9th qualification round in RCC, usually placed between 201 and 300 :)
In my local time this contest was at 4:00 am and I went to sleep around 0:00 after re-watching last weeks episode of Game of Thrones :)
When you have a string of length = 15, and K = 5, you have about 15*14*13*12 decompositions, and for 1000 test cases about 33 * 1e6 operations, so it's ≈ 30 times less than 1 sec (≈ 1e9 operations)
That doesn't matter, but your value ( 15 * 14 * 13 * 12 ) is far from true number.
The actual value is which is 1001. ( 32 times smaller than your value)