Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

danya.smelskiy's blog

By danya.smelskiy, 3 weeks 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  

»
3 weeks ago, # |
  Vote: I like it +37 Vote: I do not like it

it is a good time for chinese,^_^

»
3 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

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

»
3 weeks 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:((

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

good timing , coming expert i hope

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

:3

»
3 weeks 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!

»
3 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

2 hours and 15 minutes is good for 6 problems.

:)

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

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

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

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

»
3 weeks 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

»
3 weeks ago, # |
  Vote: I like it -57 Vote: I do not like it

Is it rated?

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

i wanna be green today.....

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Good Luck To Everyone! :D

»
3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

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

»
3 weeks 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.)

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

    Irony is that most questions are two-dimensional xD

  • »
    »
    3 weeks 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

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

what a problem C is!

How to solve it?

  • »
    »
    3 weeks 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.

  • »
    »
    3 weeks 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.....

    • »
      »
      »
      3 weeks 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.

      • »
        »
        »
        »
        3 weeks 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]);

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 weeks 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 :(

    • »
      »
      »
      3 weeks 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......

  • »
    »
    3 weeks 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)

»
3 weeks ago, # |
  Vote: I like it -11 Vote: I do not like it

I am not enjoying codeforces short rounds anymore :(

»
3 weeks 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

»
3 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

Implementationforces.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

what is pretest 2 in problem C ?

  • »
    »
    3 weeks 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.

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

    Rectangles not ovelapping.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 weeks 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?

  • »
    »
    3 weeks 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!

»
3 weeks 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.

»
3 weeks 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?

»
3 weeks 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 ;)

»
3 weeks 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).

»
3 weeks 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

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks 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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

Loved problem D. Hope it passes systest.

»
3 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

This contest is a brilliant!

»
3 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

hacking attempt failed for (A) 100000000 1 , 46153884

  • »
    »
    3 weeks 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.

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

    I lost 100 positions because of him

»
3 weeks 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?

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

    Undefined behavior is a thing.

  • »
    »
    3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it +23 Vote: I do not like it

who can tell me when the system test will begin?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      3 weeks 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.

»
3 weeks 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.

  • »
    »
    3 weeks 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.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it +21 Vote: I do not like it

Why Pending System Testing is still lasting?

»
3 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

Disgusting problems :/

»
3 weeks 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.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Probably want to surprise us by showing "Contest finished" at once!

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

todays contest was about maths and implementation..XD

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F?

  • »
    »
    3 weeks 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

»
3 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

Why not let system testing start?

»
3 weeks 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?

»
3 weeks 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.

»
3 weeks 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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

System testing started!

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

problem B are similar to 486A

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The two problems are very similar...

  • »
    »
    3 weeks 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...

»
3 weeks 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 .

»
3 weeks 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.

  • »
    »
    3 weeks 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. ^^

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

re because of 1 character :(

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve problem E?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

fully calculation based, though set was cool

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it -14 Vote: I do not like it

i dont understand