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.cse12 Musa
batpari
Mohammad Abdullah jackal_1586 Matin 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.
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
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 n is 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
Contest just before Eid. It'll be interesting! Eid Mubarak everyone.
Eid Mubarak.
Those who have summer vacation, Happy summer vacation and Eid Mubarak to everyone wish you a happy, prosperous and AC life ;)
Good luck Guys
Hoping to see some good problems and ratings up. All the best to all.
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.me/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 * log2(n)) time complexity. But it gets AC with 1419ms time. I used segment tree with binary search for all i (1 < = i < = n). Here is my submission. BTW I recommend RMQ solution with 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 Maximum value. Didn't read the problem statement well. If they can tell the Maximum value 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 maxa will increase or remain same and minb will decrease or remain same. Now there can be 3 type of cases.
1. maxa = minb
2. maxa > minb
3. maxa < minb
For second case we have to go to the right side because we want maxa to be equal to minb. 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 * 1015 since M is at most 1015.
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
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
Помогите доказать решение по Д: я перебираю левую границу слева направо(пусть i) и для нее поддерживаю l и r такие, что минимумы и максимумы равны на соответствующих отрезках от i до [l; r]. Почему верно, что l и r не нужно двигать влево никогда? Если что, решение с двумя бин поисками я тоже придумал и понимаю, почему оно работает.
min a[i..l - 1] > max b[i..l - 1] => min a[i + 1..l - x] > max b[i + 1..l - x]потому что min на подотрезке больше min на отрезкеаналогично для r
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.me/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.me/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.me/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;afterif (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.
Решение C, отправленное после дорешивания, не проходит таймлимит: http://codeforces.me/contest/689/submission/18935878 Если запустить локально на том же тесте
Почему 0.2 секунды могло превратиться на сервере в 2 секунды?
у тебя все равно упадет решение, правая граница должна быть больше 10^15
Сейчас протестировал в запуске — получилось чуть больше четырёх секунд. Так что всё верно.
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
http://codeforces.me/contest/689/submission/18931907 gives WA but http://codeforces.me/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!
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.me/contest/689/submission/18922407 (for some reason it's badly formatted in CF)
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 not get 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
1000000000properly. It is(int)1e9(works with(long long)1e18too). 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.
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.