numbertheorist17's blog

Codeforces Round #331
By numbertheorist17, history, 8 years ago, In English

Hello, Codeforces!

I am happy to announce Codeforces Round #331 (Div. 2)! The round will be held on November 15th at 7:35 MSK. Div. 1 users can participate out of contest.

The problem set was prepared by me (Girishvar Venkat) and jaina (Jeffrey Zhang). I sincerely thank GlebsHP (Gleb Evstropov) for helping with the preparations of the contest. I also thank thesilione (Bili Sun) for testing this round.

The hero for this round will be Wilbur the pig, after my good friend wilbs43 (Wilbur Li).

Scoring will be 500-1000-1500-2250-2500.

Hope you enjoy this round and wish you high rating!

UPD: Contest is over. Here is a link to editorial: Editorial.

UPD2: Congratulations to all the winners! Results:

Div. 1:

  1. tourist

  2. DBradac

  3. ztxz16

  4. V--o_o--V

  5. waterfalls

Div. 2:

  1. Ichiban

  2. Antoniuk

  3. thjchph4trjnh

  4. halyavin

  5. Rafiki53

Hope you all enjoyed this contest! Thanks for participating!

UPD3: Ratings updated.

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

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

Auto comment: topic has been updated by numbertheorist17 (previous revision, new revision, compare).

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

It's very rare that scoring distribution isn't "announced later".

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

    Don't understand what is the profit of knowing the scroring distribution before contest. Almost all participants solve tasks starting from the most easy (= problem A).

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

      If it is dynamic scoring, solving B or C first may be better.

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

lots of number theory problems ?!?! :)

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

    if there is any number theory problem in this contest, there will be many hacks .....

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

I wonder why it's 19:35 but not 19:30.

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

    I think the 5 minutes difference is just that famous DELAY!!

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

    We found that in case of 5-10 minutes delay there are many participants who additionally register. It seems it is some kind of psychology: if you see that round will start on 19:30 (and even if you know about 19:25 as deadline for registration), your brain rounds 19:25 to 19:30 and probably you will be near your computer on 19:30, but not on 19:25.

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

      Now my brain rounds 19:30 to 19:35 :D

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

      Usually, that is happened with me. I thank to MikeMirzayanov for setting this time. So, I could participate next all contests.

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

        Or just keep in mind the contest's starting time. I think it's not so difficult (only five minutes earlier) :D

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

      Hi can you register me please or delay it 5 more minutes

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

Is round going to be interesting ? Your color says the contest not going to be interesting. Always people with color like your's make contest hard and uninteresing.

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

as your username it seems we are going to have number theory problems

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

I know I'm gonna get many downvotes for this comment, but I really hope that problems would be based more on complex algorithms rather than math.

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

this contest will be rated! yeeee! ^_^

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

I thought I saw Xellos comment in this thread, but now it's disappear. Is that a bug?

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

I think its going to be a math contest (The handle of Girishvar Venkat :|) Why not changing the name from CodeForces 2 AlgebraForces??

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

    Did you create a new account for writing this comment? Why are you so afraid of using your original account if you are really thinking this way?

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

Wish I can have a good night and a high rating.

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

Hope for maths!

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

just a usual delay !!!

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

Mathforces instead of codeforces ...

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

Really liked the problems! Haven't had such a nice round for a while

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

Can anyone explain C?

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

    I've come up with the following idea:

    As you can see, we can associate a list of vertices with an index of an array (or map, if you will).

    Step 1: create the vertex queues

    Vertices on the diagonal (0, 0), (1, 1), (2, 2), (3, 3), (4, 4), ... are all map to 0. That means, we can store these particular vertices under the key 0 in some container. I store them like that:

    map< vector< pair<int, int> > > vertex_queues;
vertex_queues[0].push_back( make_pair(1, 1) );
vertex_queues[0].push_back( make_pair(3, 3) );
vertex_queues[0].push_back( make_pair(2, 2) );
...

    vertex_queues[0] now stores the vertices unordered. So, we need to sort them so that we can use them later.

    Step 2: construct the answer by taking the vertices from the vertex queues in the right order

    The last step is building the answer. We go through the array w[n] from left to right and take the first element from the vertex queue with the index w[i]. So, the i'th vertex must be the one we've just taken from the queue. One by one, we extract all the vertices from the vertex queues in the order dictated by the array w[n].

    If there are no elements in the w[i]'th vertex queue, the anser is NO. If, lastly, we look though all the vertices in the array that we've constructed and find that the current vertex is less than the previous one, the answer is also NO.

    Otherwise, we've build the perfectly valid array of vertices which is the solution to the problem :)

    14288949 — with map
    14289137 — with vector

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

    First you should sort points by their y-x then for each w[i] from last to first set the point with biggest x and y!

    now we should check that does this greedy algorithm make a aesthetically pleasant! sort points and then for each (x,y) we calculate the mp[ (x,y) ] the maximum index of every point like x' and y' that 0<=x'<=x and 0<=y'<=y in the answer! and we update it with mp[ (x-1,y) ] and mp[ (x,y-1) ] , if one of them was bigger than index of (x,y) print No!

    now we know answer for each w[i] and it's aesthetically pleasant!

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

Auto comment: topic has been updated by numbertheorist17 (previous revision, new revision, compare).

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

Editorial before finish time ??

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

hacked 5 people in problem B in my first hacking attempt on codeforces thanks to this

2

-1000000000 1000000000

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

    I also wanted to have my first hacking attempt with such a silly mistake, that I also had made, but I had not found in time where the hacking button is, what a shame...

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

      go to room than double click in any submission and hack it , of course you have to lock your problem .

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

        Thank you, but "I had not found in time" means I had done it after contest ends)

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

    Nobody in my room was stupid enough not to use long long.

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

The character "Wilbur" may just as well have not been in the problem statements. All it did was add clutter.

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

    But reading the problem through the clutter is a part of the problem. If you would be said like "given array, find sum of absolute differences between i and i+1 for i from 0 to N-1" then it wouldn't be a contest.

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

      The clutter I'm talking about is the crap about Wilbur, not the actual problem itself. The problem could have been simply:

      You are given an array a of size n which initially consists of all zeroes. In one step, you may choose any index i and either add or subtract 1 to all elements from ai to an. Your goal is to end up with the given array b.

      What is the minimum number of steps required to reach your goal?

      Simple and concise. Add a story behind it if you'd like, but don't do it just for the sake of doing it.

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

      It's a trade-off. The problems on Project Euler don't have stories, but that doesn't make them any more boring for me. Personally I actually prefer that approach, but I'm also fine with some characters and a small story to make the problems more fun.

      The thing with Codeforces is that the English is very difficult to read and often has typos or grammatical mistakes. And sometimes there's just so much stuff. See this older problem for example, would you enjoy reading that when there's pressure to solve the problem in 2-3 minutes? http://codeforces.com/problemset/problem/48/A

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

I loved the contest — keep it up! Thanks numbertheorist17 and GlebsHP

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

This comment was written before final results. I didn't know that they will be same

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

Problem E was nice but pretty hard to implement in a short time,it would have been better if the input was a tree instead of matrix(because it wouldn't have cycles and make things easier)

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

Super fast system testing this time

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

> when you hack someone and then fail on your own hack during systest

EDIT: The funny thing is, if I hardcode the answer to my hack test, I get AC. Meaning if I didn't hack, maybe I wouldn't have failed systest... worst feeling ever :'(

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

I don't know how to deal with the problem D? Is this a dp problem?

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

    Seems like it. dp[left/right][start][end] precompute two arrays to determine the first tree that will be available to cut if ith tree is cut and falls on left, and right respectively.

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

Auto comment: topic has been updated by numbertheorist17 (previous revision, new revision, compare).

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

What a bad day! I did my computer component principle homework about how cpu work the whole day and didn't finish it. That made me not think strictly in round and get a bad rank. I'm so sad. :(

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

    This straight line in your curve looks pretty cool though.

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

    On the other hand, you got the 228th place, Bredor is very proud of you!

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

    The computer component principle is a nightmare!!

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

Auto comment: topic has been updated by numbertheorist17 (previous revision, new revision, compare).

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

why the main test 18 in problem A gives wrong answer but when i run this program in my ide it give me correct answer 0

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

    The correct answer for that test is 227504, and yours is 0

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

    Correct answer isn't 0. Its 227504. I failed at the same due to a stupid mistake. Should have tested more rather then racing against time.

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

tourist is BACK for a contest! :D

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

    Maybe he decided that Div.1 contests are too complicated for him and will participate only in Div.2?

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

      you must be kidding.

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

        Ofc no. I was just trying to figure out, why hadn't he taken part in theeeeeeese Div.1 contests instead of boasting in front of Div.2 users? The answer was quite evident.

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

Why this code getting TLE? Its complexity is O(n^2) :( I really don't have any idea why.

14287878

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

    I think it is because while loop in your find function.

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

      Oh, I didn't notice that >< Btw, thanks!

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

Weak Test cases in C.
8 0 0 0 1 0 2 1 0 1 1 1 2 2 0 2 1 0 1 2 -1 0 1 -1 -2
Solutions giving YES followed by wrong sequence gets AC.
Correct Answer: NO
AC Buggy code: 14287550

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

We always see in codeforces, the output is judged by special judge. that means if the output is 1 then if you print 1.000 there is no problem. Even sometimes Lower case uppercase does not matter. Today I wrote problem A with double variable got WA. For output printing the problem says, "Print the area of the initial rectangle if it could be uniquely determined by the points remaining. Otherwise, print  - 1." There is no instruction that the output should be integer. But it causes me wrong answer and finally I have a devastating contest. 14274647

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

    Your answer does not actually specify the last significant digit of the answer

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

      Thanks, I get it. It's my fault not to specify the setprecision. Default setprecision causes the error.

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

Could someone explain me how this solution (http://codeforces.com/contest/596/submission/14278463) passed all tests?!

P.S.: during the contest I tried to hack it several times using tests like

but without any success :(

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

    Thats strange. Even the basic test such as "1 1000000000" runs forever on my computer. Are there any kind of optimizations being done in codeforces compiler?

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

      I believe so. There has been a blog about this kind of thing before.

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

      Codeforces compiles C++ with gcc's -O2 flag, which is really common among a lot of online judges and other competition platforms.

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

    C++ Optimizer. Optimizer is much smarter than that programmer.

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

      Absolutely agree :)

      So why not to disable C++ compiler optimizations on Codeforces? Because now hacking such cases is just like trying your luck :(

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

        Because it would be unfair if you keep in mind almost all compilers/interpreters do it (Codeforces supports a lot of languages!).

        Anyways: gcc's -O2 flag is used almost everywhere in competitive programming, and while optimizations like this one tend to obscure the true meaning of the code, they only happen in specific situations and do more good than harm.

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

Auto comment: topic has been updated by numbertheorist17 (previous revision, new revision, compare).

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

Very Weak Data Set for problem C ... http://codeforces.com/contest/596/submission/14281582 3 6 3 7 0 6 2 -3 -7 -4 This code cant pass this input, but passed system test.

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

    Your input:

    3
6 3
7 0
6 2
-3 -7 -4

    is not valid, is it? Take a closer look to the input section of problem C.

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

    "Also, it is guaranteed that if some point (x, y) is present in the input, then all points (x', y'), such that 0 ≤ x' ≤ x and 0 ≤ y' ≤ y, are also present in the input."

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

Why I got verdict skipped? 14275850, 14282184 and 14273892. This is my first time to solve 3 problems in a contest!

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

tourist was the first to solve each problem , amazing !!

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

numbertheorist17

Weak Test cases in Question: C. input: 15 0 0 1 1 2 2 0 1 1 2 2 3 0 2 1 3 0 3 0 4 1 0 2 1 2 0 3 1 3 0 0 1 -1 2 0 -2 3 1 -1 -3 2 -2 1 4 0

output: should be NO [also verified using [user:tourist] sol'n :p]

Two users in top5(div2 rankings) got it accepted...even though their output is wrong.
Rank1: Ichiban and Rank5: Rafiki53 :p

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

    Also my solution verify this :D (I'm 99.00% sure about my solution correctness)

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

    This is unfortunate. I thought I took care of all the cases, but I guess I didn't. Sorry about that! Next time, I will have to be more careful.

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

      Less than 1% of div2 participants solved D and less than 0.1% solved E.

      Is this the expected difficulty level to make participating fun for div1 people too? Or maybe it would be more fun for div2 people if they could get more than 3/5 once in a while?

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

        I think it is just that jaina and I thought the problems are easier than they actually are.

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

          Fair enough. :)

          I understand that estimating the difficulty must be very hard.

          If you'd like to get feedback for future problems from someone who's far from div1 level, I'd like to volunteer. Maybe sometimes it would be possible to add some simple problems and hold a div1 and div2 at the same time, making everybody happy!

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

    MikeMirzayanov, GlebsHP take a look please

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

      The testset for this problem turned out to be weak. That happens sometimes, but everyone is free to do challenges and improve it during the contest.

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

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

Who else thinks D was more doable than C?

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

    During the contest I got intimidated by the number of people who solved D and didn't give it much thought. Later I tried to solve it and found it easier than C either, it's a straight foward DP.

    Actually I think the hardest task on C was understand the english translation, the problem itself wasn't hard.

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

I Love Judge!!!???

→ Reply