Hello, Codeforces!

I'd like to invite you to Codeforces Round #354 (Div. 2). It'll be held on Wednesday, May 25 at 18:05 MSK (Moscow time) and Div. 1 participants can join out of competition. As usual round starts in the **unusual** time!!!

Me an Grigory AGrigorii Akhremenko prepared the tasks for this Round. It is the debut for Grigory as the problemsetter.

Great thanks to Gleb GlebsHP Evstropov for helping us preparing the contest, to Mike MikeMirzayanov Mirzayanov for the great Polygon platform and for Ilya IlyaLos Los and for Artur ikar Svechnikov for writing solutions.

The scoring distribution will be announced later. Good luck everyone!

**UPD** Score distribution **500-1000-1500-2250-2250**

**UPD2** Editorial

**UPD3** Congratulations to the winners

**UPD4** See you soon!=)

Will it be rated? It is not stated so I think it's a valid question.

Sure

Hello everyone! I am red_black boy!!I make a mistake.I am Black_red boy!!## I will beat everyone today.good contest hahahahahahah....

Are you five years old??

If you are red_black boy, what can you do in O(log N) ? :)

why in each time when GlebsHP helps preparing the contest , problem C be easy :p

He is now codeforces coordinator, so he helps in every codeforces round, that has nothing to do with Problem C :D

Are you sure? Look at this round and at this problem.

Div. 2 only contest, which means loads of fake new accounts of Div. 1 people... :(

This is bad. Those who are in Division 2 will not be able to rise, as will constantly play fake members of the first division.

the people from the first division. Please participate only out of the competition!

That's not true anymore. After the rating revolution the number of fake accounts decreased significantly. There was less than 30 new accounts in top-1000 in the last two div2 only rounds, and most of these are not fake for sure.

Although there are just 30 new accounts, but many contestants of div1 have many accounts which had rated. So there aren't only 30 people of div1 use div2 account to participate this round.

Why?They can also participate with

asterisk.Maybe because they love the feelings when their ratings make a big jump (who doesn't, right?)

Like me :)

unlucky , i can't participate in this contest because the electricity power cut off from my home at start time of this contest .

Sad story.

Maybe that's good for your rating...

and maybe not

It maybe my first contest in codeforces, good luck to everyone.Good luck, I think you are excellent and beautiful.

Friend-zoned people everywhere ^

Thank you.

I have a feeling you will rank the top.

Let's see if I am right after contest.

Just a feeling , take a look at his submissions and you'll be sure :D.

You must take a mistake, and I am a newbie.

You must be joking.

I found you using advanced techniques in ur submissions.

Mo's algorithm, I don't think a newbie know this algorithm.

Do you mean the mo's algorithm is advanced technique? I really just start to study Algorithm for one month....

Okay...

Good luck to you, xiao ai.

Good luck. My first contest as well. :)

Good luck to you.

This my 4th time to take a round. But it's my first time to find the round announcement before the contest... I wonder Why their is not a link to this announcement in the contest page...

Is Delinur still a translator in Codeforces? I feel I haven't see her name in a round announcement for a long time.

Unable to parse markup [type=CF_TEX]

$Oh god, I have two university exams tomorrow :(

But wait a second, stupid university exams won't help me reach the AMC-ICPC :V :V :V

I'm in :D :D :D

Now back to the exams :)

Exams are stupid, they can still wait :3

This contest may become my debut. I looked at your profile and I saw you make contests with more than 5 tasks. Will this hold for today because I want to solve as many problems as possible?

Can't wait to be a candidate master.

So am I. Best wished to us. Good luck & have fun.

Congratulations! You did it

Thank you

You guys are pretty close becoming a candidate master. I still got a a lot of work to do! Best of luck!

Good luck to everyone:)

Hope you all have a great leap in your ratings(which is impossible)

Challenge Failed, Congratulations!

My memories of usual Codeforces' rounds are fading... Usual time? haha! BTW I like contests being held at 8PM MSK. It's a good time for me. I wish it was the usual time.

I wish it wasn't, 8PM MSK is 1:00AM in my local. It's very bad.

At least you can sleep less and participate, in my country it's 12:05pm. I normally work at that time. I wish it were at 1:00am, I would participate a lot more!

I like this time too. I have high school students work on it and it is 11 am EST which is when the class is. It was perfect!

Study for Exams or Codeforces Round? why am i even thinking about this :D I am in

Good Decision! A few weeks ago I had the same problem. I decided to go for CF. Got 80+ ratings :)

Though I have an exam at University, I am not thinking about this. Absence in a CF round give me much pain than getting less mark in exam.

Damn I have 4 exams tomorrow... Shit I forgot I finished school

wow! problem D, E got the same score? D must be hard.

or E might be easy

or both

or none of them :D

very easy problems

Seems fine — only 249 people solved D and 105 solved E.

Nice contest.

solve E ! it's the best problem also easy as E

E is easy if you know a thing or two about polynomials (namely, that the remainder when dividing

f(x) byx-kisf(k)).However, I didn't find any non-annoying ways to check whether

f(x) is divisible byx-kif all the coefficients are already known...You can calculate it modulo a couple of random numbers or primes. That will nearly always work.

I don't know if there is a nice way to do it without randomisation though.

To check if f(k) = 0, note that f(k) = a0 (mod k). So a0 must be a multiple of k or f(k) cannot equal 0. So you can add a0/k to a1. Call this a1'. But then the new a1' must be a multiple of k or f(k) cannot equal 0. So now you can add a1'/k to a2.. and so on.

Are you using floating point for this? Does that not give you issues with precision? Or alternatively, give you very large fractions?

If a_i is not a multiple of k, the algorithm terminates. You only divide a_i by k if a_i mod k is 0.

I don't know if it worked... but I just used python and did it in O(n) :D (python handles big integers)

I'd love to see Python handling 10000

^{100000}in one second...If he used Python2, the multiplication would have just overflowed, and he may have been lucky that it worked.

Hodor :v :p

how to solve B?

Create 2D array for your glasses, put T * CONST (e.g. 2048) water in first one.

Iterate from top to bottom, layer by layer. For each glass substract all water that left (higher than your const), split it by 2 and add to two glasses on the bottom layer.

Count how many glasses have >= const water in it. O(N).

We use CONST to avoid of float computations. It should be power of 2, enough to fill all levels.

Ээх, я не додумался, что через T * CONST можно все к int-ам свести.

I put 1024 water in the first one and used the similar approach that you told. Is there any problem with 1024? Since the first and last glasses of the last(10th) row will receive 1 unit.

It should be enough. But you should put

T* 1024, not just 1024.I use double,is my solution wrong?

Well it depends how you implemented it. With double and division operation you could get wrong comparisons. With integers it will be always correct :)

For what I know, such dividing by 2 cannot cause precision problems with double (it behaves the same way as bit shift), so it was safe in this task. But its a bad habit for sure, I agree.

Ya I meant for each second I passed 1024 units on the first glass and then repeated the process for T time

Hack testcase of E?

I think K=0.

i handled it still it got hacked

There are still different cases when K = 0. Think about the case where all

A_{i}= 0 but one is '?'is there any case for K = 0 other than

* a[0] is already 0 "Yes"

* a[0] is nonzero but not '?' "No"

* a[0] is '?' and its human's turn "Yes"

* a[0] is '?' and its computer's turn "No"

?

If all

A_{i}are 0 then it should be "No"the question says P(x) is divisible by Q(x) if there exists a representation P(x) = B(x)Q(x) . if all A[i]'s are 0 , then if we make B(x) also a polynomial with all coefficient's as 0 , then wouldn't P(x) be a multiple of Q(x) as well?

How did you handle overflow? with modulo of some prime?

i just took 4 prime modulos

Share your approach for C. Your code is pretty simple ! @rajat1603

Take the Case when we want every element of the subarray to be equal to

a. (For other case just change allatobandbtoaand run the same algorithm again).Now consider

ato be 0 andbto be 1.We want to select the longest subarray with

sum≤K.So we take a right pointer and move it from 1 to

N.We also maintain a left pointer denoting the left endpoint of the longest subarray ending here. When sum exceeds

K, we move the left pointer 1 step ahead.So now we have longest subarray with

sum≤Kending at every index.Thanks !

Any fixed prime modulus can be hacked.

Huh! 10 seconds left, i submitted. The result on final page: Pending system testing DAMMMMMMMMMMMN. Now i don't know whether i should be happy or sad in case it passes after i submit later on :\

I think it will be counted if your submission is in queue before the contests ends

Now it isn't in my submissions too. Though i got redirected to some link with some token value at the end but probably there was a bit of lag b/w my submission and before server received it. :(

Is there a nice way to solve E without randomization?

Gorner's way)

Gorners?

Other than my reply to your other comment, one more option is to observe that if the absolute value of the partial sum becomes greater than some small value (roughly 10^4 / k-1 or 10^4*n if k is 1) then it's impossible for it to come back to zero. So you can just terminate if that happens, and otherwise proceed as normal, so you'll never get overflow.

It was a good contest with easy problem, but I could solve only A :D , i couldnt find the formula for B(i think it's something bounded with pascal's triangle ). How you solved B and C ?

That is what I thought, but I found to many exceptions in it. So I just simulated it.

It is easier to just use dynamic programming approach to solve it in O(N): http://codeforces.com/blog/entry/45031?#comment-295709

I have three big critiques. Problem C was given before and I could hack it easily. But I didn't. Problem D is awful and easy to come up with a solution. Nobody likes such problems. Problem E is easy.

Ok, so you know that problem C was given before, even though this 5 problems are the first that you solve in Codeforces? Suspicious...

Illuminati?

What I want to say is that the problem is a common use of 2-index technique, I don't mean it was on Codeforces. I don't solve Codeforces, I only solve hard problems and this contest was just to test my level.

I was trying to hack A and I wrote the exact same code of other contestant and tested it on custom invocation. It gave a wrong answer but I got unsuccessful hacking attempt. Anyone knows why?

Sorry, my bad! Everything is ok!

I solved D and found contest just finished for a few seconds...

I hope my solution has some bug so that I won't be so sad...

BTW, D is easy to come up with a solution but not easy to code it, I don't like such problems.

Well, if you are experienced enough, there's nothing to struggle with:

30 lines of switch-case to rotate a symbol clockwise 20 lines of creating edges to adjacent cells given a symbol 40 lines of bfs + misc to read/write

In total, not too much

if you know what you are doing.What I usually do — I just start coding, and quite often it appears that it is not so hard as I expected it to be :)

you are right, I'm not so experienced in program competition. When I write a solution having code above 100 lines, it often contain some bug(maybe stupid typing error like typing i for j ...), I need to do more coding. This is a nice platform :)

You should check some solutions out. E.g. mine uses only 1 line to do rotation and 5 lines to generate neighbors.

Mine failed, so yeah all cool now :P. 2 silly mistakes. I wrote somewhere 'V' and somewhere as 'v' and other i didn't checked that to go from a to b, a path from b->a and a->b must both exist.

Who the hell thought it would be a good idea to put problem D -_- like... What's the purpose of it??

with all due respect to authors

It's a good exercise in implementation.

Well, I kinda don't like it too. Easy algo (just BFS), but requires careful implementation of all cases.

That's the purpose

pretty ugly ruined my round because of a silly mistake :/

Anyone else got WA'd / TLE'd in D test case 10?

I got WA too.

Well I did get it, but fixed later. I've used too much memory :)

Did you use NxM matrix to store distance for each state in shortest path algorithm or NxMx4 matrix? I used both, with NxMx4 i got TLE and NxM got WA :(

In last submission I used NxMx4 matrix of int64 to store distances. Plus one matrix NxMx4 of int8 to store direction flags. Plus three queue's of int32 to queue positions. Around 50 Mb total.

I used simple BFS.

Just got it AC after systest, 1500ms and 50Mb.

I guess the problem is that i used Dijkstra's then. Never thought about state graph being unweighted

I don't think the size of the array is the problem. I used

`4 * N * M`

and it was fine.sad...fst 2 problem..

Why GlebsHP accepts rounds with such classic problems like those in today's C, D?. I thought the round will be cool because fcspartakm is the problem setter but found only one good problem. :D

Please, wake me up if the problems of Div. 1 contests will become easy and classic for you.

even for a div2 contestant, i spent 3/4 the contest time coding / debugging instead of thinking , i didn't enjoy this contest at all, the only good problem is the E and didn't have time to read it tho

Just read D and E and the same time. It often happens that one is harder on implementation and the other is harder on the idea.

I'm not saying they were easy or they should be hard. Just saying it'd be better if they were kinda unique.

Just when I saw C has more submissions than B, I knew something was fishy. And it turned out it was similar to Hard Process(ER 11) and Repair road. Problem B was also based on how good you are at google search(But I was unable to solve it :P).

I solved hard process today only :D

how to solve pC?

i choose odd ones to connect left even one and right even one.

scan odd ones from left to right

then choose even ones like odd ones

but stuck at pretest 12

If we divide the problem in two parts and return the max of both:

After that two pointer approach can be used to solve each subproblem.

Fill consecutive gaps of A OR Fill consecutive gaps of B. Find maximum among both.

In problem E, if you use fixed modulus then you can get hacked. For example, if you use 10

^{9}+ 7 and 10^{9}+ 9 as modulus, write (10^{9}+ 7) × (10^{9}+ 9) = 1000000016000000063 in base-10000 number system so we get "4 10000\n63\n0\n160\n0\n100" as a hack case.Now I came to know that my solution will fail in system test!

Can someone debug this code for D?

My logic should be fine, but I get WA on #10(hate implementations) Logic is to BFS the graph with 4 states for each node(representing number of rotations).

CodeI know, the implementation is pretty messed up, but I did comment a little bit if that helps

18085379 Why do I get WA? Anyone care to help me???

Your recursive Fill function does not exit early enough, it continues "pouring" water past the n-th level. Change

`if (i>9 || j>i) return;`

to`if (i>=n || j>i) return;`

. Then it passes all tests: 18093994Can you see the standing without the starred people from div 1?

Just untick show unofficial located on top — right corner of standings page. :)

Auto comment: topic has been updated by fcspartakm (previous revision, new revision, compare).About D: You know what "X" and "Y" usually mean on a 2D grid? You have some idea, right? I can not imagine why the problem statement for D was written with the exact OPPOSITE meaning for those letters. Got WA for this, upsolved after swapping X and Y when reading input. Is Codeforces supposed to be a reading competition?

I agree, a painful mistake. For me it has always been misleading — we store 2D maps and grids as arrays of rows, so if you want to access column X and row Y, you should call Array[Y][X] <-- counterintuitive, isn't it?

What works for me: just change your perception and think of X as of the first coordinate and of Y as of the second one — then array item access becomes logical — and meets the problem author's expectations.

In my memory in the majority of tasks which has x,y in GRID in statement it is alwasy that X — row, Y — column.

My memory is the opposite.

When this happens

when I see such large pictures, I shit bricks...

You guess that you can change your 'V' into 'v'.I have made a same mistake.

Holy fuck you're right. I have never been so stupid in my life. :/

Thanks a lot guys for your efforts and splendid problems :) AGrigorii, an awesome start! — looking forward to see your next rounds in future.

Problem C is a bit more sophisticated version of 645C - Enduring Exodus. Same idea, but instead of finding the minimum, you ought to find two maxima and compare them. There is also a possibility of

kbeing 0 in today's one (many solutions got hacked/WA'd because of that).It's exactly the same as C from EDU11 that happened less than two months ago.

Why there are no precision errors for problem B with solutions based on double data type?

For example in my room, 18074368 solution.

Sorry for my poor English.

All the numbers are dyadic rationals, which can be represented exactly by doubles.

I suspected that, thanks for confirming.

Wow, next contest is also Div.2 Only. And it's only after a whole week.

I find no reason for a Div 2 only round. It simply encourages more fake accounts.

Here's a reason: It takes more time to prepare a Div 1 round.

When the ratings are calculated?

Your question is NP-hard

I participated to this contest , but when i go to my profile, my rating is still 0 and the contest it's not showing in the contests tab on my profile. Please help !

Wait for some time. The ratings are not yet updated.

I nearly got my first ever "5 out of 5" on codeforces, and then I fail task B on test 83 ;-(

Is it possible to make contests on weekends?