Автор kpw29, 7 лет назад, По-английски

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. jqdai0815
  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 =)

  • Проголосовать: нравится
  • +408
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

will be 7 or 8 problems?

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится -15 Проголосовать: не нравится

    7 problems. We will inform about the scoring later.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +43 Проголосовать: не нравится

      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.

»
7 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +46 Проголосовать: не нравится

Börk, börk

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

»
7 лет назад, # |
  Проголосовать: нравится +103 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Rating for div2?

»
7 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

"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 ^_^

»
7 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

Will it be rated?

»
7 лет назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

Is everyone who can participate in this contest?

»
7 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

poland ball <3

»
7 лет назад, # |
  Проголосовать: нравится -20 Проголосовать: не нравится

Balls War 2

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
7 лет назад, # |
  Проголосовать: нравится +115 Проголосовать: не нравится

kurwa

»
7 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

Is it rated or not?

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Long Live CODERS...

»
7 лет назад, # |
  Проголосовать: нравится -43 Проголосовать: не нравится

is it rated ?

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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

»
7 лет назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
7 лет назад, # |
Rev. 3   Проголосовать: нравится -83 Проголосовать: не нравится

Is it Rated ? got it. It is rated

»
7 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

The contest starts in 18 minutes. Good luck all!

»
7 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Solution for A stays queued for 5 minutes, help

»
7 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

ПольшаМожетВПрограммирование!!!

»
7 лет назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится -6 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +36 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

It's the most beautiful contest I ever seen.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What was the hack for D?

»
7 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

How to hack A?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
7 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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 >.<

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Here's my soluton.

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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)

»
7 лет назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +18 Проголосовать: не нравится

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

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        int x = something;
        bitset<x> b;
        
        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

    • »
      »
      »
      7 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Actually even well written N sqrt N can pass.

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

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится +10 Проголосовать: не нравится

        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?

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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

    EDIT: I guess I have a bug. :/

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +25 Проголосовать: не нравится

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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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)).

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +37 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +23 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

4th Very weak pre-test cases.

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

»
7 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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 !

»
7 лет назад, # |
  Проголосовать: нравится +222 Проголосовать: не нравится

2k > n in D

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
»
7 лет назад, # |
  Проголосовать: нравится +83 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Why?

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +15 Проголосовать: не нравится

      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...

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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?

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +46 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится +2 Проголосовать: не нравится

        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.

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +17 Проголосовать: не нравится

    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)

    • »
      »
      »
      7 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +20 Проголосовать: не нравится

      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).

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится +6 Проголосовать: не нравится

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

      • »
        »
        »
        »
        7 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +20 Проголосовать: не нравится

        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?

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            7 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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?

            • »
              »
              »
              »
              »
              »
              »
              7 лет назад, # ^ |
                Проголосовать: нравится -15 Проголосовать: не нравится

              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"

            • »
              »
              »
              »
              »
              »
              »
              7 лет назад, # ^ |
              Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

              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 riadwaw here

            • »
              »
              »
              »
              »
              »
              »
              7 лет назад, # ^ |
              Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

              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.

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится -10 Проголосовать: не нравится

    Agreed.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

Using int in problem D :) good bye cruel world

»
7 лет назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

Awesome round, Kacper! Thanks :)

»
7 лет назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

WTF was this contest!!!!!

»
7 лет назад, # |
  Проголосовать: нравится +57 Проголосовать: не нравится

Feeling proud after making hack for a red one 'D

»
7 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

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

answer is min(999, n+2)

»
7 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +23 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

tourist got penalty on A :o

»
7 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

"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

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What could be the reason of WA5 in G?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    Mine running maximum test in 8.7 sec :(

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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)

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +25 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

D so many fst ....

»
7 лет назад, # |
Rev. 4   Проголосовать: нравится +36 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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) >>>>.<<<<

»
7 лет назад, # |
  Проголосовать: нравится -16 Проголосовать: не нравится

If it is rated contest?

»
7 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Perfect difficulty level distribution .

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +158 Проголосовать: не нравится

:<

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 :))

»
7 лет назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

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 :/?

»
7 лет назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

Thanks for someone hacking my D solution...

»
7 лет назад, # |
  Проголосовать: нравится +65 Проголосовать: не нравится
random_shuffle(participants.begin(), participants.end());
»
7 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

Evil pretests X(

»
7 лет назад, # |
  Проголосовать: нравится -20 Проголосовать: не нравится

nice contest :(

»
7 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

So week pretest on problem D!

»
7 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

When will ratings change ?

»
7 лет назад, # |
  Проголосовать: нравится +38 Проголосовать: не нравится

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

»
7 лет назад, # |
Rev. 4   Проголосовать: нравится +97 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится -38 Проголосовать: не нравится

    There are milions of values in the pretests. Ekhm.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 :/

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      Intentional.

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится +44 Проголосовать: не нравится

        Sad. Randomizes results as hell.

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится -20 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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.

»
7 лет назад, # |
  Проголосовать: нравится +41 Проголосовать: не нравится

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....

  • »
    »
    7 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится
    /*
    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';
    */
    
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

You can B test 16 please?

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +157 Проголосовать: не нравится
»
7 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Задачи шикарные (C-E) (F и G не читал). Во всех надо подумать и по минимуму кодить (если, конечно, вам не лень писать ДО вместо Фенвика). И еще забавно, когда новички, которые не знают ни ДО, ни Фенвика, обходят опытных участников, написав математическое решение (это я про Д).

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Есть пример математического? Я пока видел только решение основанное на подсчете количества циклов, но не формулой а в цикле. Наверное это можно формулой выразить, в общем если есть пример дай ссылку плз

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Я это и подразумевал под математическим. В любом случае, оно работает без программисткого логарифма)

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

кокой-то раунд для педерасов и чуханов. минусуйте

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Not blue again :(

»
7 лет назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

Really nice problems, thank you

»
7 лет назад, # |
  Проголосовать: нравится +61 Проголосовать: не нравится

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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится -18 Проголосовать: не нравится

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