Antoniuk's blog

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

Hi everybody!

Codeforces round #247 for Div. 2 participants will take place on May 21 at 19:30 MSK. Traditionally, Div. 1 participants can take part out of the competition.

Problems have been prepared by me(Antoniuk) and Kirill Schetinin(KaiZeR). This is the first round prepared by us and we hope that you will enjoy the round.

We want to thank Gerald and Delinur for helping to prepare the round and MikeMirzayanov for Codeforces and Polygon.

UPD: Score distribution will be the next — 500-1500-1500-2000-2500.

UPD2: The contest is over, we hope you enjoy it)

UPD3: Editorial.

UPD4: Statistics.

Congratulations to winners!

1) hzjsxxy
2) azariamuh
3) tonkosi
4) inutard
5) c.u.c.u.m.b.e.r

Gl & hf)

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

Comments Comments (82)
| Write comment?
»
11 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Ukrainian contests are always special , hope it will be a special one too

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

Antoniuk , your chart is quite interesting after you become yellow you drooped to gray then you backed again to yellow , can you tell what is the reason behind this?

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

Wow!! if Antoniuk was involved that will be definetly awesome.

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

Last contest that Gerald participated was Codeforces Round 104 (Div. 1), Since then, He is preparing contests...

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

i am a little bit worried about the problem statement.

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

    I hope the problem setter will have explanation for the first example for problem A.

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

    Don't worry it's unrated for you :)

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

Sereja also comes from Ukraine. He is always setting very attractive problemset. :)

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

I don't know if it's only me, but the english translations are very bad. I was not able to comprehend problem E at all.

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

    I can't understand russian version of problem's E statement, although Russian is my native language.

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

      It looks like this problem much easier to solve than to understand.

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

      I could not understand English statement, because it was not clear. After switching to Russian, failed to understand again. And I thought it is because I was not native Russian speaker. :(

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

    I couldn't understand the statement of E.

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

    It's not only you. For problems A-D the english translations were alright. For problem E, WTF?? I still don't understand what the problem wants us to do.

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

Problem D. There is no answer if m = 0 and d = 1

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

    The statement says there is guaranteed to be a solution for given m, k. Which means that a test with m=0, k=1 will not appear.

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

      what was the solution for problem D?

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

        i think binary search + dp

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

        If you try to find the formula for a given n, you will end up with something like (sum of binomials) = m. It can be solved greedily.

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

I think problem B should be 1000 instead of 1500 !?

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

Again, like other contests, a lot of newly registered participants (within 10 hours of the contest); but the worst of all is that the first person in standing, containing both div 1 and div 2, is one of those!

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

What is that mythical Test #9 in problem D? I can't pass it =\

It seems that D and E are way harder than normal for these contests. I solved E because I had code for R-B trees handy, which probably wasn't the expected solution.

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

    Maybe your program writes "0"

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

      That was indeed the case, but I wasn't using binsearch so my solution naturally got the zero. I don't understand the point of this, the goal is to solve the problem and not look for every possible corner case that has very little relation to the actual solution.

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

    0 2

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

      what about editorials?

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

        Will be published soon after system testing.

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

What was the approach to solve problem C?

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

    I used Dynamic Programming

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

    Compute the total number of ways to break number n into summands which are <= k. Let it be S. Then number of ways to break n into summands which are <= d-1. Let it be R, these ways to break the number are "bad" and should not be counted in the final answer. Thus, the final answer is S-R.

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

      No , I don't think that will give the correct answer in case when we take modulus along the way.

      mod = 1000 ; Suppose final S = 1234 and final R = 999 ;

      but when we will take modulo S%mod — R%mod <= 0 Which will give the wrong answer.

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

        I gave just the general idea, modulus is the detail of implementation.

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

This is my first contest :) Hope I will get a high rating :)

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

Why did this solution pass systest?

Interesting part:

REP(i,strlen(s)){
     kq+=a[s[i]-'0'];
}
→ Reply
»
11 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Any ideas on how to solve B for a much bigger N? First time i read the problem i thought n <= 10^5

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

    I have solved it in O(N^2) using DP. I think it can't be solved faster. So, n could be somewhere around 2000.

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

      What is the runtime (in seconds) for n=2000?

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

    Same here! Wasted 5 minutes and then solved C before realizing n is always 5.

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

how this solution AC ?!!! http://mirror.codeforces.com/contest/431/submission/6671729

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

Same solution for problem D got AC in MS C++ and WA in GNU C++.

6676019

6676015

Why? :(

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

    As for your code, the behavior of X >> i is undefined when i = 64, for the behavior of op1 << op2 and op1 >> op2 is undefined if the op2 is negative, or greater than or equal to the length in bits of the op1. So, you can get AC in both MS C++ and GNU C++ by replacing X >> i with i < 64 ? X >> i : 0 for example.

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

      Thank you, I got AC by calling the function with i=63 instead of 64.

      I found that it's undefined even in MS C++...

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

Problem C should tell that the number must be positive or something like that. For example 17 mod 5 = 2 = -3. When you say print 17 module 5 I can print -3 too unless you specified that the answer must be positive. After 1:24 I got hacked and immediately submit another. which is now accepted but I lost a lot of point -50 and ~ -450 or -500 for timing.

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

    the problem asked you to print the number of paths , how it can be negative ?

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

    You can blame broken % operator in C++. But don't blame contest authors ;)

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

      No! % operator works ok. I write my code in a way which the number could be negative.

      I corrected it by replacing cout << ...; by cout << (... + 10..7) % 10..7;

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

        That's what I did. I used long long and ( + 10....007) % 10...007 staff. If % operator was mathematically correct in C, there would be no need in jumping through hoops like this.

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

Wasn't problem A too easy to become a contest problem?!

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

Nice problems.... :)

Nice contest for me... :)

Hope to see you again... :)

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

Can someone please explain the statement of problem E ?

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

    The subproblem can be formulated as this: You have an area of land, with h[i] being the height of the i-th section. You want to pour V liters of "rain" on this land (so that the water level is the same for each section that isn't dry). Find the resulting water level.

    Now you have the initial heights, and a bunch of queries that either change the height of one section, or ask you to solve the subproblem for a given V.

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

When will the editorial be available??

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

Is there a way to download the test cases, other than trying to "brute force" it by sending fake solutions? My solution to E fails on one single query on test #28, and all other queries are correct. Very suspicious...

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

    Try writing big random test generator and brute checker function, and test your solution with it.

    It seems far more productive that brute forcing tests.

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

      Considering it works on all test cases except for one single query, I don't think I would be able to replicate that easily. Besides, I already did that last time I used the same data structure.

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

http://mirror.codeforces.com/contest/431/submission/6672763

http://mirror.codeforces.com/contest/431/submission/6672950

aren't these two solutions same ?

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

can someone explain me why this solution gets WA :6676798 my answer is : (all the paths using edges with weight k or lower) — ( all the paths using edges d-1 or lower)

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

I like div-2-only contest because I have to compete with the second (or nth) account of the first-division people. No, it is a joke, lol. I don't like div-2-only because that.

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

Round Stats

→ Reply