danya.smelskiy's blog

Codeforces Round #524 (Div. 2)
By danya.smelskiy, 6 years 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 stanislav.bezkorovainyi.

Thanks to Markellonchik, iSlava, and Barichek for testing, Jajceslav 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. Qingzhi_chan
  2. Laggay
  3. H-C-H
  4. lqs2015
  5. Trrui

UPD3: Editorial.

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

Comments Comments (107)
| Write comment?
»
6 years ago, # |
  Vote: I like it +37 Vote: I do not like it

it is a good time for chinese，^_^

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

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

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

    cheer up:D,

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

    I was successful in keeping my green color :) Got +50 points.

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

      You submitted 2 problems in same time and use 2 different languages :v !

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

    oh, y have become green. my congratulations! Soon I will be blue. screen))))

    → Reply
»
6 years 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:((

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

good timing , coming expert i hope

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -25 Vote: I do not like it

:3

→ Reply
»
6 years 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!

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

2 hours and 15 minutes is good for 6 problems.

:)

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -18 Vote: I do not like it

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

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

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

→ Reply
»
6 years 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

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

Is it rated?

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

i wanna be green today.....

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

Good Luck To Everyone! :D

→ Reply
»
6 years 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.

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

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

→ Reply
»
6 years 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.)

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

    Irony is that most questions are two-dimensional xD

    → Reply
  • »
    »
    6 years 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

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

what a problem C is!

How to solve it?

→ Reply
  • »
    »
    6 years 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.

    → Reply
  • »
    »
    6 years 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.....

    → Reply
    • »
      »
      »
      6 years 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.

      → Reply
      • »
        »
        »
        »
        6 years 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]);

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

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

        → Reply
  • »
    »
    6 years 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 :(

    → Reply
    • »
      »
      »
      6 years 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......

      → Reply
  • »
    »
    6 years 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)

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

I am not enjoying codeforces short rounds anymore :(

→ Reply
»
6 years 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

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

Implementationforces.

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

what is pretest 2 in problem C ?

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

    Rectangles not ovelapping.

    → Reply
  • »
    »
    6 years 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!

    → Reply
»
6 years 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.

→ Reply
»
6 years 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?

→ Reply
»
6 years 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 ;)

→ Reply
»
6 years 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).

→ Reply
»
6 years 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

→ Reply
  • »
    »
    6 years 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.

    → Reply
    • »
      »
      »
      6 years 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

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

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

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

Loved problem D. Hope it passes systest.

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

This contest is a brilliant!

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

hacking attempt failed for (A) 100000000 1 , 46153884

→ Reply
  • »
    »
    6 years 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.

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

    I lost 100 positions because of him

    → Reply
»
6 years 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?

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

    Undefined behavior is a thing.

    → Reply
  • »
    »
    6 years 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.

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

who can tell me when the system test will begin?

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

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

    → Reply
    • »
      »
      »
      6 years 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.

      → Reply
»
6 years 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.

→ Reply
  • »
    »
    6 years 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.

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

https://media.makeameme.org/created/math-math-everywhere-599f77.jpg

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

Why Pending System Testing is still lasting?

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

Disgusting problems :/

→ Reply
»
6 years 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.

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

todays contest was about maths and implementation..XD

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

How to solve F?

→ Reply
  • »
    »
    6 years 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

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

Why not let system testing start?

→ Reply
»
6 years 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?

→ Reply
»
6 years 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.

→ Reply
»
6 years 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.

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

System testing started!

→ Reply
»
6 years ago, # |
← Rev. 4   Vote: I like it -27 Vote: I do not like it

problem B are similar to 486A

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

    The two problems are very similar...

    → Reply
    • »
      »
      »
      6 years 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

      → Reply
  • »
    »
    6 years 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...

    → Reply
»
6 years 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 .

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

re because of 1 character :(

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

How to solve problem E?

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

fully calculation based, though set was cool

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

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

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

.

→ Reply