By Miyukine, 11 months ago, In English,

Hello everyone! The first round of the 8VC Venture Cup 2017 will be held on Sunday.

I am honoured to be the problemsetter of the round. Reyna helped me a lot. Huge applause to KAN for his valuable coordinator's help, and MikeMirzayanov for his admirable work for the Codeforces comunity. I also want to thank testers very much (Alexey ashmelev Shmelev and Alex AlexFetisov Fetisov).

This round is a first stage of 8VC Venture Cup 2017. If you want to acknowledge yourselves with the competition, try here.

The main character of the round is PolandBall. It's a small friendly Ball who lives in a forest along with other Balls. You'll surely like it :)

I tried to fulfill your demands with a various, interesting and challenging problems described in a concise way.

Hope to see you soon, good luck and have fun!

UPD1: Scoring 500100015002250250027503500.

UPD2 Thank you for participation! Contest is over. Did you like the problemset? Feel free to comment =)

UPD3 Editorial

UPD4: Winners

  1. tourist
  2. moejy0viiiiiv
  3. W4yneb0t
  4. ilyakor
  5. ainta.

Hope you've had a good time with PolandBall solving the problems.

Congratulations to all the winners and TOP-200 who advances into 8VC Finals =)

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

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

will be 7 or 8 problems?

  • »
    »
    11 months ago, # ^ |
    Rev. 2   Vote: I like it -15 Vote: I do not like it

    7 problems. We will inform about the scoring later.

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it +43 Vote: I do not like it

      With only 2 hours? Are you sure it would not be better to extend to 2:30 or 3:00, most rounds with 7+ problems are longer than usual I think.

»
11 months ago, # |
  Vote: I like it +9 Vote: I do not like it

7 problems in 2 hours, I think it will be great contest

»
11 months ago, # |
  Vote: I like it +46 Vote: I do not like it

Börk, börk

What a cute polan! I decided to take part in this contest.

»
11 months ago, # |
  Vote: I like it +103 Vote: I do not like it

Give him a hat, and now he's become Indonesia ball

»
11 months ago, # |
  Vote: I like it +11 Vote: I do not like it

So this is Voltorb's round. Really excited about it.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Rating for div2?

»
11 months ago, # |
  Vote: I like it +21 Vote: I do not like it

"I tried to fulfill your demands with a various, interesting and challenging problems described in a concise way."

Now I really have something to look forward too ^_^

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +58 Vote: I do not like it

    Concise challenge:

    "Can Poland into space?"

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      Hahahahahaha,that's great.

      I don't know why this meme originated. Poland has already had an astronaut in space.

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

      Yes, we can. In 1978 Miroslaw Hermaszewski was in space thanks to the INTERKOSMOS program.

»
11 months ago, # |
  Vote: I like it -7 Vote: I do not like it

It's 2:05 AM in my local time.. too late .. sad ;(

»
11 months ago, # |
  Vote: I like it -7 Vote: I do not like it

Will it be rated?

»
11 months ago, # |
  Vote: I like it -11 Vote: I do not like it

Is everyone who can participate in this contest?

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

community*

»
11 months ago, # |
  Vote: I like it +8 Vote: I do not like it

poland ball <3

»
11 months ago, # |
  Vote: I like it -20 Vote: I do not like it

Balls War 2

»
11 months ago, # |
  Vote: I like it -12 Vote: I do not like it

-

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I tried to fulfil your demands with a various, interesting and challenging problems described in a concise way.

Grabs popcorn and wait for comments whining problem C/D is too hard again.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Excited about the contest... All the best Miyukine for your first contest as an owner. Loved last contest of KAN. The problems were really good. Hoping for the same.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

7 problems,2 hours :/

»
11 months ago, # |
  Vote: I like it +115 Vote: I do not like it

kurwa

»
11 months ago, # |
  Vote: I like it +21 Vote: I do not like it

Is it rated or not?

»
11 months ago, # |
  Vote: I like it -29 Vote: I do not like it

As I understood, there will be 7 problems, Div1 and Div2 combined. As 2 hours isn't too much time for 7 problems, I think that I have to choose between Div1 and Div2 and I'm not gonna solve all the problems. If I misunderstood something, please someone explain it to me.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Long Live CODERS...

»
11 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

sorry you missed :: The scoring distribution will be announced later ;)

»
11 months ago, # |
  Vote: I like it -43 Vote: I do not like it

is it rated ?

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

    just do well and codeforces will increase your rating or verse versa .

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

now, should I do the contest or watch Liverpool vs Manchester United :/

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

    both of them XD

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it -16 Vote: I do not like it

      i will play the match in the background , and watch the dangerous attacks; the contest will start at the same time with the second half of the match; So we can enjoy the first half :) <3

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

    you can participate in the contest then watch the highlights while ratings are updated. The best way to get rid of complainers about ratings being late:D

»
11 months ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

is this a rated contest? ok i got it its rated

»
11 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Will tourist's comment be upvoted or downvoted if he askes "** ** *****?"

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +45 Vote: I do not like it

    Of course upvoted, he's tourist

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    I don't think he's a rating addict. :)

»
11 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Tomorrow at 12:00PM(BDT) is my Algorithm exam and today at 11:05PM(BDT) 8VC Venture Cup 2017 — Elimination Round. As I am not known of so many topics of my course I choose to participate this contest. Hoping my color will change.

  • »
    »
    11 months ago, # ^ |
    Rev. 2   Vote: I like it +14 Vote: I do not like it

    Totally same situation about exam, but I hope my color won't be changed :)

»
11 months ago, # |
Rev. 3   Vote: I like it -83 Vote: I do not like it

Is it Rated ? got it. It is rated

»
11 months ago, # |
  Vote: I like it -6 Vote: I do not like it

The contest starts in 18 minutes. Good luck all!

»
11 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Solution for A stays queued for 5 minutes, help

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

    same here

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

    Custom invocation isn't working as well. EDIT — It works now!

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

    Got 2 WA's which I could've fixed WAAAAY sooner if they didn't stay queued for 10 mins :(

»
11 months ago, # |
  Vote: I like it +25 Vote: I do not like it

»
11 months ago, # |
Rev. 2   Vote: I like it -6 Vote: I do not like it

Problem-B's statement should more clear . It makes a lot of confusion.

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

    Why do you think the statement is poor? We didn't need to clarify it any single time. You could've asked a question.

    • »
      »
      »
      11 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Nope.I solve it with simple approach.Making no sense both are playing optimally, i think.

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

      To play optimally, a player has to know, that the opponent knows that word too. I read the description a few times searching for that sentence, but then just assumed it to be true.

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

    I think so.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I have a confusion please, in the first problem , should we print all m so that n*m + 1 wont be a prime number ?

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

    No, just only any of the m so that n*m+1 wont be a prime number.

»
11 months ago, # |
  Vote: I like it -35 Vote: I do not like it

Is this contest rated???

»
11 months ago, # |
  Vote: I like it +36 Vote: I do not like it

Definitely the best contest in a while, thanks for the very nice problems :D

»
11 months ago, # |
  Vote: I like it +11 Vote: I do not like it

It's the most beautiful contest I ever seen.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What was the hack for D?

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

    i have the same question

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    5 3

    Answer should be equal to the answer for 5 2

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

      Phew im safe

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

        Well that was hack 1 for me. Hack 2 must have been the 10^6 case.

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

      damn i will get failed too

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

      Im crying now.

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

      Well, at least that's the first time I came so close to solving D during the contest time.

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

      Fu.........................................nny, didn't think of that.

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    1000000 499999 => many used int for result

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

    12 7, you should have k = min(k, n-k), unfortunately i will be failing for this reason

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

    I firstly use 1000000 999997 because I think it will cause Int overflow. However, the true answer is not cause Int overflow but most people failed this hack.

    The answer is 2 3 4 ..., but most people (including me, print 2 4 8 ...).

»
11 months ago, # |
  Vote: I like it +11 Vote: I do not like it

How to hack A?

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

    Some people used m=n+2. But this is wrong when n=999 or n=1000 since m must be <=1000. So they have to handle that case separately.

»
11 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Hack for Div2B:
2 2
a
b
b
c
Hack for Div2A:
330 or 726

»
11 months ago, # |
  Vote: I like it +12 Vote: I do not like it

Whats the logic behind D ? Also, I have a feeling that a lot of D solutions are going to fail.

  • »
    »
    11 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    My logic (though it TLE'd on hack 2), was simply to check the number of diagonals from vertex x to vertex x+k that have been drawn, and add to the answer (1 + number of diagonals). However, I kept track of diagonal through a circular array that I was traversing everytime, so it must not have fit..

    Weirdly...the 10^6 case passed on my system

    Edit-nvm, the case did not pass. I'm an idiot >.<

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

    Here's my soluton.

  • »
    »
    11 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    The amount of segment changes by 1 + (amount of other diagonals crossed). Each diagonal connecting the i-th and j-th node nesessarily crosses all the diagonals in range (i+1, j-1).

    Just use the segment tree to store the diagonals in each node. When you add a new diagonal (i,j), increase the amount of diagonals in i-th and j-th node by 1 and calculate the answer.

    Here is the example: http://codeforces.com/contest/755/submission/23866075

    (unfortunately, i didnt realise the int overflow during the contest)

»
11 months ago, # |
  Vote: I like it +24 Vote: I do not like it

Was Problem F checking if subset sum = k for min and greedy for max?

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

    Yes. Is there any solution for F faster than N*sqrt(N)?

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

      Bitset... I still think I will TLE though.

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

        Is there some way to create a bitset like this instead of creating a custom bitset object?

        int x = something;
        bitset<x> b;
        
        • »
          »
          »
          »
          »
          11 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Just make it larger than the largest it needs to be ; )

          Templates are evaluated at compile-time, so you can only do that to consts.

    • »
      »
      »
      11 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Actually even well written N sqrt N can pass.

      It's possible to do (N sqrt N)/32, however. See tourist submission.

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

        tourist submission is actually , in this order of nesting. There's an loop (for each cycle length i), then there's an loop (subtracting powers of 2 from cnt[i]) and finally an O(106 / 32) shift+or operation. Would you please explain this solution?

  • »
    »
    11 months ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    I think so, but I got WA with this approach.

    EDIT: I guess I have a bug. :/

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

    Yes. I got AC using Monte Carlo Method and letting it run for 10 ^ 6 iterations. Basically, you keep a set of active elements, as well as the sum of the numbers in that set. At each iteration, you either:

    1. Stop | If the sum is equal to k.
    2. Deactivate a random element from the active ones | If the sum is greater than k.
    3. Activate a random element that was inactive | If the sum is less than k.

    At each step, you also need to update the sum of the active elements. The code is simple enough, you can check my code here, though I wrote it in a rush and it's a bit more complicated than it needs to be.

    This method has a very high probability to find an answer, if it exists, given enough iterations.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For E, What's impossible case for n, k?

»
11 months ago, # |
Rev. 2   Vote: I like it +25 Vote: I do not like it

Am I right that in F we have to solve knapsack problem? Is it solvable with FFT (either using forward transforms for all, and only one backward, or successively multiplying the smallest arrays)? I doubt it will fit into time limits.

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

    You can solve the knapsack in O(k*c), where c is the number of different cycle lengths you have, so c=O(sqrt(n)).

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it +37 Vote: I do not like it

      I did that and passed pretests in 700-800ms, but this problem has a reduced TL (1.5s compared to the standard 2s), which is very odd considering O(N*sqrt(N)) for n = 1e6 is already 1 billion. I think the time limit and constraint on N made many people not even consider this solution.

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

        Well, you can do that with bitset which is significantly faster

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

          Can you, please, give a link or explain how to use these /32 or /64 optimizations with bitset?

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

            check someone's code for that problem e.g mine

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

      It's 10^9 and I believed it's too much.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

4th Very weak pre-test cases.

Hack: Long Long overflow or k > (n-k) eg 7 4.

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

    naive O(nk) solution also passed pretest

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

    Long Long overflow Oh shi~

»
11 months ago, # |
  Vote: I like it +8 Vote: I do not like it

i submitted my solution for problem D at the last second . i mean i hit the submit button and after it displayed the end of contest . but its not showing my submission !

»
11 months ago, # |
  Vote: I like it +222 Vote: I do not like it

2k > n in D

»
11 months ago, # |
  Vote: I like it +83 Vote: I do not like it

F is like the worst problem one could give for a contest.

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

    Why?

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      Because the intended solution is Nsqrt (N) for sure. It reduces to knapsnack problem with limited sum which is solved in Nsqrt(N). F was really nice but with very bad limits...

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

        Of course it is reduced to knapsack but I think that it was intended to also use bitset and make it . Why is it bad that you need one more small approach in one of the hardest problems of the contest?

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

          Well I thought about that(with 1/32 constant), but it is not actually Nsqrt(N)/64, because just one part of the algorithm can use bitset at its maximum, so its more likely something like Nsqrt (N/64) which is not a very good or relevant improvement. And the problem was really nice without it

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it +46 Vote: I do not like it

      I never enjoy solving something that looks 100% like the problem that appeared before, where a lot of people know the idea. It fits for educational rounds, but not rated ones.

      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        It cannot be ensured that all problems have never appeared anywhere.

        Believe me, Codeforces staff and writers did their best to make the round enjoyable.

  • »
    »
    11 months ago, # ^ |
    Rev. 2   Vote: I like it +17 Vote: I do not like it

    Why? I really enjoyed solving it, and the idea (of optimizing knapsack with repeated items to perform log(cnt)^W O(1) passes per item, not cnt) is beautiful, I don't remember seeing it before..

    (all this assuming my approach is correct — we'll see soon if it is the case)

    • »
      »
      »
      11 months ago, # ^ |
      Rev. 2   Vote: I like it +20 Vote: I do not like it

      I'm not defending Al.Cash's statement that this problem is the worst one ever, however I've seen the idea of replacing cnt objects with log(cnt) ones many times in the past (at least in 3-5 different problems).

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

        OK. Less activity in contests => forgetfulness => more fun solving problems even if ideas aren't original :)

      • »
        »
        »
        »
        11 months ago, # ^ |
        Rev. 2   Vote: I like it +20 Vote: I do not like it

        Replacing cnt objects with log(cnt) ones? If I understand correctly, you're talking about an O(n*sqrt(n)*log(n)) solution, not O(n*sqrt(n)).

        Do you mean you take, say, 10 objects of size 3 and replace them with 1 of size 12, 2 of size 6 and 2 of size 3? So instead of k objects of the same size, you have O(log(k)) objects of some other sizes, and the same solution set?

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

          I passed with this idea with really small running time (327ms), is this solution supposed not to pass?

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

            My N*sqrt(N) implementation barely passed and you're saying that it exists a Nsqrtlog implementation that passes as well? How is that possible?

            • »
              »
              »
              »
              »
              »
              »
              11 months ago, # ^ |
                Vote: I like it -15 Vote: I do not like it

              This is N sqrt N log theoretically. However, it can be proven that some applications of this method are still N sqrt N. Look at POI 20 booklet, problem "Polarization"

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

              I don't know about O(N*sqrt(N)) solution but it is probably because high constant factor of O(N*sqrt(N)) and low constant factor of O(N*sqrt(N)*log(N)), actually it's not possible that both sqrt(N) reach 1000 and log(N) reach 20 at same time.

              UPD: ok it seems it's O(N*sqrt(N)) as mentioned by AlexDmitriev here

            • »
              »
              »
              »
              »
              »
              »
              11 months ago, # ^ |
              Rev. 3   Vote: I like it 0 Vote: I do not like it

              I'm looking at your code: http://codeforces.com/contest/755/submission/23860782 and currently I believe it has quadratic time (e.g. when we have two stacks of O(n) size).

              Upd. I see, "break" in the innermost loop prevents it from happening.

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

          It will be still O(NsqrtN) because after replacing they have still N as their sum (and at most O(sqrtN) different)

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    Maybe, but in this contests it happens to be the best problem

  • »
    »
    11 months ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    Agreed.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My performance was so bad , however I have to admit that the problems where really so good and short. Thanks :)

»
11 months ago, # |
  Vote: I like it +21 Vote: I do not like it

Using int in problem D :) good bye cruel world

»
11 months ago, # |
  Vote: I like it -10 Vote: I do not like it

Awesome round, Kacper! Thanks :)

»
11 months ago, # |
  Vote: I like it +31 Vote: I do not like it

WTF was this contest!!!!!

»
11 months ago, # |
  Vote: I like it +57 Vote: I do not like it

Feeling proud after making hack for a red one 'D

»
11 months ago, # |
  Vote: I like it +21 Vote: I do not like it

I know lots of people will ask how to solve A so here is the solution:

answer is min(999, n+2)

»
11 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Why not 500 — 750 — 750 — 1000 — 2000 — 2500 — 3000 or dynamic scoring? Hacks have very low cost otherwise.

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

    But then by not putting 2*k>n case in pretests you can't completely ruin the contest for some people

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

    Oh, hacks are already worth way more than they should be, lol.

    Locking D and feeding on people who used int or didn't watch out for 2k > n should give nowhere near as much points as correctly solving another problem, but it does.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I haven't read D for long time because it marked as 2250 — difficult, but it was not... :(

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

    Where did you see the label "difficult"?

»
11 months ago, # |
  Vote: I like it +5 Vote: I do not like it

tourist got penalty on A :o

»
11 months ago, # |
  Vote: I like it +11 Vote: I do not like it

"Idleness limit exceeded on pretest 4" What does that mean and why did the exact same code pass the tests later (giving me -50 points for wrong answer ans some more minus for slow solving)? http://codeforces.com/contest/755/submission/23846772, http://codeforces.com/contest/755/submission/23851648

»
11 months ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

Dear authors / pretest makers of problem D, you are both evil and awesome! =D

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What could be the reason of WA5 in G?

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

    I don't know. This is a maxtest, nothing special in it.

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

    Use Custom Invocation to check your running time on Codeforces machine.

    Mine running maximum test in 8.7 sec :(

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

    Maybe divison by 0 (n could be larger than 998...)

  • »
    »
    11 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    In my case the problem was following: I tried to store values of dp(N,  * ) in fft-transformed way to avoid running transformation twice on every step. However, at some point it may happen that dp(N, j) for j > K is non-zero which means on the next step it'll screw up the result (as it won't be a product of required two polynomials anymore) so I needed to explicitly set dp(N, j) = 0 for j > K.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What if i submitted a correct solution then submit one more solution which pass pretest but is hacked (previous submission is correct) what will happen :( (changed long long to int to save memory in D and resubmitted)

»
11 months ago, # |
Rev. 2   Vote: I like it +25 Vote: I do not like it

From 950 pretests passed to ~400 accepted. Nice pretests and evilest cases in D :(

»
11 months ago, # |
  Vote: I like it +10 Vote: I do not like it

D so many fst ....

»
11 months ago, # |
Rev. 4   Vote: I like it +36 Vote: I do not like it

Don't you think D is a bit too harsh?????????

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for beautiful problems! I enjoyed a lot and it was the best round I have ever participated in CF

»
11 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

That feel when you drop from sub-200 to 340 because you were too lazy to write a sieve for A :'''''''''''(

EDIT: nvm i scanned up to sqrt(n) instead of sqrt(n*m+1) >>>>.<<<<

  • »
    »
    11 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    why would you need sieve? the constraints are pretty low. n*sqrt(1000001) should pass just fine.

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

      n*sqrt(1000*1000) = n * 1000 it is, but still ok

  • »
    »
    11 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I managed to pass with 2 for-loops in 15ms though, how did you get TLE :/

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

    I had a prewritten sieve from last contest :D

»
11 months ago, # |
  Vote: I like it -16 Vote: I do not like it

If it is rated contest?

»
11 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Perfect difficulty level distribution .

»
11 months ago, # |
Rev. 2   Vote: I like it +158 Vote: I do not like it

:<

»
11 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can we see test 6 on D? Or someone who made a lot of hacks (not talking about overflow-like hacks), can you share the idea, please?

UPD: Thanks to all of you :))

  • »
    »
    11 months ago, # ^ |
    Rev. 2   Vote: I like it -8 Vote: I do not like it

    2*k>n is test 6.

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

      Why is 2*k > n special case?

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

        Because when k*2>n, for example with test 7 5. Then 2 will be connected with 7. But you should consider this line as 7 2 rather than 2 7 to avoid repeats.

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

    5 3

    • »
      »
      »
      11 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      no, that was not it. mine works fine for 5 3 and died in 6

      Edit: it's 1000000 500001. wow.

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

    1000000 500001

    It catches both people who fail testcases with 2k > n and people who forgot 64bit data types to store result.

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

    I can offer you a solution that passes system tests, if that's of any use. :/

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

    Most of the solutions failed on test cases when k > n/2. So the example hack can be: 5 3

    As the circle is symmetric one could just take k = min( k, n — k ) at the beginning of the solution

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

    The most basic hack was 5 3 <-- should have the same answer as 5 2 because the circle is symmetric.

»
11 months ago, # |
  Vote: I like it +28 Vote: I do not like it

How am I supposed to score 13 hacks in D (as some people did on 13 different users) if I hacked all wrong (not mine xd) solutions which amounts to 3 submissions :/?

  • »
    »
    11 months ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    Hey that's me :)

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +140 Vote: I do not like it

    And that's why hacks are a stupid concept that doesn't belong in programming contests.

  • »
    »
    11 months ago, # ^ |
      Vote: I like it -20 Vote: I do not like it

    Life is not fair and it will never be :)

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

      That's why many people find ACM-styled contests better than life — because they are fair. :)

      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it +45 Vote: I do not like it

        When you are in a stupid university and you are the only competitive programmer in this university and you have no choice but to put 2 teammates with much lower level than you while most other teams consist of 3 strong participants then ACM is not fair.

»
11 months ago, # |
  Vote: I like it +29 Vote: I do not like it

Thanks for someone hacking my D solution...

»
11 months ago, # |
  Vote: I like it +65 Vote: I do not like it
random_shuffle(participants.begin(), participants.end());
  • »
    »
    11 months ago, # ^ |
      Vote: I like it +96 Vote: I do not like it

    random_shuffle(participants.begin() + 1, participants.end());

»
11 months ago, # |
  Vote: I like it +15 Vote: I do not like it

Evil pretests X(

»
11 months ago, # |
  Vote: I like it -20 Vote: I do not like it

nice contest :(

»
11 months ago, # |
  Vote: I like it +13 Vote: I do not like it

So week pretest on problem D!

»
11 months ago, # |
  Vote: I like it +11 Vote: I do not like it

When will ratings change ?

»
11 months ago, # |
  Vote: I like it +38 Vote: I do not like it

NBHEXT stoped working, did anyone else have the same problem?

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

    Yes, unfortunately, it is not working. I've already written about that in the main post NBHEXT 2 weeks ago, but have not got any responses.

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

    What is NBHEXT ?

»
11 months ago, # |
Rev. 4   Vote: I like it +97 Vote: I do not like it

So there were 5 pretests for D. What's next — only samples in the pretest? — Angry n00b who failed systest

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

    Exactly that should not happen many Coders used the inappropriate approach like submitting the solution using brute or something and then hacking the solutions of others.

  • »
    »
    11 months ago, # ^ |
      Vote: I like it -38 Vote: I do not like it

    There are milions of values in the pretests. Ekhm.

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

    Also, there isn't a single pretest in which k>n/2, which was the reason for most WAs.

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

      I guess another problem with such pretests is that it encourages hacking to an extent which is overkill. People can get too many points with just hacks. D is of the same worth as F due to the available hacks.

      Also, the point difference between D and E/F seems a bit low :/

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

      Intentional.

      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it +44 Vote: I do not like it

        Sad. Randomizes results as hell.

        • »
          »
          »
          »
          »
          11 months ago, # ^ |
            Vote: I like it -20 Vote: I do not like it

          Actually we didn't expect that so many people will fail. If one problem has some hacks, its's acceptable, isn't it?

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Great Contest! Maybe on the easy side, but who cares, my rating will increase!

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what is the hack for this submission http://codeforces.com/contest/755/submission/23862816 ??

»
11 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Given that lately there were quite a few combined Div.1 + Div.2 contests (and they went well), I'm starting to wonder whether we need the division system at all.

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

    Yes, we do. For the participants, the division system is not optimal. However, few writers are able to provide 5 problems difficult enough for the best of Div. 1. Then, you either don't have a lot of contests, or you have a lot of contests in which ~500 guys solved all the problems in less than an hour.

»
11 months ago, # |
  Vote: I like it +41 Vote: I do not like it

Also, what was the deal with C? Isn't it too straightforward and classical : I read the problem 5 times to make sure I didn't miss something....

  • »
    »
    11 months ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it
    /*
    You can search something about the "tree's diameter".
    (dfs from a vertex u and find the longest vertex away from u and mark it as v;
    then again dfs from v and find the longest vertex away from v and mark it as v';
    v and v' are the two vertex of the tree's diameter)
    if a vertex belongs to the tree;
    then the longest vertex away from it will be one of the v or v';
    */
    
  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If you solved with DFS or find/union, then it might be. Check the editorial approach. It's quite cool.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

You can B test 16 please?

»
11 months ago, # |
Rev. 2   Vote: I like it +157 Vote: I do not like it
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Not blue again :(

»
11 months ago, # |
  Vote: I like it -13 Vote: I do not like it

Really nice problems, thank you

»
11 months ago, # |
  Vote: I like it +61 Vote: I do not like it

Non-sample pretests for individual problems: 4, 6, 4, 3, 6, 12, 2. Was that intentional? The only problem with a decent number of pretests was F... no wonder there were so many hacks and failed systests.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Interesting problems and I liked short problem statements, Thanks :D

»
11 months ago, # |
  Vote: I like it -18 Vote: I do not like it

who can solve me this problem https://www.e-olymp.com/ru/problems/566