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:**

**UPD3: Editorial.**

it is a good time for chinese，^_^

better for hackers

2:30am in the East Coast USA :(

I don't care. I'm in!

and South Korean;

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

cheer up:D,

:D

## PowerUp

yeahhhhhhhhhhhhhhhhh

Try to put effort to be specialist, I think this would be better for you.. and for me too :D

I need +142. In one contest that's too much ;)

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

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

xD

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

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

good timing , coming expert i hope

good luck :V

Hope we all have a good rank.I want to become expert too :D

:3

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

That's why I called AHDPIYKO)

ANDRJYK0's pictures look quite awful(

2 hours and 15 minutesis good for 6 problems.:)

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

As it is holiday. So not so bad i think.

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

Yours too .... bro

Yours too. :D

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

Is it rated?

i wanna be green today.....

you can do it, good luck

Good Luck To Everyone! :D

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.

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

It is fixed now, thanks.

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.)

Irony is that most questions are two-dimensional xD

Disappointed by this round and the questions.

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

what a problem C is!

How to solve 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.

Don't discuss till systests

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.....

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

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]);`

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

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

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......

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)

I am not enjoying codeforces short rounds anymore :(

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

Implementationforces.

what is pretest 2 in problem C ?

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

Rectangles not ovelapping.

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

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?

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!

Thanks

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.

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 ;)

What's wrong with problem C ?

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

hadto come up with a problem and worked other way round to "hide" the obvious use of Manacher's).I actually hate chessboard problems they're not fun to think about at all

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

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

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

Loved problem D. Hope it passes systest.

This contest is a brilliant!

hacking attempt failed for (A) 100000000 1 , 46153884

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

I lost 100 positions because of him

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?

Undefined behavior is a thing.

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.

OK. But why I got WA?

In function countwhite you haven't return anything. Fix it. It will work fine.

Thanks!

who can tell me when the system test will begin?

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

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

I think it wasn't clear that

O(26 ×R×C^{2}) would pass for problem E. Exact number of operations is . I used hashing to get it inO(R×C^{2}) after wasting so much time.Btw I can see other user's submissions.

Edit — Above comment was edited.

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

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

Why Pending System Testing is still lasting?

Disgusting problems :/

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

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

But do people really like it?

todays contest was about maths and implementation..XD

How to solve F?

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

Thanks. Got it after reading your code.

Why not let system testing start?

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

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

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.

System testing started!System testing is in process, at last.

problem B are similar to 486A

The two problems are very similar...

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

That's also right;

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...Thanks for the duration of 2h and 15 min . I managed to submit C at 02:08 .

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.

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. ^^

re because of 1 character :(

poor U !

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

How to solve problem E?

AC O((n*m)^2) 420ms. 46184740

fully calculation based, though set was cool

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

i dont understand