albertg's blog

Codeforces round #382
By albertg, 8 years ago, translation, In English

Hi Codeforces community! I am glad to announce that at 27 November 16:35 (GMT time) will take place Codeforces Round #382 for participants of both divisions.

Author of this round is me (albertg). I am from Armenia and the only Armenian author of any Codeforces round yet. (Sorry Edvard). This round is my second round and I hope this is not the last one! :) it is the last one. As usual, I'm thankful to the coordinator of Codeforces Gleb Evstropov (GlebsHP) for helping to prepare this round and Mike Mirzayanov (MikeMirzayanov) for wonderful platforms Codeforces and Polygon. Also special thanks to super_azbuka for an idea of a problem.

As usual, contestants will have 5 problems and 2 hours to solve the problems. In this round you should help Ostap Ibrahim Bender to reach Rio-de-Janeiro. Good luck and have fun!

UPD1: Scoring: div1 750-750-1500-2000-2500, div2 500-1000-1750-1750-2500.

UPD2: Editorial is posted.

UPD3: If somebody has question(s) about solutions of problems, please write me a personal message.

UPD4: Please read this.

UPD5: Editorial of problem div2E/div1C is posted.

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

Comments Comments (321)
| Write comment?
»
8 years ago, # |
← Rev. 2   Vote: I like it -95 Vote: I do not like it

Clashing with another contest
One of them (HR preferably), please reschedule, so we can participate in both.

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

    If you want HR to reschedule why are you posting it here?

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

Who is Ostap Ibrahim Bender ?

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

    He is a famous rapper from Odessa.

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

normal time again

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

Is it rated?

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

Its fu*king rated..! Dont ask is it rated or not !

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

5 problems round again! Wish it to be an interesting round~: )

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

Hey, I'm new to codeforces. Can you please explain me what is Division 1 and division 2? Thanks.

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

    Please

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

      Thanks! Just one more query. Do we have to register separately for the contests (for instance, this one) or if we are on codeforces, we can directly give them? If we have to register separately, how to do so? Thanks again.

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

        Yes, you have. Registration opens about 24 hours prior the contest.

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

    waiting to see your performance in your first round
    good luck

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

Again....5 problems!!!

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

18:35

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

Perfect time for me

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

Codeforces always helped me to improve my thinking capability , thank you codeforces :)

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

The comment is hidden because of too negative feedback, click here to view it

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

Petr has register for DIV 1. He must be aiming to get his second spot. Wish it to be exciting round!

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

    jqdai0815 has registered too. He will try to prevent this.

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

    Actually he can get his second spot without participating :D

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

      Tourist used that trick before, remember?

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

      Is it all? Just a comment? Aren't you gonna write a blog?

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

      Actually you also got second spot without participating :D
      Seems like its too difficult to get positive rating change when you are among top rated contestants.

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

I hope I can help Ostap Ibrahim Bender to not reach Rio de Janeiro.

Life is not the best right now here :P

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

    You don't have to help, by the way, but I warn you, we have a long reach

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


Ostap Bender is a fictional con man who appeared in the novels The Twelve Chairs and The Little Golden Calf written by Soviet authors Ilya Ilf and Yevgeni Petrov.

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

So we should expect graph theory problems in this contest.

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

After a long time :D Back to home , codeforces ! The love! <3

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

Is it rated ?

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

Hello.
This is my first contest.
Wish me good luck.
Also every Punjabi add me.
Jai babe di

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

    Good Luck!

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

      Thank you for your wishes.

      I was solved with 4 problems .
      I do coding and get a job and a girl friend and a happy life with some naughty time .

      Also I am trying to get girlfriends on CodeForces.

      Add me.

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

Score Distribution?? Not declared yet, 17 minutes left

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

    "scoring will be posted just before the contest" might mean 30 seconds before the contest :)

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

Where is scoring?

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

This scoring will be posted just before the contest!

So the contest is gonna be delayed again?

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

At least I don't have to worry about system test (and can sleep early)

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

A=B=C=D<E

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

That sad moment when you're certain of your solution but it won't pass and you can't find where is the error

rip rating :/

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

    Same as you, WA test 5 C and WA test 6 D

    RIP rating :(

    Plese someone tell me what where those tests so I can go cry myself to sleep

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

      WA 5 C, hacked D ;_;

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

      on D instead of searching for highest prime I searched for any prime P with n - P <  = 500 and it passed test 6, the pure greedy solution isnt correct it seems

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

        Check out Goldbach Conjecture

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

        I repeat this 1000 times: while (n > 0) { x = calc(n) // calc(n) = the biggest prime number which is <= n; repeat x = calc(x — 1) 0 -> 3 times if n — x = 1 then x = calc(x — 1); res++; }

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

        No need of searching.

        If prime, print 1.

        else if even, print 2

        else if n-2 is prime, print 2

        else print 3

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

          You know, before the contest I knew nothing about Goldbach Conjecture and never used logN prime test. I learnt all of this just during the contest and implemented this: if prime ans = 1, if even ans = 2, if odd ans = 3. But why if n-2 is prime then ans = 2? I understand that this is true, but why namely n-2? Why not n-4? Maybe I just dont know math good enough :(

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

            Because 2 is the only even prime number.

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

            because 4 is not prime. You check for n-2 because 2 is also prime, and then that odd number would be written as a sum of 2 primes. if you checked for n-4, then you would decompose the number in one prime plus 4, which would give 3 instead. The only case that an odd number is a sum of two primes, is when one of them is 2.

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

              Sorry, n-4 is my mistake. Then why not n-3? I see that 2 is somehow more unique in this case, but why namely 2? Is there a theorem or you just logically deduced this?

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

                man, seriously!! are you even thinking? (no offence) this is too trivial.

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

                  The comment below explained it good and I really couldnt understand it. What is trivial for you may not always be trivial for every one. P.S. If you say "no offence" it is still an offence.

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

                If an odd number can be split in 2 primes, one of them must be a 2, because in order for 2 numbers to add an odd number, one must be odd and the other one must be even. Then, the only posible split is 2 and n-2, if n-2 is prime.

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

                Because 2 is the only even prime.

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

    Are you talking about D? Cause I'm pretty sure mine is right too lol (unless I just entirely misunderstood the problem).

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

      yeah, just found out it gives WA for 2e9 as input :/ fml

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

        Lol that was my wrong answer too. Guess I should've googled a bit harder to find out about the Goldbach Conjecture.

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

    rank dropped from 11 to 600 , just because of a stupid blunder :/

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

How to solve Div1 C and D?

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

    Div 1 C:

    DP(u, dist, nearest_one) is number of ways to color:

    • subtree rooted at u.
    • Amongst the vertices that does not satisfy condition "at least one black vertex v at distance no more than k", the maximum distance to u is dist
    • The black vertex nearest to u has distance nearest_one.
    → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Edit: I am mistaken :P

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

How to solve Div2 C? Every time I see a problem about any kind of paired tournament I become sad.

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

    It should be a Fibonacci Sequence...

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

    https://www.quora.com/What-is-the-best-way-to-solve-SPOJ-problem-code-TENNIS1

    Contest quality is going down nowadays :/

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

      Wow, it even has tennis statement as well. I wonder how many people googled this.

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

      and author of this problem is albertg and it is posted in 2014?

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

      Well , even though this problem was googleable.

      I reduced this problem to taking out the maximum possible height of an AVL tree for given number of nodes.

      Then you can solve it using Cheating

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

    Fibonacci Number relation.

    Analyze that minimum number of players required for x number of games at top:

    1 — 2 players

    2 — 3 players

    3 — 5 players (One having played 2 matches and other 1)

    4 — 8 players (One having played 3 matches and other 2)

    ....

    The answer is maximum index where fib[i] <= n

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

    Think of it this way. To have a 1-game tournament, you must have 2 players. You can consider 1 player to be a 0-game tournament since there already is a winner. In order to have an n-game tournament, the winner of an n-1 game tournament must play the winner of an n-2 game tournament. This is simply a Fibonacci sequence and can be calculated using dynamic programming. (Extra players beyond the target Fibonacci number cannot make a difference because they cannot reach a high enough game depth to challenge the current champion).

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

    Think recursively. Let the winner has to play x games. Then he has to play at-least x-1 games and the other player has to play at-least x-2 games. Now you can see the pattern. It's Fibonacci. Hope it's help.

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

Can anyone explain how to Div 2 D? I did it greedily where I took the largest prime less than n where n-x >= 2 and then continued to take the smallest prime under that number until I got to 0.

But it seems that way is wrong. Did I miss the correct way entirely?

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

    Two words: Goldbach Conjecture

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

      Yeah I figured that and that's what I was doing so I guess I just had a bug in implementation.

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

        If even (and not 2) the answer should be 2. If odd, then the answer is 3 unless N-2 is prime, in which case the answer is 2. Of course if prime, answer should be 1.

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

          Yeah the one that breaks my code is 2,000,000,000 (it prints 4). Thanks for the help!

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

    I used Goldbach's conjecture, though my solution was hacked.

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

      Did you take care of case where n-2 is prime? Because in this case you can split in numbers: 2, n-2 and the answer would be 2.

      I was "lucky" to get hacked by this case and could correct in time!

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

        No, that is the reason. Unfortunately I was hacked a bit late so I didn't manage to fix the solution in time

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

    why less than n? If n itself is a prime number then the answer would be just 1. I didnt get the solution but this might be your mistake.

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

      I checked for that initially (I should've mentioned that I guess) so I don't think that was it.

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

    I used this. I hope this passes system tests.

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

    Hint: Every number can be written as sum of 3 or less primes. So check if it is possible to write as 1 or 2 primes, if not it must be 3.

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

      So that's what it was. When I input 2,000,000,000 I got 4 but I couldn't find a set of primes that made it sum in 3. Could I ask how you came up with that? Did you already know that you could express the numbers that way or did you just think about it?

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

        That is not true, 2000000000 can be written as a sum of 2 prime numbers. Following is a list (all of them are primes): 

        8388739 + 1991611261 = 2000000000
37749343 + 1962250657 = 2000000000
33554977 + 1966445023 = 2000000000
4194403 + 1995805597 = 2000000000
41943721 + 1958056279 = 2000000000
73 + 1999999927 = 2000000000
8388811 + 1991611189 = 2000000000
20971789 + 1979028211 = 2000000000
29360533 + 1970639467 = 2000000000
20971807 + 1979028193 = 2000000000
12583099 + 1987416901 = 2000000000
127 + 1999999873 = 2000000000
29360449 + 1970639551 = 2000000000
139 + 1999999861 = 2000000000
4194511 + 1995805489 = 2000000000
4194439 + 1995805561 = 2000000000
223 + 1999999777 = 2000000000
37749421 + 1962250579 = 2000000000
16777711 + 1983222289 = 2000000000
20971957 + 1979028043 = 2000000000
4194637 + 1995805363 = 2000000000
33555217 + 1966444783 = 2000000000
12583297 + 1987416703 = 2000000000
29360257 + 1970639743 = 2000000000
8389063 + 1991610937 = 2000000000
25166023 + 1974833977 = 2000000000
4194583 + 1995805417 = 2000000000
8389111 + 1991610889 = 2000000000
379 + 1999999621 = 2000000000
12583237 + 1987416763 = 2000000000
25165843 + 1974834157 = 2000000000
20971651 + 1979028349 = 2000000000
41943883 + 1958056117 = 2000000000
12583183 + 1987416817 = 2000000000
25165909 + 1974834091 = 2000000000
16777441 + 1983222559 = 2000000000
41943919 + 1958056081 = 2000000000
4194739 + 1995805261 = 2000000000
8389261 + 1991610739 = 2000000000
577 + 1999999423 = 2000000000
33554503 + 1966445497 = 2000000000
12583561 + 1987416439 = 2000000000
20972311 + 1979027689 = 2000000000
16778077 + 1983221923 = 2000000000
29361067 + 1970638933 = 2000000000
4194871 + 1995805129 = 2000000000
37748791 + 1962251209 = 2000000000
12583609 + 1987416391 = 2000000000
33554593 + 1966445407 = 2000000000
20972437 + 1979027563 = 2000000000
20972449 + 1979027551 = 2000000000
20972473 + 1979027527 = 2000000000
25166719 + 1974833281 = 2000000000
16777729 + 1983222271 = 2000000000
41943439 + 1958056561 = 2000000000
4194217 + 1995805783 = 2000000000
8388571 + 1991611429 = 2000000000
        → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    My solution (apparently correct) was based on Goldbach's conjecture. The answer was always going to be 1, 2 or 3.

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

      Yeah that turned out to be what was wrong (my code prints 4 for some numbers).

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

    Yeah it's wrong. There is Goldbach's conjecture which says that every even integer can be expressed as the sum of 2 primes and every odd integer can be expressed as the sum of 3 primes. But in some cases we can use less primes, take it as an simple exercise.

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

      Alright good to know. Thanks for the help!

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

    If the number is prime, return 1 (all prime numbers obviously have a tax value of 1, and this is key to the following algorithm). Otherwise, if it's even, then the Goldbach conjecture follows (every even number >2 is the sum of two primes) and you can return 2. If that is not the case, then check if n-2 is prime. If so, then the number is the sum of two primes (2 and another prime) and you can return 2. Otherwise, it is the sum of a prime and an even number (which itself is the sum of two primes), and you can return 3.

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

    Greedy is flawed here. I initially thought it can be solved with greedy. Later, found that it fails if n == p+1, when p is a prime, greedy algo will try to split it as {p,1} but in the description it was given each of split elements should be greater than 1.

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

Div2 B hack?

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

Any idea of prestest 5 of C ?

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

    Suppose, it is "n = 13", answer is 5.

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

      Can you please draw tournament tree for n=13 ?

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

        You can get it from comment below about n = 8 by adding subtree of 5 leftmost participants to the right.

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

          Sorry, that tree for 8 contradicts main rule of tournament. Please provide tree where that rule holds independent of outcome of each game.

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

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

              Thanks. It turned out that grid is not known before tournament starts.

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

    I think pretest 5 would have been 8.

    Answer for 8 is 4 and not 3 as the Maximum number of matches increases when the total number of participants is a Fibonacci number.

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

      Can someone actually draw a tournament grid (tree) for n=8 ?

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

        1 2
        1 3
        4 5
        1 4
        6 7
        6 8
        1 6
        in order of games played.

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

          If player 8 wins 6 in their match, then in the finals it will be second game for him, but 4th game for player 1. That is contradiction with the main condition of problem statement (difference between played games no more than 1)

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

        behold the power of MS paint

        drawing

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

          Thanks, but this picture contradicts main rule from the problem statement. If player 8 and player 1 go to the final, they will have number of played games differ more than 1.

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

            We are assuming the best case scenario (maximum number of games played), so we can assume that 6 will win in this case.

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

              Organizers cannot assume that someone will win or lose. By definition of the problem they need to construct a tournament grid to match a rule: "two players can play against each other only if the number of games one of them has already played differs by no more than one from the number of games the other one has already played"

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

                No, it is not the problem statement. By definition you should find a maximal possible number of games. You don't create a tournament grid, you only should take the best from all possible scenarios of grid+games.

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

                  I copied this from problem statement. Problem statement says that main rule should be applied for the grid (independent of games). But grid above is not valid for the main rule. It can produce sequence of games which contradicts that rule.

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

                  But the grid is not fixed. At that point, it does not exists. And it is not obvious what is grid in that problem.

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

                I think the grid is not completely defined at the beginning. This way it makes perfect sense. Anyway, this is not clear at all.

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

          I might be wrong, but I think the statement is a little bit unclear. This tournament grid is not valid in general, right? I mean, player 1 can't face player 8 according to the rules.I didn't realize that we could consider this kind of grid. :(

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

            Why player 1 need to face a player 8? It is a set of games 1 2 / 4 5 / 6 7 / 1 3 / 1 4 / 6 8 / 1 6 / and some other stuff, when games are valid only if all players won all their games before that. In case that drawn on a picture, we have answer 4.

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

              I get the answer, but why not? The statement says the tournament is being organized. Why would someone organize a possibly invalid tournament? You're right, but it could be a little bit more elaborated.

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

              Is tournament grid known before games are starting? Or organizers can just randomly pick players during the tournament. Problem statement is very clear about "tournament grid", so I assume it should be finalized before tournament starts.

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

                It must be the second option. They can pick players along the tournament.

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

                  Problem statement is very misleading than. It describes the different problem.

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

                  I think it's ambiguous. The expected interpretation is not invalid, so as ours.

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

Loved the idea behind problem D div. 2 (B div. 1).

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

    what idea? i couldn't find the idea behind it! i thought it was greedy but did n;t accept it.

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

      Goldbach conjecture

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

        Is it an idea? If you are not familiar with the conjecture, it is highly unlikely that you will solve the problem.

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

          True. This truthfully was the worst contest that I've participated.

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

steps to perform well on codeforces contest , steps 3 & 4 are enough in this contest i think :/ ....

UPD : you'll need step 2 also , but you should read all the old problems on spoj ..

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

One hell of a tricky contest!

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

How do you solve C? I was so certain my solution was going to pass but it didn't :( I think many others struggled on it as well.

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

    Dp[i] = the minimum number of players needed such that the winner can take part in i games

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

      Wow I didn't think of it as a DP problem. How would you transition between states?

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

        Fibonacci sequence, where dp[0] = 1 and dp[1] = 2.

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

This was a hacking contest. 1 integer input problems for C,D. "7" and "9" were hack cases for D.

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

I've attempt to hack div2 A using the following test input, on the codes that did not handle negative indices (for example, 22533346):

5 4
TG...

However, they output correctly. Is there something I have mistaken?

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

hack.JPG

At first: Thank you for hacking :D.

A few minutes later: Sorry for hacking :(. I don't want to lose my rating (significantly).

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

    Hack-ers aren't cruel at all, what is? Seeing a wrong solution and ignore it! :v

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

Solved D for the first time! I hope it will pass system test. :)

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

Dooms Contest :/ GG Rating

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


I wonder how this guy might be feeling after hacking 5 solutions for D and getting hacked back by one of those users.

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

    awful contest!!! especially for problem div2 D , it needs to know Goldbach's conjecture. Is it related to problem solving skill?!???

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

      I do think that Goldbach's conjecture is a kind of common sense instead of solving skill.

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

    I don't know about him but bvd is very relieved after getting revenge I think.

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

I'm sorry to tell, but truth should not be concealed : Awful problems on C and D (they don't deserve their intended points) :(

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

    Couldn't agree more.

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

    I agree. Almost no algorithmic skills were needed to solve these two.

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

      Actually contests require problem-solving skill, not only popular algorithms and data structures :D

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

    I think C is ok. It's something you can figure out with a piece of paper, D is just about whether you've encountered the conjecture or are googling during the contest.

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

    What's wrong with C?

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

I got disappointed with my result in this contest. I am pretty sure I have become better in algorithms as I usually practice in TopCoder. According to the new rating in Codeforces, I got moved to Div2. Then, I decided to participate in this contest to reach div1 here, too. Generally, I have difficulty with these kinds of problems since instead of thinking about algorithms, I am forced to find corner cases. I don't really like these kinds of problems though I have the great respect for the author.

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

i used this code for problem C i got WA in pretest 7 any idea ?

while(n>1){ if((n%2)==1){ans++;}; ans++;
n>>=1; }

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

    For Problem C I think it's a fibonacci problem.

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

      Could u please explain it ?

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

        Yes I can.

        We define f(n) to be the minimum number of players required such that the winner can play n games at most.

        So the ideal situation(to make the number of players minimum) is that the last game the winner played is with another player who played n — 2 games already(since the winner played n — 1 games at this point).

        So we have: f(n) = f(n — 1) + f(n — 2)

        then the final answer is just the maximum number m which satisfied f(m) <= tot_number_of_players.

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

else A&B(div1) problems were fun.

thanks.

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

    Yes, both A and B are terrible. I wouldn't recommend them to anyone of any level. Maybe if the author used only one of them it would have been suited for Div.1 A

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

My friend just told me that he solved C and D (Div.2) by finding other peoples' codes on ideone. This is so unfair -_-

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

    If it is matched with some other code that submissions will be skipped :)

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

      If people are smart enough to find codes on ideone, they will definitely modify it as they know about this dirty trick. I was surprised to see the rising submissions for C and D.

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

    Report him.

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

    Since when did this start happening on codeforces? Same author, Same problem.

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

      How is this even possible ? is the author foolish or something ? How can he repost one of his own problems ? Lol

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

      the contest should be made unrated . Div1 A was copied and Div 1B was google-able :(

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

        kingofnumbers was right in his blog for which he faced so much criticism. The author of this round did not even care to change the title of the problem. -_- People cheating from ideone and authors making one problem googleable and one problem exactly same(again googleable). Bye bye albertg. Hope this second round is your last round.

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

    this not convincing reason to make unrated this mean that they have to make all previous contests unrated

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

      there he is ^
      lol i'm such a shitty friend

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

        who are you -_- I don't even know you -_-

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

          Bro, if you want people to believe you, at least don't make any more lies that I can easily prove wrong
          Come on, you gotta be smarter than this!

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

      So you want to cheat from ideone and then fight for whether the reason is convincing or not to make the round unrated?

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

        I didn't cheated you can confirm from my status -_-

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

Did anyone used prime numbers to solve D?

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

    Yeah (D2 D was the same as D1 B). The key insight is the Goldbach conjecture (any even number >2 is the sum of two primes).

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

    Yes, I am

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

Problem D/B be like:

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

problem D can anybody google it

this is unfair

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

    Yeah, no problem is fare. Or did you mean fair?

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

in problem C:

"Don't miss the unusual constraint for k."

is just a lie :|

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

Hope I can jump to div1 for the second time.

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

Div.1 A I wonder how many people could google this http://www.spoj.com/problems/TENNIS1/ during the round.... -_-

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

I've actually learned something new from this contest, thanks!

1) Google exactly the problem statement because apparently... you might get lucky (same author, same statement)

2) After #1 is done... you know what to do next

3) If everything fails, try checking other people's code on ideone.com because apparently... well, you got the idea

Go Googleforces!

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

https://www.quora.com/What-is-the-best-way-to-solve-SPOJ-problem-code-TENNIS1

HELLO FROM 2K15 BOYZ

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

this contest reminds me of april fools day contest :D :D

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

    Actually April fools day contest is more interesting than this contest.

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

Is it fair to repeat your already existing problems? albertg

http://www.spoj.com/problems/TENNIS1/

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

I don't want to sound rude or anything, but this contest was very bad and in my opinion should be unrated, and I'm not saying that just because I participated badly. The main reason is that problem C was on SPOJ — link and was posted there by the author of this contest! Anyone could just google it. Also D was an ugly problem, and the only way to solve it was to either somehow already known about Goldbach's conjecture, which is not all that well-known, to search it on google which shouldn't be a way to solve a problem, or to guess it, which would be just luck.

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

    For D, If someone is able to deduce that answer will equal to minimum number of primes whose sum is equal to n then google search will take you to Goldbach's conjecture. So I feel it's ok. BTW it was similar to Dima and Lisa which was blocked during contest.

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

      Deducing that was easy for a D level problem, the hard part of the problem was finding the number of primes, so 90% of the problem was solved through google

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

      Are we supposed to be using Google during contests?

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

    I didn't know about Goldbach's conjecture, so I bruteforced the first few answers and OEISed them. Still bad though

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

Div 2 D is just the same with #324 div 2 D. (http://codeforces.net/contest/584/problem/D)

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

    In this round's problem you have to prove that you should only pick primes. Minor difference, but at least something

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

While it's true that the author may have used one of his own problems and this was a mistake, it's important not to consider the entire contest as bad just because one or two tasks were not optimal. It takes a lot of time to prepare these contests, especially for both divisions, so at the end of the day, we are all in the author's debt, not the other way around.

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

    Although I didn't participate but we aren't talking about optimality here. You were an author before and you know it's not an easy task to come with the problems but you also know that it's a huge responsibility, in case it's a dup problem we can excuse him assuming he didn't know it existed but here he was the author and it had been there for 2 years.

    There was no problem solving in Div2 D also just using a well know theorem.

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

    Not really. Authors are paid to create problems for a contest, and if they are reusing one of their older public problems, they are basically cheating.

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

make it unrated is the most stupid thing CF can do

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

I don't participate in one contest and the freaking problem D can be done with the Goldbach Conjecture , fml.. They should make it unrated, this isn't fair!

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

One of the problems was a straight copy, and the other one was a google search problem. Making this round rated cheapens the value of one's rating.

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

In Div1-D, is it enough to check for each relation if it is contained in exactly one valid permutation?

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

    I solved using the following:

    Let A be such matrix that Ai, j = 1 if permutationi can equal j, and 0 otherwise.

    We know that the number of all valid permutation is a permanent of A, and in . So we have to check for some queries (x, y) that Mx, y = 1 (in , here Mx, y is the respective minor). It's known that Mx, y = A - 1y, x, so we just calculate A - 1 for n3 / 32 and win.

    UPD: and A - 1 exists since .

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

is contest rated?

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

Actually, problem D is the direct application of Goldbach's conjecture. I think this is the 'ABC' in the world of math/number theory.

I remembered that I've learned this when I was really really young, maybe the time when I was a primary student or a middle school student.

Even though, I failed to come up with this quickly in the contest and tried several wrong ideas, wasting my time.

From the view of problem setting, I don't think this problem (as well as C) is good. I think people don't want to train their knowledge of commen sense in problems like D in div2. These problems can be better if they engage more thoughts. As for me, I enjoy harder D, even if I can't solve it.

But from the view of a problem solver, I think div2D is still good problem. It reminds us that we should not forget the most fundamental thing when we are solving hard problems. If tourist competed in this round, I think he would solve div2D easily. We as problem solver should think of how we can deal with such problems quickly under adverse condition instead of complaining about it. Life is not always fair, right?

Anyway, thanks for the problem setters. It is not easy to prepare a contest. And somehow, it is not easy to come up with easy problems. Hope the next round will be better and I can become purple. :)

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

Regarding the repeated problem issue, if I were in charge I would zero out all results from 1A/2C but not unrate the entire contest. The problem lies exclusively in a single question, and yes it is a major problem, but it's not like all of the questions leaked or anything.

Also, some here are saying 1B/2D was "unfair"; I have to say I personally disagree, with the caveat that maybe this wasn't the best problem to have in Div 2 because of this. Yes, 1B/2D relied on some knowledge/research -- but in the end, what harder problem doesn't to some extent? At the ICPC Mid-Central Regionals, one of the hardest problems anyone solved (and, in the end, the one that put my team over the top to go to Worlds) seemed intractable -- until, that is, I realized that the problem of deciding whether a given power level is possible reduces to 2-SAT. Without knowledge of 2-SAT and its reduction to the strongly connected components problem, this problem would be impossible to solve. In addition, most geometry problems have some innate knowledge requirement in order to reach the key insights involved. Maybe this problem was a bit irksome because its knowledge difficulty was above its algorithmic/implementation difficulty, but overall I don't think it was a bad problem (though, again, maybe it should have been replaced with something else for div 2).

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

    But some people spent most of the time thinking about it, wasting the time which they could've spent searching on google D's solution

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

    What about someone who had no idea about the repetition of problem C and solved it by himself giving maximum of his contest time? Will it be fair to zero out his accepted code?

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

Look at the code of winner of div2 round. Who uses DPDPDP as a variable? I wish there was no find and replace option built.

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

    I guess it turns out that KSL who was previously first place cheated. Maybe people downvoted you a little too early, because there definitely was something fishy about that guy.

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

blokes ya just have butthurt cuz you didnt solve these problems. great contest, well done.

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

Hi. Can anyone help me with div.2 B? My code works fine on my computer, including the first test case. But on codeforces the output is -2 on first test. http://codeforces.net/contest/735/submission/22553933

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

    I think you algorithm is incorrect to begin with. The correct answer is taking the first min(n1,n2) to the smaller set and the next max(n1,n2) to the larger set.

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

      Thank you, but I swap the values if n1 > n2: "if(n1 > n2) n1^=n2^=n1^=n2;"

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

    change long double to double

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

      Thank you very much! But why is it so?

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

    You shouldn't have used long double. Make the sums with long long and then cast to double when printing... Got AC here with it: http://codeforces.net/contest/735/submission/22558151 :/

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

      Could you also tell me why long double didn't work? edit: I googled it.

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

        I think there is a problem with codeforces and long doubles. I also submitted with long doubles and had WA in test 1. Better use double.

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

        Well I don't know the actual size/range of long double but it seems like some kind of weird overflow (? overflow with sum 6?? lul wut??)

        Looked it up and on wikipedia they basically say it's unspecified so I guess it's better not to use it on contests... I recommend always using long long and cast, works well for me :s

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

In my opinion, tests for problem D are not enought. Some accepted solutions are checked only prime numbers to 1e5. I think there are no complete test cases.

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

Why do people use Google during the contest in the first place? And if one uses the argument "everyone else is doing it" then how different is that person from all the other googlers?

Correct me if I am wrong, but the purpose of these contests is to hone one's skills. Although the problem setter made a mistake posting one of his own problems, take into consideration that the author took his time to put this contest together.

Without using Google, I find Div. 1 A&B very reasonable. It definitely took me more time to come up with Div. 1 A but I came up with that so why should I care that someone looked it up online. I didn't even know about Goldbach's conjecture but managed to solve B with some kind of brute force. It seems that the problems were more or less balanced if not for the googlers. But googlers are googlers, why should one compare himself or herself to them.

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

    Agreed. Your non-Goldbach's conjecture version makes me feel better about that problem.

    There's never going to be a way to stop people from cheating anyways.

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

I spent most of time working on problem D... There seemed to be a fancy conclusion as the solution to problem D, but I hadn't got it. Umm... I should improve the level of knowledge.

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

why my code got WA in test 11 Div2B

submission

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

    I think overflow in sum1 and sum2 might be the problem here. Try using long instead of int.

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

How to solve Div 2 E / Div 1 C?

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

Does anyone know why the problem C of Div.1 use unusual constraint for k?

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

    There is a solution with O (2^k * n).

    We iterate over the vertexes, which will be painted (this vertex is removed no more than k from the root), brute over her mask and update dp.

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

    Personally, I don't see why it's considered unusual?

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

      I say it is unusual because the statement say that. And I cannot think out one solution using this constraint. My solution can be done in O(n^3). In order to use the constraint, I take some time in thinking it bug I give up in the final.

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

    There is O(n·k4) solution. Dynamic programming with dp[2][n][k] — the number of ways to fill a subtree that either the topmost black vertex is at some height or the topmost non-satisfied white vertex is at some height.

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

Just googling round)

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

thanks the author for ruining my 2 hours:/

i should have participated in HR ICPC contest :(

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

    All problems there were OLD HR problems :) People Googled/Searched HR archive and submitted :) So, by your logic, you would have complained about HR contest too!

    So the best solution for you would have been shutting down your system for the time being :D

    It's better to stop complaining and learn :)

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

      If you cared about improving you wouldn't say that (unless ofc you have solved all the problems on hr)

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

waiting for Edtutorial just to give you your deserved downvote

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

Wow, they actually made it rated.

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

Did anyone take advantage of a problem div1A being googlable? There is no editorial or any comments under that problem. I've just tried to submit a solution there and got ERROR — so I guess it wasn't possible to test one's solution by submitting a problem there. The only possible issue I see is that someone may have already read that statement. There is a tag "hidden" though and maybe it means that a problem isn't showed in the global list of problems. Still, maybe someone managed to find it in some way before, but it doesn't look like a likely scenario.

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

    Uh the solution is on quora.

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

    Erm... https://www.quora.com/What-is-the-best-way-to-solve-SPOJ-problem-code-TENNIS1

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

    This author should be banned permanently for giving the same problem twice. There should be no reasonable explanation for such behaviour. Giving one more problem on "Goldbach's conjecture" totally sucks as well. This round is ridiculous.

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

      Yeah, also take a look at his other problem on SPOJ. Not an exact copy paste as in Div1-A, but it requires Goldbach's conjecture. I wonder why he would need to copy-paste and/or re-use ideas from his own problems. This is utterly absurd.

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

      I can understand giving a problem which appeared before, you might not know about it, it happens from time to time. But when it's YOUR OWN problem...

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

    I didn't know that a solution is described somewhere. Ok, then it's a bad situation.

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

Codeforces really wants me in div1 :)

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

well, the round is rated for both division, same shity problem for the same author and with the same statement
everything is fine , don't you think that at least we own you an apology ?

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

    Cmon, problem C div 2 was nice. The only mistake imo was to copy the exactly same statement.

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

THIS IS RIDICULOUS!!

Most contestants are complaining that problem A Div.1 is repeated with the same statement and the same author & problem B Div.1 can be googled easily and all we can get is IGNORANCE..

I downvoted the contest, it should be UNRATED!!

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

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

    Yes, the ratings have been published already mate. It is RATED.

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

This contest is just terrific!

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

    Wow, another account standing in the "Ban queue"! :D

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

    you didn't do this round, why you are so emotional now? My dear "Trump"

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

now , i think that Edvard is the only Armenian author in codeforces . :3

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

Just for fun: problem with (a bit) similar idea to D2-D / D1-B: https://community.topcoder.com/stat?c=problem_statement&pm=11607

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

I wonder if albertg will write an editorial for Div1/A or he'll just post the Quora link.

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

Let's make the contest editorial post the most downvoted post on codeforces....

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

I'm poor in math; Then I got a 75 ratings decreasing..; Horrible math....; However,This is a Nice round; Thank you! (I'm poor in ENGLISH too.TAT)

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

I thought it would be unrated, maybe I will back to blue when I wake up tomorrow ...

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

I like mathematics so I think C and D were good problems. Maybe it was too easy to copy them from google but beside that they were interesting and challenging.

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it -62 Vote: I do not like it

albertg Here is a list of "Things to Do":
1. Apologise CF community for your behaviour and laziness to not even change the problem title.
2. Request Mike to make this round unrated.
3. Live with the curses of people affected by this round.

CF should have not make this round rated. I will definitely move to AtCoder, Codechef, Hackerrank and CSAcademy. But now-a-days, frequency of contests has decreased. Can anyone suggest other similar sites that hold frequent contests with their standards maintained and proper and genuine problem setters.
Anyways, here is the link to downvote this guy.
EDIT: Reply to all saying I have only 1 submissions. "This is obviously my secondary account. To all the people ready with questions like, "Why do you need to comment from your fake account? Do u fear to reveal your identity?" I have the answer: "I get downvoted for no reasons from my main account. Plus I need such account to enjoy contests and do not let my div1 rating to go to div2.". Why am I so mad? Because I can't use the coach account and see test cases of gym problems. Plus I am an addictive coder at heart and love my rating. Hope I clear your doubts."

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

    Well if he does 1 and 2, 3 will be invalid since noone will be affected anymore. Also I think CF is good, only that sometimes mess-ups like this happen. We all make mistakes. Although when we make mistakes we shouldn't take this long to make an apology...

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

    "I will definitely move to AtCoder, Codechef, Hackerrank and CSAcademy"

    You have exactly one submission on this site. I wouldn't exactly call that moving...

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

    You participated in 0 contests and you have exactly 1 submission in Codeforces. Moving to other platforms won't affect CF much.

    Why would you want to downvote an editorial? Do you want it to disappear (at least from the "recent actions")?

    That being said, I also think that an author behaved badly.

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

    This is obviously my secondary account. To all the people ready with questions like, "Why do you need to comment from your fake account? Do u fear to reveal your identity?" I have the answer: "I get downvoted for no reasons from my main account. Plus I need such account to enjoy contests and do not let my div1 rating to go to div2.".

    Why am I so mad? Because I can't use the coach account and see test cases of gym problems. Plus I am an addictive coder at heart and love my rating. Hope I clear your doubts.

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

      I get downvotes for no reason regularly. Once, I made a contest announcement and quickly got it downvoted. So I made the same contest announcement again — because I don't care about an e-penis (contribution), just about what I write being seen.

      Maybe you should move to Reddit instead, it seems more up your alley.

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

        Nice comparison. Btw. that feeling when you have e-penis smaller than a woman (gKseni).

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

          That stands in direct contradiction to Rule 30, though.

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

So, Problem C div2 / A div1 apparently is http://www.spoj.com/problems/TENNIS1/

The author is the same btw.

And this problem is hidden from the site because of its unclear statement.

My solution was ceil(log2(n)) which I think is right.

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

    Same, I missunderstood the condition and many people did too... Although on this I'm gonna blame myself for not being careful, the author has enough blame on him already.

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

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

Screencast: click

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

Also today’s DIV1 E was actually the same like this problem http://informatics.mccme.ru/moodle/mod/statements/view.php?chapterid=714#1. You just needed to add two more cycles.

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

I think the author wanted to make an Educational Round but accidently published it as a regular round :3

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

One of the worst contests I have ever participated in xS

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

I love math so much and I want every contest be like this (not)

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

I think there is problem with editorial link.

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

    The contest with the largest no problems ever

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

I've read all the comments and very upset about the situation. I told to writer and asked him to describe here how it happened. The situation with 736A - Tennis Championship is very disappointing. I'll announce the decision about the rating as soon as I decide something.

Sorry for the issue.

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

Why did this code not get wrong answer on a test like 100000 50000 50000 and with al the numbers equal to 100000 given that 5*10^9 is bigger than maximum int? no overflow

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

Zlobober We need more rounds from you ! :(

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

Hey, can you please explain me the difference between the various problems A,B,C,D,E ? Are they different in difficulty? Or there are just of the same difficulty but based on different topics? Or both? Hope you dont't mind. Thanks :)

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

    They should be ordered by difficulty. I mean A < B < C < D < E. Nonetheless, it is not always so. With respect to the topics, they are usually different, but A and B are often implementation.

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

I demand justice! I solve and solve and no point from C. Also I see it copyd from elsewhere. Make it unranked or I leave site!!1

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

What am I missing here ? :(

22565660

Problem : 735C - Tennis Championship

→ Reply