Greetings to the Codeforces community!

Regular Codeforces round #355 for participants from the second division will take place on 1 June, 19:35 MSK. Participants from the first division are able to participate out of the contest.

It is my third round on Codeforces. Hope you will enjoy this round.

I want to thank Gleb Evstropov (GlebsHP) for help with preparation of this round and Mike Mirzayanov (MikeMirzayanov) for great Codeforces and Polygon systems.

Participants will be given five problems and two hours to solve these problems.

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

**UPD** Editorial is here

**UPD** Congratulations to the winners!

Div. 2

Div. 1

nice and short announcement I think one of the problems is about shortest statement :D Have a nice contest ;)

Good LuckFor AllDo you have a children's Day today?As a 8 years old's black_red boy, I must be the king of this contest ((유∀유|||)) .Are you really 8 years old's boy? Why your profile displays you are in Sichuan

university?Maybe he just want to get the last place in the contribution list by collecting down-votes.

No, you are absolutely wrong.I just say the true things.

Could you do me a favor?

Please close it :\

I think you are not black-red!

You are brown!

What is the meaning of Brown?

brown

I am offensive and I find this brown.

Keep those lame joke away from codeforces!!!!

no i have not children's studied in University like your profile Displays , just go there and play around the black_red trees :p :p

Probably born on leap year, celebrating birthday once in a 4 year, so its 32 years actually

Good luck everyone! I hope that I'll jump to Div.1 tomorrow and never return back to blue again...

It's pretty much not possible returning back to Div.2 when there is no Div.1 rounds whatsoever ;)

exactly ! :/

good luck tweety :D

Good luck Tweety. Have a nice day

Good luck :)

Congrats tweety :)

Almost did it. The only remaining part is not returning back :P

Wish you happy journey in Div1

Don't ever forget us Div 2 people :P

is it rated?

here he comes...

phrasing...boom :)

You know, It's not funny anymore..

I'm still giving them up-votes :)

Regular Codeforces round means that it's rated.

finally , there he is

This joke has been over-used, and you have to come up something new!

Vanya is in the house

Yes,

the round is rated:pThis is answer is for those who are gonna ask "Is this rated?"

I am trying to solve problem from your past rounds, but when submit ( 18173020 ) it say

Denial of judgementIs the package for this problem crashed?! what is the problem in my submission?!

UPDthe problem fixed.How come Wild_Hamster's profile says his last visit was 5 days ago when he posted this 11 hours ago?

A Codeforces Round in it's usual Time now that's new :D

This contest is going to begin at 00:35 in china.It is too late, and staying up late is not good for my skin.but I really want to be a blue

xiaoai.Man, I'm in NZ and I have to get up at 4:30 for the rounds

She is a girl

There's a girl who's considering participating in a contest at 00.35 just to earn rating? I don't think so.. :)

In fact, I am a girl.Why do you think a girl doesn't be eager for earning rating?

Oops, I was wrong then! But you can't deny that there aren't many girls who would do such thing. Anyway, good luck for the contest!

@Deemo because of your profile picture , I have always thought that you were a girl

and I had crush on you :v

am I the first man who had crush on you ? :p

Yes, you are the first one that I know about :D I had a similar feeling for Doreamon though, so I know how you feel :))

I also thought Deemo is a girl. Then I saw his name...

me too ! oops :D

That's a pity.Hope you have a great advance.

I play it, and feel not good too.

Nice & short announcement . And Hope to have some nice, short & easy to understand problem statement . And all the best to every participants for today's contest .

Let div1 round too. Otherwise, too many fakes will div1 by the participants.

Too bad it clashes with another Yury_Bandarchuk's div2 oriented contest on hackerearth (everybody knows it is held on the 1st of every month).

Not everybody. I didn't know. And I tried to schedule contest in such time, that it doesn't clash with another contests:

May 28 — Codechef&gcj

May 29 — RCC&gcj

May 30 — SRM 691

May 31 — csacademy beta round #6

June 2 — Hourrank.

Hope this round will be my first 4/5. God bless me ^_^

Yea I want that too!

and it's again 3/5 :(

me to...

Even I want that

Do not want 4/5. You should solve at least 5!)

Your previous rounds had all math problems. I hope this time there will be more balance :D

Yes maybe all problems related to data structures. Please no more downvotes I am sorry no data structures only maths.

[DELETED]

Why people are against data structures problem?

I don't get it either

I

lovedata structures problems.Yes, I agree with you. Let's hope this time around, we get some nice problems of

algorithmicnature. After all, this is Codeforces, not IMO.The email I got said that this was going to be 6 problems in 2.5 hours. Is it 5 problems in 2 hours or 6 problems in 2.5 hours?

Lots of math problems are coming I guess :)

Let's hope lots of

algorithmicproblems are coming.Let's hope lots of problems are coming.

Five problems are coming.

ok then let's hope that 5 algorithmic problems are coming.

Winter is coming

Summer and Spring will also come.

Ok, then hold the door!

Let's hope we can learn new things from this contest :)

Not Lots of Problem, Maximam 5 Problems :)

You are right

Lord Commander:DWild_Hamster interesting profile picture :D

Recursion :)

Any update about score distribution? Or is it standard?

Good luck everyone! :)

what about score distribution ?

Links to hack submissions do not open in >ten minutes.

Omg, I'm so stuck on C. Thanks god it is not rated round for me.

My naive dp soln passed. http://ideone.com/GfTCm3

Here a short solution. 18194600

Thanks very much for the great round! In my opinion, the only criticism is that the difficulty gap between C and D was too large.

How to solve D? Obvious DP gives TL 19.

I get TLE on 19 too, and waste the rest time dealing with this, still can't solve it

I too got TL on 19th case by dp.

I was thinking to sort the elements of each type according to their dp value. while traversing we could stop beforehand if it is guaranteed that the other elements would be more expensive.

I don't know if it would pass or not. But I didn't get any time to implement that.

Please share your approach if it worked.

I got TL on 19 too, and I tried to improve my solution exactly as you wrote — unfortunately I was in a hurry and got WA on 10 due to some mistake. But I believe it should be good enough.

I tried after the contest got over. Still stuck on 19th case

This was my solution during the contest but it was TLE as well :)

I was too slow to code it, and never coded Dijkstra before. But my approach would've been making a directed graph with starting point having edges to all 1's, all 1's having edges to all 2's etc. and then do Dijkstra from start to P, that should work right?

That would still get a TLE as the number of edges in the graph is too high.

Nope, it won't work.

I am using a similar approach as yours, the limit will be the case where p = 3 and there are 45000 elements with p = 1 and 45000 elements with p = 2, in this case it need >2s to finish so it will be TLE. To speed up the algorithm, keep the points with p = x grouped by their x-coordinate and y-coordinate respectively, then for each point with p = x + 1, we dont need to traverse all of the points with p = x, we can traverse each column and each row and find the best one using binary search, so the total time will be O(m*n*max(m,n)logn)

Are 99% of hacks on Div2B are of integer overflow?

Yes. :) That is how I got my 5 hacks.

that's why i implemented it in python.

Waiting for my D to fail...

How to solve D faster then O(p*(mn)^2)?

I wrote solution in O(n*m*n*log(m)). But it's not fast enough :(

Dijkstra?

Segment tree on each row to find minimal value

Actually, you only need to keep track on at most one value for each row.

Can you explain your solution?

Why Velter? Your solution is fast enough to pass the final test :|

It's a good question :D But TLE on 16 pretest

no. my solution is olso O(n*m*n*log(m)) add it got accepted CODE

I had a solution with time complexity O(p*(n*m)), but it failed at pretest :(

I think I got O((mn)^2) by just finding differences between n+1 key and n key, still not enough (for Python at least, I think 45000**2 might be OK for C++)

It won't be enough even for C#/Java/C++.

Even for magic, 'cos 300^4 is 81*10^8

I think you solution is actually O(n^3) ,just like mine, but this is too slow even in c++. I get TLE in case 19 too.

N^3 should pass easily in like 100ms on worst case. So probably it is not N^3.

I think the worst case is p = n = m = 300, and 300 chest for each type. But it's just intuition, Maybe case 19 is something else

It depends on algo used.

For some algos worst case will be p = n = m = 300, 44851 chests of two types and 1 chest of every other.

44851 chests of two types you are right, I didn't notice this case..

Worst case is when n = m = 300, and p is 4-5, so it's 20k * 20k * [4, 5] > 1.6kkk

you are right, I'm too simple

I think I missed D by seconds!

I hope my solution doesn't pass. I was taking the limits small.

I was getting TLE on 19th case. How did you manage that?

So uh, how to solve D? I was trying to think of DP but couldn't.

IMO , for a point you need not check every Other point with value 1 greater. Check all the rows and columns that form a border across it!

DP + Square Root decomposition

In the optimal path, once you have collected the first

kkeys, you should move to a square to collect thek+ 1th key. Thus we can divide the entire matrix into layers whereith layer consists of the co-ordinates of the matrix where such thata[x][y] =i.Maintain a value for each of these points -> the minimum distance traveled to reach it.

Now we need to do transition from layer i to layer i+1. A brute force implementation for transition could take

O((nm)^{2}) time. Thus we take two cases -> If the size of the previous layer is greater than (nm)^{0.5}and otherwise. If it is smaller than (nm)^{0.5}we can do bruteforce, else we do a BFS withcarefulbook keeping. Overall complexityO((nm)^{1.5})Hi, sorry if this is a stupid question, but what exactly are we doing in the BFS. I mean if we're doing BFS to find cells of the next layer wouldn't it still be wouldn't the BFS still be O(nm)? I read the editorial and it uses the same approach but I don't understand it.

A BFS from layer i to layer j will take O(nm), but you only do it if layer i is large (larger than sqrt(nm)). Since the total number of chests is nm, you can have at most sqrt(nm) layers with size sqrt(nm).

O(m * n * m * log(m * n)) with list + binary search and a little lucky!! :D :D

Problem

Cwas very hard to understand. But B was hackable so I liked the contestI hacked by you :( stupid mistake

Yup it was..i misunderstood the statement and took me a while to solve it.

I was constantly getting wrong answer on pretest 4. Any possible corner cases? I thought of all possible scenarios, could not find anything :(

same here.

Test case 4 is 5 5 5 4 2 1 2 3 3 4 4 2 2 3 4 1 2 4 2 1 5 4 2 4 3 1 1 2 If we start with 4 key then we can straightaway go to key number 5 with 5 moves!! Why is the answer 9 then?

You must go from (1, 1) to key 1 -> 2 ->... -> p ;) ;)

I WA in pretest 4 and after that I read threads again: "All key 1 open" (not (1,1))

Problem D: I have Dijkstra in O(mlogn) approach based on std::set which don't passes 19th pretest. Starting vertex is cell of P type. Please any help, comments about my owful code 18199256 or your solutions for this problem.

The number of edges is very high, dijkstra is too slow.

D seems like some pro shit. When's the tutorial getting posted?

no matter how much i tried it got TLE

pro shit seems required

Basic ideas of D was pretty simple, you can solve for rows and cols independently.

EDIT :

this is wrong.Can you please briefly explain how to solve D?

Posted

What am I doing wrong at problem C?

https://ideone.com/fOMtB2

Your line with pow is incorrect. Take a look at Editorial

First u need precalc all the possible results, and count it in a map(or vector) Finally, multiply all the values (mod 10^9+7) example:

s = xyzw

ans = (m[x]*m[y]*m[z]*m[w])mod (10^9+7)

18194600

Nice round, I have already failed C in system test in the last 3 rounds, hope this time I can be lucky :D

I failed my B this time T.T

How the hell there are more submission for D than E?

that feel when didn't even get to read E because I was stuck on D. :(

I really hate when I miss to notice integer overflow, then get hacked 10 minutes before contest, after which I have to resubmit, thus losing 350 points. The only good thing is that after this I managed to hack one other solution :) so I got 100 points back

It's better than not getting hacked at all and never realizing it :/

You're right, but still it is better to notice overflow as you write the solution, not 1:30hrs later

Annoying how a simple overflow can change my ranking from 150 to 1000

if D turns out to be simple i'm going to shit brix

I can't understand C

is there anyone that explain for me?

i spend most time to understand it..

same here.

You get very long number in input. You should translate it in binary representation (6 bits per char in input, total max of 600000 bits), lets call it A.

After that you should eval how many unique pairs of (X, Y) exists, so that X & Y == A. Where & is binary AND.

Find & of all pair of values from 0 to 63 and then calculate answer for each character accordingly. Submission

i have a simple solution

just take every char in the string convert it to integer from 0 to 63

for every integer increment the total number of zeros by 6 — popcount(converted char)

then the answer is just 3^total_zeros

Here is my submission : http://codeforces.com/contest/677/submission/18195929

Same here, i couldn't understand it until the last 15 minutes, and got Accepted in the end :D

Why all hacks submission was on

Bproblem ?In D i was misunderstanding that it has the (1,1) chest initially.That passed three samples....TAT..

*chest

You can edit your comments.

it's Candidate Master workaholics

Thank you. :P

Same here. I tried my effort to find the nearest p+1 in eight directions for each p just like Manhattan spanning tree, submitted just before contest ended, and got WA on test 4 :(

UPD: It seems my solution doesn't work, which got WA on test 14 :(

There will be some mistakes? I thought that the proof of Mht mst based on the points were not in order. But in this problem the points are in a specific order.

Of course it is incorrect, which would fail when the optimal path is on a straight line.

I tried the nearest 200 points for each p , ans I got AC , I think perhaps you should try more points :)

How to solve problem C?

Realize that.

1 & 1 = 1 //One way to get 1

1 & 0 = 0, 0 & 1 = 0, 0 & 0 = 0//Three ways to get 0

For the pair of strings to find a and b Lets understand that if a&b=1 , then there would be 1 in both. For a&b = 0, it can happen in three ways 00 ,01,10. As number is less than 64 , it can be represented with 6 bits. So you should check the total number of zeros in every number of 6th bit representation. So ans = 3^tot.

First u need precalc all the possible results, and count it in a map(or vector) Finally, multiply all the values (mod 10^9+7) example:

s = xyzw

ans = (m[x]*m[y]*m[z]*m[w])mod (10^9+7)

18194600

I love the contest! Surprisingly most of the problems have a simple way to solve :D.

Oh my god your username is the GREATEST. LOL

Correct me if I'm wrong.

Task E: nothing prohibits non-positive d (it says three

integers, notpositive integers). With non-positive d set of items under given constraints is empty. So, technically, answer for all zeroes must be one and not zero?My solution that prints 0 passed, and I think some solutions that printed 1 failed, seems not fair if I'm right =)

Problem B says, that each second Vanya does the following:

1) If there is at least one piece of potato remaining, Vanya puts them in the processor one by one, until there is not enough space for the next piece.

2) Processor smashes k centimeters of potato (or just everything that is inside).

So at each second Vanya checks if the next piece can be accommodated. Most of the solutions that I saw, first add whatever can be accommodated, and if at i_th index, ar[i] + remainingAmount > h, they add to the answer remainingAmount/k. But it is also possible that after some seconds that is less than remainingAmount/k, we get enough space to accomodate ar_i. It is clearly given that Vanya does the above two mentioned things each second. Do both of these solutions give same answer? Am I missing something?

Can you please explain the time complexity of problem D?

How do you people solve problem E?

I thought 1000

^{3}divided by a good constant is just fine for three seconds, but my initial attempt took 2x more. Eventually, I managed to squeeze theO(n^{3}) solution into the time limit. Perhaps it's even easier with a superior optimizing compiler such as GCC.For each center binary search the maximal radius such that you don't pick up any zeroes. Count the number of 2's and 3's in a cross with this radius. Use partial sums to quickly get number of 0's, 2's and 3's in a cross.

Thanks. That's and not much more code than

O(n^{3}) with the 45 degree rotation — nice!I will not use int anymore, I will write all my future solutions using long. this is the second time I fail system test because of using int. is there any disadvantage of using long?

Memory Limit

Multiply operation is a little slower than int.

Problem D is solvable by Dijkstra? I get Memory Limit!!!!!!! :/

Any idea?

#fastreading

2016-06-01 19:35:59

Shouldn't've submitted much later :P

that's fantastic , I hope once I can submit one like this ( and get it AC ofcourse )

I think that D sucks a lot. The time limit was chosen very badly. Some solutions with the same complexity: O(n*m*max(n,m)*log(n*m)) passed and some failed because of that.

Besides author provided theoretically strong pretests. People got busy trying to improve their solution as it was getting TLE on pretests. It created an impression that the pretests are strong in terms of performance and once you pass them you should just worry about the correctness.

Surprisingly I spent some time optimizing my solution just to discover that it was failed because of tle in the final tests.

Either time limit should be higher — 3 seconds or pretests should be weaker so that nobody wastes their time improving something which was going to fail anyway.

I didn't analyse many solutions and you may be right about adjusting TL. But, I don't agree about pretests. It's awesome that pretests were strong and it should help many people. People with slow codes can check their solutions with Custom Invocation anyway. So, in general they shouldn't do it not to waste their time? It's risky to implement complexity which won't obviously pass and one must take it into consideration. I don't see why telling someone "hey, your solution is wrong" is bad. I know that later there is info "hey, your solution may be OK because passed pretests" but it doesn't guarantee anything.

I think that I was one optimization away from the acc, so if the pretests were stronger it would be also ok.

The problem is that they were chosen in such a way, that they were engaging people in solving this problem. Contestants were spending time trying to pass pretests instead of solving other tasks. It was a false help. If they were stronger it would be a real help. If they were weaker, nobody would complain about it as passing pretests guarantees you nothing. But also nobody would bother spending so much time on this task.

Besides we are speaking about n*m*max(n,m) (obviously pass?) and n*m*max(n,m)log(n*m). In my opinion both should pass easily. If somebody is trying to differentiate solutions worse by factor of log it means that he wasn't confident that the problem was difficult and interesting enough, so he made time limit more restrictive.

It was a false help for some participants, a useful help for others (I had many things wrong and catched them one by one, thanks to pretests). That being said, I see your point now. But I think it's hard to adjust pretests so perfectly.

Unfortunately, if you want to allow

O(n^{3}·log(n)) to pass easily, then it may also allow squeezedO(n^{4}) to pass. I think that the chosen constraints were ok — there is intendedO(n^{3}) (passes easily) and one may risk and writeO(n^{3}·log(n)) carefully, to also get AC. Fine for me. One may get TLE a few times but in the long run it isn't a big deal and I don't see a better solution.Okay Wild_Hamster, you beat me this time, well done!

it's your 2nd contest , take it easy , it took me 55 contests to get here and you just did in 2 , you're a monster hahaha , div1 is waiting for you next week good luck .

Thank to all for such contest. It was really unexpected thing for me to be in top-10. :D

I was writing it normally, solved ABC, then got TL #19 on D. Then I thought: "I need to get maximum points here" and started hacking. :D When I opened my room there already was a guy with 1 hack. After 1 refresh I saw +2 near him. Then +3 were near me. :D And when I only refreshed my page, it said "Sorry, your balance is X, you can't surf internet anymore". As you already understood, X is some negative number. :D I ran from home to nearest terminal, which is not near my home, :D put cash for my dear internet provider, came back, made 2 more hacks, optimized my TLed D solution in some shitty way and it passed systests. :D

Try to tell this story better and you can pick up girls with it.

Savage :D

That much dedication.... therefore you are in Div1:)

Perfectly right submission http://codeforces.com/contest/677/submission/18209483 calculating 3^n. WTF test 9 has no input. I was lied. they said length was more than 1? In contest solved two problems but shouldve used long for t in 2B but i used int for a perfectly correct answer :(

The input is a lots of underscores ('_'). You should have processed the input char by char instead of using slow BigInteger class.

oh great thanks.

is there anyone that explain to me D?

testcase #4

5 5 5

4 2 1 2 3

3 4 4 2 2

3 4 1 2 4

2 1 5 4 2

4 3 1 1 2

why answer is 9?

what i understand is 2: (1,2) -> 3: (2,1) -> 4: (2,2) -> 5: (4,3) thus ans = 7

you need to go to 1 at (1,3) first

Wow this contest was easy! Even a noob like me could solve the first problem in like 3 minutes.

Congratulations to

Div. 2user fake_fake who wins the round! 1st place from the 3rd try! Nice progress, man...