Hi everyone!

I want to present you the Codeforces Round #361 (Div. 2) that will take place on the 6th of July at 19:35 MSK. The contest was prepared by Gabriel I_Love_Tina Cojocaru and Mihail ThatMathGuy Tarigradschi.

I'd like to thank Dan danilka.pro Sagunov and Gleb GlebsHP Evstropov for their help in preparing the round and for making the round possible,Mike MikeMirzayanov Mirzayanov for the great Codeforces and Polygon platforms.

Good luck in the contest!!

UPD1.In this round you will help our hero Mike solve tasks he encounters every day.

UPD2. Editorial

UPD3.Congratulations to the winners of the round.

Div 1:

1.Um_nik

2.cgy4ever

3.anta

5.ksun48

7.Kaban-5

Div 2:

1.Sky4teen

7.fenchen

8.Grandpa

10.raiders7

Wow ! everyone got a "middle" name :) ;)

Ahmad

musa.cse12Musabatpari

Mohammad Abdullah

jackal_1586Matin Khan Zarzis## set a flag that I will increase my rating 100+.Hope not to hit my face.

so... i don't know about you, but I just hit my face :c

i hit my face last week too :<

Yah i'll try to do better than past.

I hope you will!Good luck!

i also. You too.

Wow really short announcement... I hope problem statements will be the same ;)

Yes i also think so.

For all muslims, this time we're gonna participate with our stomachs filled.

Eid Mubarak :D

To Cyan finally ! :V

Eid Mubarak

Good luck :3

we are eagerly waiting for this :)

Eid Mubarak Everyone :)

Eid mubarak.

The next day of contest will be Eid Day. Eid Mubarak everyone. Wish you'll have a nice Eid Day.

you too

What's better than a round at the beginning of the summer vacation :)

vacation's ending in India :(

I have two questions. Where is Delinur? I haven't seen that handle in announcements for a long time. And who translates problems now?

Sad but true. Delinur left Codeforces. I believe the translations are made by authors if they do not give any credits to other people. Or by someone else, by occasion.

Some info from Mike, by the way.

plz no more down votes:'(

no down votes plz! i will never comment again:'(

Will it be only in English?So, After a complete cycle(360 degree), this gonna be the first round in the first quadrant.

Codeforces Round

#(360+1)(Div. 2)It is also

19 squared!So it's about the game of Go :D

For all muslims .. Eid Mubarak

Hope the problems will be as real as your handle, I_Love_Tina, unlike something as "The family has 100,000 men give presents to each other."

Oh no, ThatMathGuy! I am never forget a problem on analytic and algebraic topology of locally Euclidean metrization of infinitely differentiable Riemannian manifolds!!!!

double check is quiet like to check:

Surprisingly, this is not really useless check.

But

nis integer, not float :)I think Zlobober is talking about the general case because in the current case there is no n at all.

http://ideone.com/AZFxab

http://ideone.com/ovOplK

Could you explain why ? Thanks. I thought there is no precision error so they should be equal.

Nan equals nothing, including itself :P

Thanks, I didn't know that double type has a special value(NAN) before

What about the first one? if(a[0]==a[1])

http://ideone.com/DRwCFr

Ohh!!! I didn't know that. Thanks :)

`

NAN :)

The time for this contest is too bad for us! Because it's 00:35 in China. What's worse is that I have lessons tomorrow morning,so my mother doesn't allow me to take part in this contest.I think i must take part in the contest secretly.But,if my mother find me doing this,I think my mom will clapperclaw me.How miserable i am ! Bless me not to be found，codeforces!

An addictive competitive programming is one which you cannot stop taking once you have started

Hope to do better this time !!

Contest just before Eid. It'll be interesting! Eid Mubarak everyone.

Eid Mubarak.

Ohh! a contest wrote by Moldovans , seems to be a good one !!

Eid mubarak....!

Those who have summer vacation, Happy summer vacation and Eid Mubarak to everyone wish you a happy, prosperous and AC life ;)

Always waiting for the hell-mode problem :3_thanks for your great test

Good luck Guys

Hoping to see some good problems and ratings up. All the best to all.

Nice & Short Announcement . Hope to have the Problems will be similar to the size of announcement and interesting.

All the best for all the contestants . Wish you a very high Ratings which makes the following festival much more interesting.

Recently I can't open submission code of old problems(Rounds before about 100), including my own submission. Anyone has any idea about this problem? Thanks.

facing similar problem!!

yeah I have this problem too ...

This round and every other round hero. Thanks to mike for the great Codeforces and Polygon platforms

sry for positioning of his head:)

Does anybody feel that the A problem is a lot harder than usual ???

Yes!! I am not able solve it :(

Yes, It's too hard.

Is it just me who thinks this round is scary difficult?

I've actually checked if it's div 1.

I've checked too :D

I think problems should be named like this

LooooooooooooooL

XD

XD

My dream to become Cyan has been destroyed :(

i'm becoming Newbie again

I think this round is too hard. :'(

This round has really made me take a I_Love_Tina check. ;_;

How to solve B? Dijkstra?

i solved with bfs

Simple BFS would do. Just think how you can make graph unweighted.

Got you. Thanks )

BFS

ad-hoc or dp like

BFS ! AS all cost are +1 for each node bfs to a[i],i-1 and i+1

Just add edges [i — 1, i], [i, i + 1], [i, a[i]] and find shortest path from 1 to i.

Simple BFS should do the trick. Keep an array storing the minimum distance from 1 to each node and initialize all values to inf and dist[1] = 0. Then, from each state, you can reach the node to your left and right with time=1. As well, you can reach the state which has a shortcut to in distance[1]. Only visit a state that you have never been to before and update the dist[] array as you go.

**Edit, when I wrote this, there were no replies. Guess everyone wanted to help!

Dude can you explain with some code?

http://codeforces.com/contest/689/submission/18935730

Dude, what is wrong in this code? My Code

yeah I used Djikstra.

Really nice round) Many thanks

How did you guys solve D?

I got pretests passed with binary searching, for every index, the segment that has the same min/max, and answering min/max queries in intervals in O(1) with RMQ.

I think it can be done using 2 pointer two... But the implementation might be complex(IDK).

n = 200000 and sequence is fill with same digit

what time complexity in your solution?

Can you please explain how you used binary search?

Let's count how many intervals are "good" beginning with i:

It will be some segment [l, r>, i <= l <= r <= n

The max_a(i, l) is an increasing function, and min_b(i, l) is a decreasing function, so with binary search you can find the first index l where max_a(i, l) >= min_b(i, l), and then with another binary you can find R, so that max_a(i, r) == min_b(i, r) for every i < r <= R

max(x , R ) is increasing with decreasing x. min(x , R ) is decreasing with decreasing x.

Now find lower and upper points where max(x,R)>min(x,R) and max(y,R)<min(y,R) . add y-x+1 for every R

O(N*logN*logN) gives TL on D :( . I was way more stuck on such an easy solution of B!Same here ! Got fooled into doing dijikstras ! :(

i used RMQ to answer min/maq queries in O(1), that didn't TLE

Yes. I thought that my solution with Segment Tree would pass. But I got TL 7 and rewrited it using sparse table.

My code has also

O(n*log^{2}(n)) time complexity. But it gets AC with 1419ms time. I used segment tree with binary search for all. Here is my submission. BTW I recommend RMQ solution withi(1 < =i< =n)O(nlog(n)) time complexity for this problem (because of the tight time limits).PS: The funny thing is that I couldn't solve it at the contest time because I thought both Mike and !Mike can tell the

Maximumvalue. Didn't read the problem statement well. If they can tell theMaximumvalue what will be the solution then? Anyone have any idea?If they both compute maximums, they will always output the same number. Just print n*(n+1)/2.

That's not true. For this case:

3

1 2 3

4 5 6

The answer is 0

Vhai in your solution how these two line works ?? I mean what is the logic behind this ?? when (p.fs-p.sc>0) lo=mid+1; ans else hi=mid-1; how the direction of binary search is selected ?

If we go to left then

max_{a}will increase or remain same andmin_{b}will decrease or remain same. Now there can be 3 type of cases.1.

max_{a}=min_{b}2.

max_{a}>min_{b}3.

max_{a}<min_{b}For second case we have to go to the right side because we want

max_{a}to be equal tomin_{b}. For third case we have to go to the left. For first case if we want the lower bound then we go to the left. For upper bound we go to the right.Nice round. How to solve C? Many people solved it very fast! I hope many A fail. :P

Binary search for least value of n that satisfies no of ways greater then or equal to m. At the end you need to check if this value is actually equal to given m or not.

what Right limit did u start with ? And how did u calculate it ?

i actually manually checked what value could give answer till 10**15. it was around 10**16.

EDIT: Screw this, damn i did checked this in a loop but since i coded binary search function first and then checked for this value, i forgot to update to 10**16. So it will fail final tests most likely :(

Srry for spoiling your party before sys tests :P

I just used 8 * 10

^{15}sinceMis at most 10^{15}.Long.MAX_VALUE should be a safe bet I think.

binary search to find n

I think that problem A has too week pretests. I hacked 5 solution and I will fail the system test(.

same thing but 2 solutions only hacked :D

Was fun finding the logic in different peoples A solutions ! Remarkable !

What was the hacking test cases in div2 A ?

4 9394

3 349

3 167

What would be the faulty logic in these cases?

for example, i thought only about this pairs: 1&0, 2&0, 3&0, 1&7, 3&9. My solution passed pretests and got WA69

I hacked one solution with 5 36984

Even my solution fails on this but unfortunately I cannot hack mine :(

You are really a hell_hacker if you want to hack your own solution XD

I hacked a 02

MAybe 40 also was missed

183 got a lot of people as it used the full 3x3 square but could be moved down to 460.

4 2469

hardest round ever!

finished coding D less than 1 minute after the contest ended

For me round was very interesting and one of the best in last time ! Thanks !

Before 30 seconds the end, i submit div2E and got WA Because i print with I64D, not I64d...

my input : 3 1 1 2 2 3 3 4

output : D

I'm really sad...

: D

In Div 2 A,

What was wrong in this

if there is a 1,2,3 and 7,9,0 in the string, then YES

otherwise NO.

2 17

The answer is "NO"

1

3

the answer is no.

1,7 should get a NO because it has identical finger movement to 2,8 and 5,0 and 3,9

very bad statement

I had to read E for 10 minutes before I understood the problem statement.

This really freaks me out!

I know that feel bro

wrong answer on test case # 4 :):):)

You probably forgot the backwards paths from point i to point i-1. I had the same mistake :)

i forgot this and costed me 3 WA but realised it later and got AC

I don't get this test, can you explain why the result at intersection 10 = 8 ??

solve 3 and 2 fail maintest...

I thought this would make me rank 2000+, surprisingly rank 800+ by just solving B :)

My Problem A fails for n=1.

Careless mistake sucks!

same with me forgot to put else before if in a condition and got A missed :(

Shittiest contest ever !!!

Tasks were fine by me, maybe A harder than usual, that's it o.o

Actually it was one of the best I ever gave....

Problem A and B was tricky.

the worst round i have ever seen

I concur

Can someone explain why I'm missing these two questions B: 18932534 edit : oops didnt read question

then just check c edit: ok i guess my lower bound is incorrect C: 18935173

`long long lo=m*6;`

You lower limit is too high. I just used 1.(edit: too late)

That was the bad contest I have ever seen

I think many people run when they saw Div2A.

Like this

I can't find mistake in my D. Anyone? :) http://codeforces.com/contest/689/submission/18935532

well first and foremost it's O(n log^2 n), which TLEs on systests

there must be a bug in your binary search, it's easy to get it sometimes wrong by +-1 or < instead of <=, etc.

I think that this contest is the worst only for people who solved only A. So you should study programming better. I liked this contest because of problems C and D. So thank you, I_Love_Tina and ThatMathGuy, for the round.

Well, I think all problem was great. but some description was too hard to understand.

Really thanks for problem setter.

A and B didn't pass, I lost an hour for them... But C and D are easy

Why pypy/python is so slow?? http://codeforces.com/contest/689/submission/18935945

I optimized my pypy submission so test cases 1-11 were each in less than 100 ms, but it still ran out of time: http://codeforces.com/contest/689/submission/18934688

Sky4Teen???? A fake Account + Shitty Naming Sense!!! :/

What is wrong in my soltion of Div2B: My solution

A subsection of your output: 15 1 2 After a shortcut you can go both right and left.

Didn't get you. Could you be a bit more elaborate? Also , I have changed my solution a bit but I am still getting a WA

Not sure, why, but if I add

`if (a[start] == end) return 1;`

after`if (start == end) return 0;`

, it works for testcase 6. However it is still way too slow.I think you don't cover the case where it's optimal to get to some node by jumping to it from a previous one and then going backwards

I have corrected it, but I am still getting a WA : Solution

Made a typo in A (used brute force and forgot that there are 4 rows and not 3) and failed A on systests. :D

But I still solved B and C so I have this going for me which is nice. By "this" I mean remaining in Div.2 for eternity of course.

Rating changes, come on :D

Waiting for rating change !

Finally!

One of the best rounds I have done, was freaked out initially after seeing Div2 A though!

Yeah me too :o

Same feeling :D

But ,problems was not so cool.....!!! 4 me As Beginer....!!! (:

http://codeforces.com/contest/689/submission/18931907 gives WA but http://codeforces.com/contest/689/submission/18936829 gives AC I can't understand the reason for it

you're missing one 0

what do you mean ?

I think you should have i <= 1000000

because when m=10^15, the answer is about 4.9 * 10^15.

but when i=10^5, i*i*i = 10^15 < 4.9*10^15

OK got it thanks :)

Good problems, thanks authors!

I want to give Mike a shit! after this test =__=

Hardest round ever.

¡Easiest and funniest round ever :P!

you just solved problem-B

I can't.

Can anyone help me explain this 18922000 solution? And how to develop ideas like this?

If you don't have any of digits 1,2,3, then any number you can "move up", so answer is NO. Same goes for left, down, and right. For example you can always "move down" if you don't use digits 7, 0, 9.

My submission: http://codeforces.com/contest/689/submission/18922407 (for some reason it's badly formatted in CF)

Thank you so much! :)

I thought the contest was rated

[...] will be better if it isn't so :D

The contest is rated

Aaaaand rating updated :D

And it was rated

people saying EID mubarak are getting too much downvotes.Guys they are people like us and celebrate festivals like us .If somebody would have said happy christmas he would have recieved like 1000 upvotes. seriously didnt expect the coding community to be so immature.

No, if 10 people had already said "Happy Christmas!" and more people still leave comments saying just that, then they would definitely

notget 1000 upvotes, they would be downvoted. Eid Mubarak is no different. It's just repetitive and adds nothing to the conversation.they mostly have only upvotes o_o

Nice round (although A was more difficult than expected) after being away for a while. Fast system testing and rating changes. Finally pretests weren't weak.

Pretests for A were REALLY weak. So many solutions were hacked :)

I agree that it was a nice round

Yes, for A I may be wrong, but not for C and D. Problem A doesn't have some non-obvious cases if you implement it straightforward.

n = 1 was a non-obvious case for A :P

No? It was an easy case not being different from the others.

Easy test case — Yes

Not different from others — No

wa-submission

ac-submission

PS — both submissions were after the contest

OK, I partially agree. It depends on the implementation (for example in my code there wasn't needed to be checked for that case: 18922236). But it's a good advice to always check your solution with a test with the minimum constraints and a test with the maximum constraints.

For my code it wasn't a special case

Guys, let me teach you how to write

`1000000000`

properly. It is`(int)1e9`

(works with`(long long)1e18`

too). I was tired counting zeroes while hacking.And thanks for the round, problems were good (maybe, A was hard for A and E was easy for E).

Since the font size are same, you can tear a piece of paper to make a ruler, or take screenshot and compare the length of them in software like mspaint.

Task A is probably too complicated for Div2-A, but it is a nice task for Div1 player (many ways to fail it). :P

For problem D I submitted a O(nlog^2n) solution and got TLE. I resubmitted the exact same code and got AC with 1716 ms. Is the Codeforces grader usually this inconsistent?

That should be impossible, because CF checks and says something like "You have submitted exactly the same code before."

I added an empty line that won't affect the code.

Why can't I see any submissions for problem-D in your submission history?

Maybe you forgot to click show unofficial.

Small Doubt:

In problem A, for testcase:

One solution can be

`4790`

. Please correct me if this is wrong. Thanks in advance.18957061Yep, it's your code answering YES while answer is NO.

How to solve C with dfs ?

I think that this solution for B should work for relative small n, why it got WA on 4 ? or i am wrong ?

Hi all. I'm getting WA in test case 17 of problem B(DIV2). But on that case tester solution and my solution are giving same answer (on my pc).

test case 17: 7.0e100

my ans(on CF): 7000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 my ans(on pc): 70000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 actual ans: 70000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Code: http://ideone.com/rSAuxb

I don't know why CF changing my output. Is there any problem with solution ? Any help will be appreciated. Thanks!

sorry a kid worte

Please fix the link to the editorial in the contest page, since it links to this post and not to the actual tutorial. Thanks for reading.

Editorial