gridnevvvit's blog

Codeforces Round #184 (Div. 2)
By gridnevvvit, 12 years ago, translation, In English

Hello!

A few hours later, on May 19th at 17:00 MSK, you are lucky to participate in Codeforces Round #184 for Div. 2 participants. Traditionally, Div. 1 participants can take part out of the competition.

Problems have been prepared by: Gridnev Vitaliy (gridnevvvit), Ignatyev Alexander (aiMR). It’s our second round and I hope not last. We want to thank Gerald Agapov(Gerald) for help in preparation of this round, Michael Mirzayanov(MikeMirzayanov) for marvelous Codeforces and Polygon systems, Mary Belova(Delinur) for translating the problems.

We hope you will like these problems, and that it will be fun to solve them.

Also we strongly recommend you to read all the problems.

We wish everyone good luck and high rating!

UPD1: Scoring will be standart: 500, 1000, 1500, 2000, 2500.

UPD2: Editorial

UPD3: Congratulations to winners:

  1. SillyHook06
  2. hyplymac
  3. HAPKOMAH
  • Vote: I like it
  • +147
  • Vote: I do not like it

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

I like the previous contest of gridnevvvit. i hope this contest is similar to previous.

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

    window is open, you can easily jump out.

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

I think it will be interesting. :)

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

I hope that contest would be easier than last time(181 round)

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

two successive rounds that starts at 17:00(MSK) I hope this starting time keeps on.

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

"pretest 3" what a pretest!

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

    Problem A ?... i can't imagine what is wrong in my code :(

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

      in problem A,

       Vasya can only sum pairs of integers (a, b), such that for 
any decimal place at least one number has digit 0 in this place

      it means you cant get sum of (10, 20) but you can get sum of(1,0), (100, 11), ... Maybe it's the 3th test

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

        it says at least so I assumed that if both numbers had a digit that was 0 we could add them.

        also what exactly does this refer to?

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

          For each digit p in number a and number b, at least one of a_p and b_p has to be 0.

          e.g.: a = a_2 a_1, b = b_2 b_1 => a and b can be added if a_1 equals 0 or b_1 equals 0 (or both) AND [same condition for a_2, b_2] (=> a and b both have 2 digits, so a_2 and b_2 are non-zero => they can not be added)

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

      In problem A, the maximum number of the chosen integers is between 0 & 4. Because if you choose a 2 digit integer, you cant get another one( If you choose another 2 digit number, the first digit of both of them is !0 & you cant sum that pair). And you cant choose more than one of 1 or 3 digit numbers with same reason. So in maximum case, Vasya can choose 4 numbers a,_b_,_c_,_d_, a=="0", b = a one digit integer, c = a 2 digit integer, d = a 3 digit integer & d = "100" Sorry for my terrible English!

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

        this is not always true. what about the input 1 0 0 0? he can choose all the 4 integers!

        UPD: just re-read the problem statement. the input i mentioned is invalid, because all the integers must be distinct! sorry about that!

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

I_Love_WJMZBMR

This handle made my day.

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

I do not understand problem A's statement!!! Can Anybody explain to me what problem A means? Thanks in advance.

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

    Problem A is weird.

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

      Can you please explain this test case:

      3
      2 70 3

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

      Can you explain with an example?

      I thought that having two numbers A and B, then if and only if either of those numbers has at least one digit that is equal to 0, then the two numbers can be added.

      So for example 90 18 can be added, 11 99 can not be added and 10 100 can be added.

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

        actually 90 and 18 cannot be added because at 10's place there are 9 and 1 and none of them is 0.

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

      Yeah, this was my worst contest ever, A problem was very strange

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

    It seems like I will never understand what the author wants to get in Problem A. Problem Statement: "...pairs of integers (a, b), such that for any decimal place at least one number has digit 0 in this place ..." Step 2 of tutorial: "If we got number greater than 0 and less than 10, we take it." I really do not understand then test case 2.

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

The Round #184 is displayed "finished" here. What happen?

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

what was the pretest 3 in problem A?

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

Horrible !!!!

What a case is pretest 3 !!!! :/

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

This was a hard contest.

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

worst contest ever for me.... :(

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

I can't connect to "yandex.st" website. This issue increases time of loading each page to 4-5 minutes for me. I should have waited a long time for reading problems or to see the result of my submitted code during contest. Anybody else having the same problem? Can the moderators fix this?

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

    What? yandex.st?

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

      Codeforces get js from jandex.st. You can view the source code of this page and you can find yandex.st there.

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

    Iraninan users have the same problem, but today I used mozilla and I didn't have the problem

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

    I think in these cases, you should go to codeforces.com through a proxy, just a simple proxy could be fine since we don't need any JS in codeforces ;) : here is mine : www.jabeja.tk/p/index.php

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

ideas for solving C ??

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

    Think of the binary representation of the sum and the binary representation of a 2^v -1 decimal number.

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

    2^V-1=2^0+2^1+2^2+...+2^v-1 if array consist of distinict elements ans=MAX(a1,a2,...an)+1-n; there is only one problem if you have same powers in array.In this situation you need to transform your powers in such way that get distinict powers, for example: if you have 2^8,2^8,2^8 you can tranform it and get 10^8,10^9 if you have 2^4,2^4 you can tranform it and get 2^5

    sorry for my poor english

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

    2^0 + 2^1 + . . . + 2^n = (2^(n+1)) — 1 Your task was just to find the biggest power of 2 and count how many of the powers from 0 to the biggest are not shown in the sequence. but dont forget to change two a s to one a + 1 for example : 2^3 + 2^3 = 2^4...

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

During system testing it showed that my C got accepted. Now, it shows that it failed on test case 26. What happened?

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

Dynamic scoring would work better!

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

How to use long arithmetic in this solution?

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

    Don't think you eally need it. What about d=gcd(p,q); p=p/d;q=q/d? :)

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

      WA43. I think that we need long arithmetic because of p = big prime number and q = big prime number => their gcd equal to 1 and it doesn't change our p and q.

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

        I am not talking about overflow. For example you have p=100, q=50. And your algo will find Pn=2 and Qn=1 which is quite the same.

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

      And another question. Why thistakes AC and WA43? What is the difference?

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

        In first one you use BigInteger by default so it is OK.

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

Can someone please explain this testcase for problem A: Input: 2 1 2 Output: 1 1

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

    consider answers: (0), (1 1), (1, 2), if you can choose (0), you can choose(1 1), in both answers you couldn't choose two numbers that can add together.

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

Could someone, please, help me? I can't find mistake in my solution for C problem. Here is my code.

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

    I think you need to delete (or count) elements that become 0 again.

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

      Oh, damn. You're right, thank you! Such a stupid mistake :)

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

cool bug in the codeforces! http://nic.p.ht/up/c70903297fe1.png

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

    it means that your solutions is in a queue and not now accepted :)

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

      But I didn't pass the pretest of problem C :(

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

    Jump from the window.

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

Conteste fogholade chert!! Maskhare bud...

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

Kudos to problemsetter for D. A really nice problem, in how a lengthy statement with many conditions can be visualized in a way that leads to a simple solution (although with several special cases to be checked).

To explain what I mean, my solution:

  • it's clear that the original graph, as well as any target graph, must be a DAG without multiple edges

  • the first condition for the target graph means that it contains a directed path through vertices 1->2->3->...->N; then, the 4th condition means that between any 2 corresponding vertices, there is no other (shorter) path, so "any edge from vertex i must lead to vertex i+1 or at least i+K+1"

  • the 5th condition boosts this to "any edge from vertex i must lead to vertex i+1 or exactly i+K+1"; you may view the graph as an incomplete cycle with additional "bowstring" edges

  • the 5th condition also implies that if there's a vertex i (with the smallest possible i) in any target graph that there's a bowstring edge from i to i+K+1, then all other bowstring edges may only lead from vertices i+1..i+K to the corresponding +K+1 vertices (if these exist); these conditions are also sufficient for any target graph

  • so if the input graph contains an edge from i to neither i+1 nor i+K+1, the answer is 0; similarly if there're 2 bowstrings i->i+K+1 and j->j+K+1 such that j >= i+K+1

  • if those conditions aren't satisfied, we must add all edges i->i+1 and then we can choose a suitable first bowstring edge (if the first bowstring in the original graph is a->a+K+1 and the last one is b->b+K+1, then the chosen first one must start at vertex at least b-K and at most a, inclusive, but also at vertex at least 1 and at most N-K-1, obviously); iterate over all those possibilities, or over all vertices from 1 to N-K-1 if there's no bowstring in the original graph

  • if we've chosen the first bowstring from i to i+K+1, the answer is 2^(maximum number of bowstrings we can add-number of bowstrings already starting at vertices between i+1 and i+K in the initial graph); the second part of the exponent is fixed due to all bowstrings having to start at vertices i+1..i+K, and the first is simple min(K,N-K-1-i) when indexing vertices from 1

  • precompute powers of 2 up to 2^K; then simply iterate over all possibilities and add them to get the answer

Details are skipped, feel free to ask if you find something lacking. Code: 3746010

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

    Thanks. I am a setter of this problem, but there was another statement. There were no initial edges in graph. But Gerald gived idea to add initial edges in graph

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

for problem a test 3, the array of my output is :

[70, 40, 30, 100, 50, 60, 0, 16]

why it's get WA, if we sum from 70 until 0, the total is 350, and 350 + 16 is valid operation, i think...

thx

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

    30, 40, 50, 60 and 70 can't be in the same output. Vasya can only sum pairs of integers (a, b), such that for any decimal place at least one number has digit 0 in this place

    In the second decimal place, none of them has 0

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

    You cannot sum 40 and 30, for example

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

      why ? isn't one of them has digit 0 ?

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

        "Vasya can only sum pairs of integers (a, b), such that for any decimal place at least one number has digit 0 in this place."

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

          oohhh, took so long to understand that important sentence,

          at first glance what crossed in my mind is, vasya can sum pair of integer (a,b) if a has at least one 0 or b has at least one 0

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

            I made the same mistake and got two wrong answers. Two of my friends also misunderstood the statement. I think it would be better if there were more clear examples or sample tests

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

I wonder why updating ratings takes a lot of time!

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

    Checking solutions is a way easier problem than updating the ratings I guess

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

      You know, they have to change colors of nicknames at every single subdirectory. Manually. It takes time.

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

In Problem A. How can a single number form a pair?

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

    We're looking for such numbers that if we choose any pair, their addition is allowed. But if there's just 1 number, there are no pairs, so we never get a situation which is not allowed, so 1 number is a valid output :D

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

      Vasya wants to choose some integers from this set so that he could sum any two chosen numbers.

      But the set dosn't contain two numbers! So the output cannot be a single number i guess.

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

        Read "so that he can sum any 2 chosen numbers" as "there are no 2 chosen numbers that he can't sum". 1 number satisfies that.

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

          I think sometimes CF expects us to read the mind of the problem setter. :/ no more arguing.

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

            Sorry, but that's the standard convention in mathematics. I've encountered it several times (once with the warning that the problem statement uses strict mathematical logic :D).

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

            hang yourself

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

taking long time to update ratings!!!

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

Rating?

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

The contest time is too early for me! It's better if the contest starts two or three hours later.

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

The best contest ever... Problem C was easier than A!

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

    Повесься

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

      what does it mean?? "Повесься"

      → Reply