numbertheorist17's blog

By numbertheorist17, history, 22 months 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. overtroll

  5. waterfalls

Div. 2:

  1. Ichiban

  2. Antoniuk

  3. ph4trjnh

  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  

»
22 months 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).

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

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

  • »
    »
    22 months 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).

    • »
      »
      »
      22 months 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.

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

lots of number theory problems ?!?! :)

  • »
    »
    22 months 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 .....

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

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

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

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

  • »
    »
    22 months 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.

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

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

    • »
      »
      »
      22 months 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.

      • »
        »
        »
        »
        22 months 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

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

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

»
22 months 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.

»
22 months 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

»
22 months 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.

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

this contest will be rated! yeeee! ^_^

»
22 months 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?

»
22 months 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??

  • »
    »
    22 months 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?

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

      Nope! My last account got ruined by my crazy friends, this is a new one..

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

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

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

Hope for maths!

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

just a usual delay !!!

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

Mathforces instead of codeforces ...

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

C is the most confusing question ever

»
22 months 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

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

Can anyone explain C?

  • »
    »
    22 months 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

  • »
    »
    22 months 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!

»
22 months 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).

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

Editorial before finish time ??

»
22 months 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

  • »
    »
    22 months 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...

    • »
      »
      »
      22 months 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 .

      • »
        »
        »
        »
        22 months 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)

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

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

»
22 months 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.

  • »
    »
    22 months 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.

    • »
      »
      »
      22 months 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.

    • »
      »
      »
      22 months 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

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

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

»
22 months 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

»
22 months 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)

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

Super fast system testing this time

»
22 months 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 :'(

feels

»
22 months 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?

  • »
    »
    22 months 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.

»
22 months 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).

»
22 months 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. :(

»
22 months 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).

»
22 months 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

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

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

  • »
    »
    22 months 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.

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

tourist is BACK for a contest! :D

  • »
    »
    22 months 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?

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

      you must be kidding.

      • »
        »
        »
        »
        22 months 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.

»
22 months 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

»
22 months 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

»
22 months 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

  • »
    »
    22 months 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

    • »
      »
      »
      22 months 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.

»
22 months 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 :(

  • »
    »
    22 months 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?

    • »
      »
      »
      22 months 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.

    • »
      »
      »
      22 months 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.

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

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

    • »
      »
      »
      22 months 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 :(

      • »
        »
        »
        »
        22 months 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.

»
22 months 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).

»
22 months 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.

  • »
    »
    22 months 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.

  • »
    »
    22 months 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."

»
22 months 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!

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

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

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

I used binary search for problem C and got AC. Here is my solution 14289254. But I don't think thats it is correct. It should give TLE on a certain test case.

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

Not seeing so much memes this time gives me strange feeling

»
22 months 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

  • »
    »
    22 months 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)

  • »
    »
    22 months 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.

    • »
      »
      »
      22 months 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?

      • »
        »
        »
        »
        22 months 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.

        • »
          »
          »
          »
          »
          22 months 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!

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

    MikeMirzayanov, GlebsHP take a look please

    • »
      »
      »
      22 months 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.

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

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

Who else thinks D was more doable than C?

  • »
    »
    22 months 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.

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

Can someone explain why I am getting different outputs on codeforces and ideone if I am executing the same code ? codeforces link ideone link

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

I Love Judge!!!???

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

My computer Ram died!!!????