Russian Code Cup 2016 — Elimination Round
By RussianCodeCup, history, 8 years ago, translation, In English

Hello!

Let us remind you that Russian Code Cup 2016 Elimination Round will take place on June 19, 2016 at 14-00 Moscow time. Top 200 from each qualification round can take part in Elimination round, 200 best coders in Elimination round will get branded championship t-shirt, and top 50 will advance to the Final Round that will take place in September. There are money prizes to grab in the Final Round.

Good luck everyone and see you at http://russiancodecup.ru !

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

Comments Comments (41)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm wondering what does "Register at http://russiancodecup.ru and participate!" mean in the invitation email?

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

How to solve B? i got WA several times with ternary search.

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

    sort according to non-decreasing L[i] , now if u set number of left legs to L[i] , the number of valid pairs will be number of R[j] ≤ N - L[i] where 1 ≤ j ≤ i , so do coordinate compression and apply a BIT.

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

      A priority queue would do too. Always pop the queue whenever Rtop > N - L[i] because it will never be valid again as N - L[i] is non-increasing. The answer for taking L[i] as the number of left legs equals the size of the queue after popping invalid items.

      P.S. Hey fellow doge!! LOL

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

    I sorted the sequences increasing with respect to L.

    After that, I iterate in that sequence, let's say at step i we have Li as the left number:

    • Then the maximum right number is Ri = N - Li. Observe that in this way, Ri is decreasing
    • Since Li is increasing, we satisfy every note in respect to L before, the only problem is satisfying R queries before. So we use a structure (like a C++ map for example) that can get the values of R before that are greater than our current R — and we delete the values lower than our current R since Ri is decreasing. The answer for iteration i is the sum of values in the map. We get the maximum in every iteration.
    → Reply
»
8 years ago, # |
  Vote: I like it +24 Vote: I do not like it

How to solve E???

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

    For each i, compute two values:

    • The sum of values of all coins whose value is between [2i, 2(i + 1))
    • The smallest value of all coins whose value is between [2i, 2(i + 1))

    This will lead to an O(nlog2n) solution. However I'm not sure if this is intended (sparse table got MLE, segment tree got TLE, segment tree + pruning passes).

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

    There are absolutely no complex DS involved, at least in my solution.

    First, think about why it's enough to iterate "x -> 1 + sum of numbers up to x" for a given range until the sum is smaller than x. It's fast enough, since as we're iterating, x strictly increases and so the sum increases quite quickly.

    We can find sums in a given range using a Fenwick tree. We'll process numbers in non-decreasing order, add them to the Fenwick tree and deal with iterations in all queries at the same time.

    When we've just processed all numbers  ≤ x for some query's current x, we can find the sum for its next iteration, check if it's time to stop and if not, move on to the next iteration there. The current iterations for all queries can be stored in a set / priority queue / etc., from which we can take the smallest ones as long as they're less than the currently processed number. Time complexity: unknown, but it passed without any optimisations.

    UPD: Downvote logic on CF again. If I'm wrong, why not comment?

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

      You are actually right, it is N log N log K, where K=10^9. Each query will be processed log K times max, and they are in the priority queue.

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

    i used persistent segtree to get sum from L to R with values from x to y. It passes with coordinate compression.

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

So how to solve E?

I tried complicated O(n * sqrt(n) * log(n)) solution and got TLE on test 27.

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

    : let's add numbers one by one starting from the smallest, and maintain sums on the segments from queries. If we're adding number x and there are sums  ≤ x - 2, recompute them (and if they're still too small — we're done). The trick is, each sum will be recomputed logarithmic number of times: if it was s1, then s2 and then s3, then s3 - s2 ≥ s1.

    One pitfall is that Segment Tree is too slow here :( But Fenwick tree passes.

    → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 5   Vote: I like it +18 Vote: I do not like it 
    S = 0
while (true) {
   S2 = sum of numbers less than or equal to S + 1 on segment [l, r]
   if S2 == S
      break
   S = S2
}
print S + 1

    That can be done online with persistent segment tree code

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

      It looks like you uploaded a wrong code. It doesn't work on the sample, there shoud be inequalities on line 188.

      EDIT: OK, the bug is not here, now I don't know how to fix it.

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

        Yes, my fault. There should be += instead of = in line 249. I thought no one run the code which is posted as example:)

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

      I love this piece of your code:

      typedef int itn; :D

      → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

I was sad that I spent the whole contest trying to get D accepted, when I saw tourist and Petr failed it too, I'm completely fine with it now :P

Edit: Same code passes in the Gym in 300 ms, what was up with the time limit for this one?

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

201st. Nice.

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

For B,If there are multiple solutions, output any of them? Why did I always get WA on test2...

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

Duh, how is that so many people solved E and some even in 7 minutes :f? I managed to get it ACed, but I think my idea is not that straghtforward. I divided numbers from input into intervals [2k, 2k + 1) and for every such part I built a segment tree taking minimum on interval and prefix sums. Then I did this:

    RE (_, q) {
      int a, b;
      cin>>a>>b;
      int cur_z = 1;
      REP (l, L) {
        int m = tree[l].Read(a, b);
        if (m <= cur_z) {
          cur_z += prefs[l][b] - prefs[l][a - 1];
        }
      }
      cout<<cur_z<<"\n";
    }

But it still needed a bit of stupid optimizing since I got TLE.

Is that a case that many people had prewritten some structure like "what is sum of numbers on interval [l, r] not larger than x?"

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

    Not the first time most important problem of RCC elimination round is from some other contest. Copy-pasting doesn't take that much time.

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

    I spent about 10 minutes. Copy-paste of Fenwick tree (+2 minutes) and fast input-output.

    1. Well known greedy

    2. We see 2D-queries

    3. To solve the problem in offline sort queries and use Fenwick tree. Implementation is short, 25-30 lines of not copy-pasted code

    P.S. Some people said the problem was on CodeChef contest. For me it was a new one.

    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +37 Vote: I do not like it

The problem E is the same as this problem (editorial).

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

How to solve problem D??

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

    Greedy algorithm. First fill all containers to minimum volume. Then, start filling the containers to maximum volume in the order of increasing pi. When filling a container to volume v, reserve of reagent ci and of any reagent (you need to track the total volume of unreserved reagents).

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

      Do you have some ideas why this has enough precision (I'm asking partly because my extremely similar solution failed because of a precision issue)?

      It looks like you're operating with numbers as large as 1e10, then the error we get on each operation there is around 1e-6, so it seems unexpected that we can get an answer that's checked with tolerance 1e-6 and pass?

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

        In the first part of my program (when the containers are filled to minimum volume), both sumv and sumcap are integers, so there is no rounding errors here. In the second part (when the containers are filled greedily), sumv is an integer until the very end. In the last part (when the answer is generated), there are no values as large as 1010. So, the only interesting place is the second comparison between sumv and sumcap. Well, it works for some reason, quite possibly because of weak tests. In my submission, EPS is 1e-9, but it was mostly a guess.

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

          Thanks — keeping everything in integers as long as possible is pretty clever! Although as you point out, it doesn't seem to help for the worst possible case.

          I've looked at both reference solutions, and they use eps liberally here and there, so maybe the contest authors know why there is no big precision loss here?

          In my solution, I've used the same trick with multiplying certain numbers by 100 to avoid imprecision there, but switched from integers to doubles slightly earlier, and maybe have a less lucky eps.

          My code
          → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
          ← Rev. 2   Vote: I like it +149 Vote: I do not like it

          Yeah, it looks like this problem is unsolvable without BigIntegers. Here's a testcase where we can actually pour out all liquid except 100/lcm(1,2,3,..,100) which is about 1.5e-39. So the correct answer is NO, while I expect all passing solutions to output YES.

          1
25 26
1 10000 1 100
1 10000 2 99
1 10000 3 98
1 10000 4 97
1 10000 5 95
1 10000 6 94
1 10000 7 93
1 10000 8 92
1 10000 9 91
1 10000 10 89
1 10000 11 87
1 10000 12 86
1 10000 13 85
1 10000 14 83
1 10000 15 82
1 10000 16 81
1 10000 17 79
1 10000 18 74
1 10000 19 73
1 10000 20 71
1 10000 21 67
1 10000 22 64
1 10000 23 61
1 10000 24 59
1 10000 25 53
18 8 41 83 40 15 22 5 14 46 24 12 15 7 16 79 75 5 54 13 9 5 6 22 24 142
          → Reply
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
            ← Rev. 3   Vote: I like it +107 Vote: I do not like it

            I hope one day people finally understand that problems with yes/no answers and double are bullshit

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

              Well, they are not bullshit, if say in statement something like "if change all parametrs within blablabla, answer will not change". But probably it can be hard to validate.

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

                Well, it's almost always hard to validate and/or create adequate tests (i.e there should be tests where params within 2*blahblah and that may break smth) and/or nobody cares

                If that's done, I agree that's OK

                → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +35 Vote: I do not like it

not the first time.... and this passed sample and wa at test 4...

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

    Same me, "cout<<-1<"\n" bring me out of top 200.

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

The contest in GYM: 2016 Russian Code Cup (RCC 16), Elimination Round. Welcome to practice!

Thanks for organizers and jury. I liked it!

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

Will participants not in Russia still receive shirts if we came top 200? I'm just curious as it wasn't clear on the website.

→ Reply