Russian Code Cup — Second Qualification Round
By RussianCodeCup, history, 9 years ago, translation, In English

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.

  • Vote: I like it
  • +36
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
9 years ago, # |
  Vote: I like it +96 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +39 Vote: I do not like it

    The same for me. Wasted some time solving task A from the 1st qual.

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    I wasted 50 minutes solving problems from 1st round. So the contest was during 1:10 for me.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Did we have to register before the round to participate in it? I registered just now and can't submit :(

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, same thing happened to me in the 1st qualification round.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

will there be system testing after contest or the pretests contain everything?

→ Reply
»
9 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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).

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +108 Vote: I do not like it

    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...

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      Shouldn't you hide this for trolling purpose?

      regarding any topics related to the tasks

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        If you think like a troll, maybe you are one of them...

        → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Nice one. So, the question is: is my status (AC/WA) related to the tasks? I would say that it is related indeed ;_;

      → Reply
»
9 years ago, # |
  Vote: I like it +123 Vote: I do not like it

Nice sorting.

→ Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve D. T-shirts ?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    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 .

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +44 Vote: I do not like it

      You don't even need to include turn into DP state, because turn = bitCount(mask) % 3.

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      In fact, no need for the 'turn' register, the number of remaining tshirts determines the current player.

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      We can get rid of turn because it will always equal n — number of bits in the mask % 3 :P

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Well, you exactly know, whose turn is it now, but it doesn't really matter, of course.

      → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +41 Vote: I do not like it

    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)):

    for(auto v : turn) {
    for(auto u : p[v]) {
        if(!ban[u]) {
            ban[u] = 1;
            break;
        }
    }
}
    → Reply
»
9 years ago, # |
  Vote: I like it +10 Vote: I do not like it

How to solve B and E. Btw I found C and D much easier than B.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 ...

      → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    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.

    → Reply
»
9 years ago, # |
  Vote: I like it +38 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    can you explain your logic?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it +10 Vote: I do not like it

      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"

      → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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).

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
9 years ago, # |
  Vote: I like it +43 Vote: I do not like it

This contest in Gym: 2016 Russian Code Cup (RCC 16), 2nd qualification round.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to sort an array of ints (not Integers) in descending order in Java?

→ Reply
»
9 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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 :)

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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)

      → Reply