danya.smelskiy's blog

By danya.smelskiy, 4 months ago, translation, In English,

Hi, Codeforces!

Codeforces Round #524 (Div. 2) will be held on Nov/24/2018 10:35 (Moscow time). The round will be rated for the second division (rating is less than 2100). As usual, participants from the first division will be able to participate out of competition.

You will be given 6 problems and 2 hours and 15 minutes to solve them.

This round was prepared by me, arsijo, and StasyaCat.

Thanks to Markellonchik, iSlava, and I_love_Maria_Ivanova for testing, AHDPIYKO for pictures to the problems, and MikeMirzayanov for wonderful platforms Codeforces and Polygon.

The round is based on the II stage of Ukrainian Olympiad in Informatics, that is why please do not discuss the problems before the system testing start.

UPD: Scoring distribution: 500 — 750 — 1250 — 1750 — 2250 — 2500.

UPD2: Congratulations to the winners:

  1. LingXuan
  2. Laggay
  3. H-C-H
  4. lqs2015
  5. Trrui

UPD3: Editorial.

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

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

it is a good time for chinese,^_^

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

I will put my best effort to keep this green color :p

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

II. stage of Turkish Olympiad in Informatics is at the same time, clashes with the contest:((

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

good timing , coming expert i hope

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

:3

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

Nice, it's been a while since we had pictures to the problems!

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

2 hours and 15 minutes is good for 6 problems.

:)

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

It's a very bad time for a Bangladeshi Participator. :(

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

Your rating graph is inspiring. Hope for a good contest. :)

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

it's good that no one will wake up that early to make a DDos-attack

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

Is it rated?

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

i wanna be green today.....

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

Good Luck To Everyone! :D

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

Does CHelper work when the codeforces is in HTTPS? Any workaround? All of a sudden, codeforces is redirecting all the requests to HTTPS, and now, I'm unable to participate. :( Parse Contest feature doesn't parse test cases. So, that isn't an option as well.

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

E is 2500 points. Is the round wrong, or the announcement?

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

Never seen such one dimensionality in any contest in my life ever!!!

All questions from C to E involves a matrix and problems from A to D require some type of maths.

Really disappointing problemset.

(EDIT- On the top of that, really really unbalanced problemset. The gap between C and D is not really ideal. Clearly a bad contest.)

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

    Irony is that most questions are two-dimensional xD

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

    And on top of that use (x, y) x for column in C and (i, j) i for row in E, genius

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

what a problem C is!

How to solve it?

  • »
    »
    4 months ago, # ^ |
    Rev. 6   Vote: I like it +3 Vote: I do not like it

    https://stackoverflow.com/questions/19753134/get-the-points-of-intersection-from-2-rectangles
    First find how many white and black are initially on board.
    For both rectangles(white cand black colored) calculate its area (say W and B).(number of cells)
    Then find the intersection of two rectangles that many cells will be deducted from W count.(black color will overwrite white color)
    Now from this 3 information you can find final answer.

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

    judge overlap

    If no intervals overlap

    I think u can solve it,its not very hard

    If exist, initialize the overlap, that is, turn the white part back to black.

    my code seem very stupid.....

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

      I just spend all time of contest for just finding the overlap area.

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

        Here is my code,its show how to find overlap area.

        scanf("%I64d%I64d",&n,&m);

        scanf("%I64d%I64d%I64d%I64d",&x[1],&y[1],&x[2],&y[2]);

        scanf("%I64d%I64d%I64d%I64d",&x[3],&y[3],&x[4],&y[4]);

        x[5] = max(x[1],x[3]); x[6] = min(x[2],x[4]);

        y[5] = max(y[1],y[3]); y[6] = min(y[2],y[4]);

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

        It was little confusing given coordinates were inverted.(Bottom left (1,1))

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

    I spent almost of the time just to find the overlap area oh god, first i had thought it 's really simple :(

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

      Yes,when i first to face the problem “how to find the overlapping area of rectangle”,it spent my 2 days....

      It impressed me, so I remember it very well......

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

    C title topic: At the beginning, there is a checkerboard with black and white colors. Initially, the area of ​​area one (x1 y1) (x2 x2) (the points in the lower left and lower right corners form a rectangular area) are all painted white. Then apply the area of ​​area two (x3 y3) (x4 y4) to black. Find the number of black and white grids on the final board.

    answer:

    In the calculation area one (x1 y1) (x2 y2), there is a white grid w1 black grid b1 at the beginning. In the calculation area two (x3 y3) (x4 y4) area, there is a white grid w3 black grid b3 Calculate the area where the two areas intersect. The three (x5 y5) (x6 x6) area begins with a white grid w2 black grid b2

    At the beginning, there are orw white plaids on the board. Orb black plaids. 1. The area is painted white. orw += b1, orb -= b1 2. The area where the area two intersects with the area one or two is painted black. 2.1 Get the white of area two orb += w3, orw -= w3 2.2 Obtain the black of the intersecting part orb += b2, orw -= b2

    The number of black grids added on orb is w3 + b2 — b1 Corresponding. The number of white lattices reduced on orw is -(w3 + b2 — b1)

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

I am not enjoying codeforces short rounds anymore :(

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

I'm so upset just 1 min and I would've submitted C I just wrote a variable instead of another damn it

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

Implementationforces.

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

what is pretest 2 in problem C ?

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

    how did u approach the problem i think its merely overlapping rectangle problem... i am also getting WA on pretest 2.

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

    Rectangles not ovelapping.

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

    Using long instead of int passed 2nd test for me.

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

    It will be available after system testing

    I got WA on pretest 4 on problem C, but i checked all the possible cases of rectangles positions and no mistakes found. Now i really wonder what is it?

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

    just try 'long long int' instead of 'int', my code was also failing on pretest 2 as i was using int. but total blocks could be ~ 10^18 so int wont work. hope it helps!

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

The round is based on the II stage of Ukrainian Olympiad in Informatics,

that is why please do not discuss the problems before the system testing start.

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

It's only a mathforces round, why you hef to be so mad?

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

I don't really understand why problems like C appears in contest like this. I could understand it, if contest would have 5h.

But excluding this task contest was really good prepared and there wasn't dos attack during the contest ;)

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

Tedious and uninspiring problems. A, B, C are simply mathematical, formula based problems. E, a rather disappointing use case of Manacher's algorithm (as if author had to come up with a problem and worked other way round to "hide" the obvious use of Manacher's).

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

I actually hate chessboard problems they're not fun to think about at all

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

    There was nothing related chess moves, just a rectangle in which adjacent colors are different, So you can't call it that.

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

      I know I'm just pissed of cause I needed just one more min

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

its not even mathforces :(((((((((((

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

Loved problem D. Hope it passes systest.

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

This contest is a brilliant!

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

hacking attempt failed for (A) 100000000 1 , 46153884

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

    I think codeforces can perform about 2e9 simple operations in 1 second.

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

    I lost 100 positions because of him

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

I've sent my solution of problem C a couple of times, but each time the system returned WA on pretest #1 and didn't show this try in the scoreboard (like -1, -2, and so on). However, on my PC in code::blocks, my solution outputs the correct answer on the same pretest #1 (I checked it after the end). How could that happen?

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

    Undefined behavior is a thing.

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

    If the solution is not passed on pretest 1. Then the submission will not be considered as a submission or wrong submission. If solution passes at least one pretest then it will be counted as a submission and will be considered as wrong submissions if it doesn't pass all the test.

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

who can tell me when the system test will begin?

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

    May be after 4 hours. A ICPC Regional in running in GYM.

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

      Then why did the contest start at this time? It's not good to keep many people waiting long.

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

I think it wasn't clear that O(26 × R × C2) would pass for problem E. Exact number of operations is . I used hashing to get it in O(R × C2) after wasting so much time.

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

    Btw I can see other user's submissions.
    Edit — Above comment was edited.

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

      Pretend you dont...and dont discuss problems! =))

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

Why Pending System Testing is still lasting?

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

Disgusting problems :/

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

Whats the point in not discussing problems and delaying sys tests when the solutions are visible.

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

todays contest was about maths and implementation..XD

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

How to solve F?

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

    I can tell you, but it was told to not discuss problems before systests. :(

    Edit:

    -Make a segment tree where in every node you keep a set containing the pair {left border, the minimum right border of an interval that starts after the current one(including the current one)} for every interval corresponding to that node

    -We can construct this tree in n log^2 n time and answer every query online in log^2 n by using the lower_bound operation on the set in the segment tree nodes.

    There is an log n per query solution too but this works too

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

Why not let system testing start?

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

Is it right participants have to wait for system testing to begin over an hour?

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

There should definitely be an official announcement in cases where system testing is supposed to start much later than the normal routine.

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

May be system testing will start after 5 hours from the ending of contest. As there is 2018-2019 ACM-ICPC, Asia Shenyang Regional Contest running at GYM.

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

System testing started!

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

problem B are similar to 486A

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

    The two problems are very similar...

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

      ya but many would miss the idea of f(r) — f(l-1) and do brute force

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

    wow, why so many downvotes:( ? i just want to point out that the problem is copy-paste able (just add extra code for query and - f(l-1)) so codeforces will be more careful to choose problem, me and my friends who solved 486A just copy paste and modify the submission, maybe i should more clear about what i trying to say...

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

Thanks for the duration of 2h and 15 min . I managed to submit C at 02:08 .

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

Congrats for this successful contest. I am new here and curious about the reason that submitting problems after contest in Problem Set and didn't get the details of the wrong answer which other problems to feed back.

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

    I get messages of test data in both new and old submissions now. Maybe it's blank to preparing the test data. Never mind this comment. Thanks for the contest, I earn 93 ratings in this luck first contest. ^^

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

re because of 1 character :(

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

Can anyone tell me why i got -10 in this contest?

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

How to solve problem E?

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

fully calculation based, though set was cool

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

butthurt! 4 accounts of the top 5 are fakes!!

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

i dont understand