Nerevar's blog

Codeforces Round #218 (Div. 2)
By Nerevar, 11 years ago, translation, In English

Greetings to the Codeforces community!

Today in Saratov there is a second day of the local school competition, so we again introduce you a round based on school problemset. Round is for participants from Division II. Members of the first division can participate out of competition, as usual.

Round starts on 8-th of December at 09:00 UTC

Problems were prepared by employees and students of Saratov State U, including MikeMirzayanov, Fefer_Ivan, NALP, HolkinPV and me.

Scoring: 500-1000-1500-2000-2500.

UPD: Congratulations to the winners:

  1. asalwaysdontbeahero
  2. VKRNVO5
  3. chnluyi
  4. pkwv
  5. Xe4NIK

UPD: tutorial.

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

Comments Comments (45)
| Write comment?
»
11 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

What will be the scoring? Edit: Scoring added

→ Reply
»
11 years ago, # |
  Vote: I like it -42 Vote: I do not like it

I hate contests in unusual time (Do U know what is time?!)

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

I am coming

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

    That's quite unfortunate choice of words :P

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

Forgot to register for the contest T_T. Realized when tried to submit :(

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

Found someone who wrote the following code

int arr[100];
for ( i = 1; i <= n; i++ ) scanf ( "%d", &arr[i] ); //Here n can be 100.

Tried to hack it with a test case where n is 100 ( My first attempt to hack a code in my life ) but failed. Is there any full proof way to make the code go out of bounds?

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

what a greedy contest! :D

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

What is the logic behind Problem D?

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

    You just need to simulate what the problem asked for. Fill certain container until it is full. Once full, pour the remaining water in the next container. If the next one is full too, try the next one until you find an empty container or you reach the floor. Finding the next container efficiently is the trick here. I used Disjoint-Set-Union data structure to quickly find the next container.

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

      I used a segment tree, I initially thought of DSU but after that I thought that it would have too high of a complexity.

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

        Why? If we use path-compression, isn't it just almost O(1)?

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

          Disjoint-Set-Union is just enough... very small implementation... Nice problem :D

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

          Seems I analysed it too superficial... alas, segment tree was good too.

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

      I used the same idea in practise session but it is still showing TLE

      → Reply
»
11 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Oops, my solution for Problem C & D both got WA6 unfortunately. Orz.

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

what was the idea for E?

Was this to sort the input and work with k consecutive parts ??

I tried this and got WA on pretest 2.

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

    Solution is correct. There might be bug at your implementation.

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

Nice contest with really fast system testing :D

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

Can someone help me with B?

My approach was: 1. Factorize a in powers of 2,3,5. 2. Factorize b in powers of 2,3,5.

Answer will be sum of differences of power. To find power, I found all powers of 2,3,5 uptil 10^5, for fast calculation. Yet, for test case -> 1,000,000,000 999,999,999 — it was taking more than 2-3 seconds.

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

    finding powers of 2 could be done like this


    int ans = 0;
while (n % 2 == 0) {
  n /= 2;
  ans ++;
}
    → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Which is the test 32 ¿? I can´t see tests in submissions :( I got accepted in practice, but I cant´t imagine slow behavior for any test.

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

      Using bitwise operation could be faster:

      int ans = 0;
while ((n & 1) == 0) {
  n >>= 1;
  ans ++;
}
      → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +17 Vote: I do not like it 

     Sent   Hacked   Accepted 
 A | 1235 | 15     | 1020     |
 B | 1132 | 36     | 662      |
 C | 716  | 9      | 285      |
 D | 329  | 0      | 150      |
 E | 95   | 2      | 18       |
Participants count: 1342

More info

→ Reply
»
11 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

wonder why my submission 5386072 (using recursion) gave MLE. my guess is that stack size of the judge is pretty low, because i used the exact same idea in practice submission 5388703 and got AC.

EDIT: i think the solutions and tests have not yet been made public, so u may need to wait for a few minutes to see them.

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

    We can't see your solution.

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

    I think that your solution made an infinite recursion. As I know, the stack size of the judge is equal to the memory limit of the problem.

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

When I try to see someone's solution here http://mirror.codeforces.com/contest/371/standings nothing happens. A pop up is there when I double click on the cell. But the submission link to show the user's actual code doesn't work for me. Any help?

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

    You'll be able to see solutions after some minutes.

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

I have a question about Problem B! In the first sample, how to get the output result 3 ????? I always think the result should be 2. That is, first, 20/2=10, then, 15*2/3=10, and over.

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

    20=(2^2)(3^0)(5^1) 15=(2^0)(3^1)(5^1)

    Make the powers equal, which will require 3 steps.

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

    When Fox is dividing the cheese by 3, she TAKE 2/3 of it. So, if the size of cheese was n, after dividing it becomes n / 3.

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

Can anyone help figure out why my D is wrong at Test 6 Ans 34th ?? Thx.

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

Is there anyone love to share thoughts on problem E?

My implementation was sort station ids by their location. Then I guess the solution must be k consecutive stations. Then I scan from left to right. I got WA on 15.

Is my algorithm totally wrong or I missed something in my code? Thanks.

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

Worst time ever :( Please move the hour or maybe the day xD

→ Reply