Hello ladies and gentlemen.
I'm honored to announce you that Codeforces Round #366(or should I say, IOI 2016 opening CF contest) is gonna take place on August 7th and I'm the writer. Please note that the timing is unusual.
As usual, there are 5 problems in each division and duration is 2 hours.
I want to thank LiTi for testing this round, GlebsHP for helping me prepare it and MikeMirzayanov for legendary and unique platforms of Polygon and CF.
The main characters of this round are The Avengers!
I wish you all Accepted solutions and Successful hacks.
Scoring will be posted soon.
Problems are sorted by their expected difficulty, but I strictly recommend you to read all the problems.
GL & HF!
P.S: Top IOI participant in each division (only with handle present in this list) will be rewarded with Persian souvenirs in Kazan.
UPD: Totally unrelated, but since the previous IOI group in telegram no longer exists, here's a new group!
UPD: Scoring is 500 — 1250 — 1250 — 2000 — 2500 in Div.1 and 500 — 1000 — 1500 — 2250 — 2250 in Div.2
UPD: I'm really sorry about the difficulty. System test is about to begin.
UPD: Editorial is out.
UPD: System test is over, congratulations to the winners.
Div.1 winners are:
Div.2 winners are:
Souvenir winners are lawrenceli from team USA and eXeP from team Finland (If that's not true write me in private).
kiram to maghzet
kiram to kasi ke manfi bede... kalle kiria manfi midin vase chi
namosn mellat nmifhmn chi migi mosbat midn :D
به تخم چپم که نمیفهمن کصکشا
bashe fahmidim toam az in chiza baladi hala gooreto gom kon inja jaye in harfa nist.
A contest for IOIers, prepared by an IOIer.
Just how freaking amazing PrinceOfPersia is.
Top IOI participant in each division will be rewarded with Persian souvenirs in Kazan.
This remind me of the reflection of zhj who participate in IOI 2015 as China team's member.
He said a iran team member gave lyy 300 IRR as souvenir and as return, lyy gave him back 10 RMB. After that they checked the exchange rate...
(300 IRR = 0.0664 RMB)
(No offense, just saying. I look foward to seeing cool souvenir from iran team too!!)
I really don't think that the value of the currency matters because it's a souvenir and I seriously doubt they would want to spend that money anyway.
Yea I think so. It is just funny that they didn't get along with the exchange rate and didn't know how much to give as return as proper. And giving a relatively large amount of money.
Last year I didn't prepare any souvenir and in the last moment I heard from my brother that in IMO people exchanged their own currencies, so I picked up moneys which I got from my grandpa, those were for 30 years ago and had absolutely no value in cash! However they are really rare and antique somehow :-D I'm sorry for the inconvenience I caused.
By the way, this year is different and you can expect many cool stuff :)
wow! Then I think it totally worth it. Sorry for the misunderstandings.
"relatively large amount of money." XDDD
Are we seriously creating a discussion which looks like accusing somebody of being a dirty defrauder because of <1,5 USD?
lol I don't know how can you read my word as accusing somebody as a defrauder. How can you defraud someone by giving someone money first.
I just think nobody would give 10RMB as souvenir as normal. 10RMB is a banknote(normally people would give penny as souvenir). Also 1, 5RMB is also banknote so I think giving 10RMB is abnormal.
I apologize if my wordings are shown as offensive as English is not my mother language. I have no intention to say anyone as a defrauder.
I agree 10RMB is not much money but I can eat many food and have breakfast using just 10RMB. I would be doubted before I give someone 10RMB as souvenir if the amount of money means nothing and can give other as alternative and the meaning is still the same. That's why I used the word relatively. Or maybe I'm just poor or stingy.
300 IRR :|
Надеюсь что этот раунд не будет как #365.
Размечтался...
Are you really confident of using "the Avengers" character? :D
I don't think I get the references. Can someone enlighten me, please?
It's Mickey Mouse and Minnie Mouse in front of Kazan Kremlin (IOI 2016 is gonna be held in Kazan).
Nope, the castle is just located in Disneyland.
Avengers related contest after Suicide Squad premiere? :D
А почему в рассылке PrinceOfPersia красный?
Why is it unrated?
The writer never said that it was unrated.
It is rated, and I will become purple JIBANCANYANG. that is great, okay gays come on!
You would better change "gays" to "guys" because of their meanings! :D
Is it funny to say the same thing again and again :|
wrong place
Forgive me gyus, I mistaken this word as unrated.
UPD: Totally unrelated, but since the previous IOI group in telegram no longer exists, here's a new group!
BTW, there are some teams (like team Kazakhstan) who weren't on my list but are now here. Wouldn't taking handles from that list be a better idea?
UPD: he changed it
You rewarded with 3rd place in the last contest :P :D
anyway good luck bro ^^
Go back to my blue xiaoai. Fighting!
Is it rated?
Sure！
Why do people ask this question so many times? Usually the rounds are rated and in the case it ends up being unrated (last contest), it's usually made pretty clear (almost always in bold).
Do people just want negative contribution?
I think in this contest people have read Totally unrelated as Totally unrated it happened to me.
but in other contests I don't know why maybe it's one of codeforces traditions.
I used to be voted down because of this question. From that, I always find the information in mail! =)) My contribution is negative. You should find by yourself before asking anything.
Why negatives??
We should know this after the last contest became unrated...
salam
manam mikham emtahan konam babinam mosbat midan?
do most words in your language ends with "en" or "em" ?
Good luck guys! Wish you success!
"Top IOI participant in each division will be rewarded with Persian souvenirs"
Should I expect no-math problems ?
I hope everyone will be better!
I hope this round quickly judged. Better rating!
Well, this turned out to be a case of being careful what you wish for.
(As in, systest will be over very quickly)
Iranian contest always contains full of expected value problems... ~.~
really???
Do you know BWC?
I wish high rating for everyone :D
I wish me higher rating than everyone :D
I wish everyone higher rating than you :D
Good Luck Everyone!!!
and may be you are Mr Everyone, right? Nice to meet you! ;)
It would be fun with Avengers :D. Moreover so many hacks I guess. GL all :)
Is this contest rated or unrated?
Rated
What is the major idea in lots of amd's problems? — Math and Probability I guess
In Iran's INOI math , graph theory & combinatorics is very important & also PrinceOfPersia is a INOI gold medalist!
I hope to be a pupile in this round , I hate my gray color XD XD motivate me please XD
why my brother ?
hey 10 mins delay please :(( I'm coming...
amd problems that I solved in practice are very test case-y.
Ignore this comment.
These problems are for Div 0.
Hello. I returned after 5 day trip without internet and occasionally found that #366 is running. I could participate during 1h 20min which remain, but why registration is closed, reason?
You know the contest is hard when there are only 27 people in Div 1 who solved B and only one person to solve C when the contest is 80 minutes in....
I think that today no avenger cannot solve all the problems at the time of the contest. Because it is very difficult tasks. ('_')
Fill like "Hawkeye" — so useless.
OK
Jesus Christ...
Никто не решил Е, 1 человек на данный момент отослал D, что-то не так во 2 дивизионе...
Причем я отослал жадный алгоритм, и он прошел претесты. Точно что-то не так.
The Avengers take a revenge with their hard problems!!
Nothing to to do when there was 1 hour left... Most difficult round I have participated in.
Hardest contest ever. How to solve Div1B? I tried O(n^2) DP but failed...
How did you mask the x positions if you applied dp?
Can you explain your idea?
Thanks for this round. But I still want to say, I feel very terrible now.
After contest ends can somebody explain how they solved Div1 B (Div2 D)?
The solution is trivial if O(n3) dynamic programming algorithm passes 4 seconds limit.
I will wait till the submission is allowed and test my solution.
Obviously it doesn't pass
Isn't it impossible for O(n^3) to pass in 4s?
Did the author prepare interesting problems? — Yes, he actually did!
Did the author prepare interesting contest? — No, absolutely no!
Even in div2 A and B were very very easy, and C was a little long to code.
May have gone away 1 hour and 53 minutes before the end :|
Anybody else thought that in A the first t notifications are the first t in the stack of notifications like any social app? :D
Really I WA many times on that..
Wasted 2 WAs because of that :(
Oh, so it wasn't translator's fault!
6 WAs because of that :c
I hope Codeforces can balance the difficulty next time……
So many people overflowed on 2B, but apparently overflowing is completely irrelevant when just determining whether an integer is odd or even. Sadness.
My hack for Div2B was
2
2 1
Can somebody explain why this happens? , Me too, I had a lot of overflowing solutions in my room and I couldn't find a case to hack them.
If it is int, then overflowing goes modulo 231. We only need the parity of the sum. Parity doesn't change modulo 231, so overflowing is not a problem at all.
UPD: If we check whether the sum is equal to zero mod 2 — we can't hack anything. But if we check whether it is not equal to 1 mod 2 — overflowing works I believe.
No
if somebody used
if(s%2==1) print 2 else print 1then we can hack by3
1000000000
1000000000
1000000000
But everyone in my room checked using s%2==0.
Yes, since that was the only hackable solution, I too checked all the solutions. Lots of if(s%2), if(s&1), and if(s%2==0), but not one if(s%2==1). Guess there's no justice in this world.
why is (s_int & 1) always equivalent to (s_LongLong & 1) in overflow?
You can just think it as if the first bit in int represents -2^32, so it doesn't affect the % operation nor the & operation.
Well, technically it does affect % operation, as dush1729 said.
What is test case 3 in div 2 C?
code can anyone see my mistake? please tell me
n<=q? I fix that then getting AC
I'm thinking maybe I misunderstood the problem statement, because my code is behaving as intended on the failed test case!!
Oh no, I just finished B :(
What was everyone hacking on A?
UPD: Seems like my B is too slow.
Damn -O2 optimization ;(
I got 2 unsuccesful hacking attempts because the optimization fixes the O(N) while loop
Good to learn that the compiler optimizer does that for next time :)
I wonder if they actually knew the optimization would work or just wrote inneficient code and got lucky ...
I have read about it many times(in CF blogs) but I thought 10^14 operations will give TLE even with -O2 optimization. I guess it's best not to hack Div2A for TLE.
Подскажите пожалуйста, как код в задаче В: int n; while (n--) { cin >> a; while (a > 1) { a--; } ЗАХОДИТ при максимальном тесте?
-O2 творит чудеса
Надо весь код смотреть.
В таком виде оно изи оптимизирует внутренний цикл
https://godbolt.org/g/X8MwmK
I like long statements but this time statements in div1-A and div1-B were so misleading. Reading the same notifications and jumping to the left only when one is small — at least strange.
An approach for "Kangaroo" problem from CEOI few weeks ago gives a solution for 704B - Ant Man immediately.
But kudos for providing hard problems.
Could you give a link to statements and analysis? Thanks.
According to Xellos's comment, their online judge is down.
The problem statement was:
You are given three integers s, e, N (1 ≤ s ≤ e ≤ N ≤ 2000). Find modulo 109 + 7 the number of paths from s to e that:
3 -> 7 -> 9).The solution is described by muratt's comment — in short go from left to right and keep
dp[i][the number of times you move above i].My solution today: 19697314.
Thank you. Really not obvious, that we can do this, it's the NP-problem in common case (I thought that we can create a test where |xi - xj| doens't take part much in the answer).
I've read your solution and the muratt's comment and still cannot comprehend the solution.
Could you, please, elaborate a bit more on the method you used?
Imagine an optimal path. For every position i imagine a vertical line cutting the path j times. The idea is to calculate dp[i][j] — the minimum cost of arranging parts of the path on the left (before i) so that it would go exactly j times through a vertical line over index i. In my implementation j is the number of times the path goes from left to right. So, it must go from right to left j or j + 1 times (the latter if we are between s and e).
Is there any proof why this gives optimal solution? Why this can't be applied to generic graphs to solve TSP problem? Is your solution the same as in editorial or it uses diferent idea? If different, do you understand how is it solved in editorial?
As in any dynamic programming — we consider all possible paths so yeah, we must find an optimal solution. A solution in editorial is slightly more complicated but the idea is the same. Two dimensions of my dp are (I think) the same as two first dimensions of dp in the intended solution. I handle s and e a bit better.
Was Dinic intended in D?
Yes
Then why are the constraints so high? I spent about 20 minutes, trying to come up with a faster solution, but in the end I just convinced myself, that it can't be done faster. Do you have any proof, why it works fast? The graph is bipartite, but the capacities are not unit, so I don't think that it works in
.
It works in
according to Karzanov's theorems.
In my solution I also need a binary search around Dinic so it'll be O(E1.5·logN). Does the intended solution do the binary search as well or it's just me?
It's just you, though I understand where this log comes from :)
I see, thanks! In this case I can't wait to read editorial to see how to avoid that binary search :)
It's not something magically invented to that problem, that is just what needs to be done in typical LR flow, however I admit it is a bit tricky and I also had binary search on my mind for some time. In my implementation I firstly compute flow from s' and t' to find a saturating flow and then compute max flow from s to t on the residual network resulting from previous flow (notation as here: http://web.engr.illinois.edu/~jeffe/teaching/algorithms/2009/notes/18-maxflowext.pdf)
Ah, right, instead of minimization we can try to maximize the flow here. In my solution I was always thinking in terms of minimization of the number of blue points (if r > b, then swap blue and red) and that's why I needed a binary search. But in this problem we can instead maximize the number of red points and thus we can solve it without binary search. Thanks!
On the other hand, system testing will be shorter than usual:)
Oh! :D
So, how to cancel an upvote?
Very tough problems — thanks amd for the contest!
The problems were interesting, that's for sure, and I'm eager to find out how B and C are solved, however, the contest itself was very unbalanced. There were too many contestants who were simply stuck after solving problem A. Ideally, the difference in difficulty for every two "adjacent" problems should not be so large.
I think that these problems are difficult to understand
Div2.D/Div1.B has pretty strange storyline...
Yeah, and it makes no sense.
any help for DIV 2B.. I suffered there -_-
Just sum all arr[i] — 1, and check parity of the sum. If it's even, print 2, if it's odd, print 1.
I thought that.. Is there any proof..??
Kynit explained it well, the comment under me.
Yeah! A chain of size C will always take C-1 moves before it is reduced to chains of size 1. It doesn't matter what moves the players make — the total number of moves will always be the same. That means you can update the winner just by checking if the new chain has an even or odd length.
No matter the way they play, they winner will be determined by the number of turns the game takes to end. So, is just a parity check!
http://mirror.codeforces.com/contest/705/submission/19709431 Some one please tell test case 3 ?? Why is my code wrong ?
The way you handle the third operation is incorrect. Your code considers whether there are still unread messages for application X if I understood it correctly.
I think test case like below will break your code
In the 4th command x[1]>0 but its position is 2. So you should not remove it.
I received a compilation error with the following message:
"Can't compile file:
cc1plus.exe: out of memory allocating 5584 bytes"
What happened? (I submitted the same code after it and the verdict was another one)
Sorry, it happens sometimes because of some memory lacks. I'm finding the way to fix it.
In Div2D/Div1B is simple Dijkstra-like approach incorrect? If it is(I guess it is after those results) — why?
Because with Dijkstra, how will you guarantee that you've visited every vertex exactly once in your optimal path?
Missed that sentence, thanks :) Good thing I couldn't participate
I thought that too!
How you will check that the answer found by Dijkstra passes through all vertices?
I solved it with dp
Man I busted real hard after Div 2 A lol. Can anyone explain the logic behind why B was so simple? And I screwed up too many times on C.
Check out ghazanfar_iiuc's question above!
Ah! That actually makes a lot of sense lol. Dang that was pretty simple I guess. Thanks for the help!
Generally it is easy to see that if you generate winners for first 10 values or something else...
It is classical Grundy theoreme and you can see that for even numbers grundy value is equal to 1 and of odd it is equal to 0. After that in case total xor (it is same as amount of even numbers % 2) = 0 winner is second otherwise winner is first.
P.S. You don't need Grundy, it is just checking parity with finding optimal strategy. Anyway I thought as above on the contest.
Hmm interesting. I'll take a look at the Grundy theorem sometime soon then. Thanks for the help!
biggest integer number is odd and after overflow we have even negative number.
it is correct for B (if you use int instate of long long int) ||(have overflow).
Whether someone else got TLE on d2 third with using set ?
I can not understand why that solutions gives TLE and some other solutions with Seg. Tree are correct.
My TLE code
I got TLE on 52nd case. I used mapping to vector
Dont know about your solution, but I also used set in Div2C and it got AC.19701130
It should be u = max(u, x + 1) instead of u = x + 1.
I was cheated by the javascript timer in my computer. When I was going to submit Div1C (2 minutes remaining), bump... The contest is over, :( !@#%. **** I hope my solution is bad, otherwise !@#%.
It is the first time I get an AC and I felt so sad :( 19734900
Didn't registered for the contest and came 45minutes late, looked at the standings and thought WTF 45 minutes in no Div2 participants solved Antman.
It only took me 15minutes to understand all other participants' feelings.
I wonder how the Div2D question is solved, it's pretty hard to take delta x into consideration.
By the way, queues are very evil, vectors are much more kind.
12MB vs. 260MB... why? Can someone explain?
Yep, this doesn't look right; I used queues.
This is known problem, deque allocates way too much memory to store elements in it. Queue is using deque as a container for values by default.
As a chinese netizen, I devoted myself to the great Chinese network. When there are 10 seconds to the end, I submitted a solution of B(I think it is correct because I stress tested it). And then when I refreshed the page, it says the solution wasn't submitted. If the contest was 5 seconds longer I could have made it submitted. :(
+1s!
+1s!
understanding the description is harder than solving the problems
I think the contest is not div1 but div0...... It's too hard!!!
May it unrated?
No way.
And it shouldn't be turned into unrated: the problems were hard, but that's all. It should only be turned unrated if it's unfair, and it was completely fair.
http://mirror.codeforces.com/contest/547/problem/D -> http://mirror.codeforces.com/contest/704/problem/D (with solution fitting to both problems here: http://mirror.codeforces.com/blog/entry/18126?#comment-230210)
...
Hoho, stealing comments on CF, I haven't seen that one on CF :D.
Maybe he didn't know how to share the link to your comment!
wish you all high rating:D
How to solve DIV 2-C
Deques: deque<pair<int, int> > q — store all added notifications, deque a[N] — added notifications for each app.
Something like this :)
Could you explain this ?
Sure, firstly, we just add notifications one by one to deques (q — all notifications, a[x[i]] — notifications of the x[i]-th application). Add means push cnt value to deques, cnt — number of current notification, in other words, the number of queries of the first type. So we could notice, that all numbers in each deque will be sorted. We want to store there only non-readen notifications.
Secondly, ans — number of non-readen notifications, for 1 type: just increase by one ans, for 2 type: we decrease ans by a[x[i]].size(), because we read all non-readen notification, for 3 type: a little bit more complex.
Thirdly, 3 type, we need to remove all notification from common deque, that have number less than x[i], but we should descrease answer only this number presents in the app deque. So, all deques are sorted, we have pair<int, int> on top of the q (which means: first — number of notification, second — number of application), then we need to remove this notification from application. So we do this like for two-pointers problem.
In conclusion, we add and remove one notification from deques one time, so complexity is O(n + q).
Probably, the most interesting part is
msgstructure:All the messages of app i in the message_queue before index
apps[i].queue_indexare read by Thor. When comes the query of the seconds type, we change that value:apps[i].queue_index = queue_end.Not Happy....Problem set.
It looks like in order to perform well in PrinceOfPersia's contests it is profittable to get well acquainted with his previous contests :D.
http://mirror.codeforces.com/contest/547/problem/D -> http://mirror.codeforces.com/contest/704/problem/D (with solution fitting to both problems here: http://mirror.codeforces.com/blog/entry/18126?#comment-230210)
http://mirror.codeforces.com/contest/536/problem/E -> http://mirror.codeforces.com/contest/696/problem/E (those are not that similar, but HLD is a rarely used method)
Is any solution for Div1-C with simple implementation?
I solved this problem but i could n't implement cause it was so long!
Sorry, wanted to answer the comment above.
He asked for Div1-C not Div2-C...
How to solve DIV 2-D........n^2 -DP ? Maybe?
I solved it just by adding chairs one by one. Just insert them in the optimal place in current path. So you are right, it is something kind of DP.
orz! rank1!
I don't really understand why this solution can solve this problem. Could you please explain it to me or give me some proof about the correctness ^_^.
p.s I think this solution is kind of a greedy solution.
How do we know that this greedy solution works?
v
I don't quite understand your code... But it seems that you are considering cycle by cycle, since you are setting x and y to 0 whenever a new cycle is added.
You would better make this contest unrated -_-
I'm surprised E does not have any submission in Div2 and D does! E was definitely felt easier D.
I got TLE on third with O(n) solution. This becomes funny :D
Same idea and same TLE well dunno why it doesn't work
Me too, TLE with O(2*N)... :/
It seems that many people are getting TLE43 on Div2C with the O(n) solution where you take a vector and then keep track of the most recent deleted location.
i used the same idea as yours ... but i am not able to figure out why it is failing in pretest 4 ... my code http://mirror.codeforces.com/contest/705/my#
edit : ok a silly mistake ... i changed index = no +1 to index = max(index,no+1) and it got accepted .
u = x + 1 is causing troubles when x + 1 < u. Rather make it u = max(u, x + 1). Queries like 3 100000 -> 3 1 -> 3 100000 -> ... will break your solution...
Well that was a simple mistake haha thanks for your help ! It won't happen next time for sure
I not to miss that case, nice hack :P
In last time with this queries, I am always think that queries are sorted. My bad!
Could somebody tell me what's the type of the problem C of div 2? I Had a really hard time solving it,and I wonder if I want to solve a problem like C of div 2 in this contest next time,what should I learn? Is there some problems like this or some tutorial I can refer to?
Does anyone have an idea, what might be the purpose of the function
lucky_test()in 19691627 ?adrenaline
considering there's no srand, I'm not sure it's for adrenaline.
I am sorry, but I still did not understand the purpose of lucky_test().
To generate random input for the program and test your implementation. You can implement 2 solutions: bruteforce and clever one. Then use
lucky_test()to compare results:bruteforce(a, b) == clever_solution(a, b).I read once again the usage of the function... well, probably it is really for adrenaline :)
Comparing your bruteforce() and clever_solution() has nothing to do with this lucky() function...
System testing is slow as hell
Thanks for tough but interesting problems, PrinceOfPersia! And for lightning-fast editorial!
congo u were great during contest
Thanks for the early Editorial! I hope this continues in future contests .
Heck! :\ Used set instead of queue in DIV2C. Thought it won't affect much. But here i am with TLE on 43rd case. :'( Hurts!
I used set and it worked. Your solution handles incorrectly the third query. You should change "last = t" to "last = max(last,t)" or something like that!
Woh! Crap! I was initially using a separate 'if' to handle cases greater than 'last'. Later, I wrongly assumed that loop condition was taking care of everything automatically and removed the 'if'. Didn't notice that 'last=t' wasn't handled by 'for' loop condition. Thanks for pointing that out, I really appreciate that.
http://www.codeforces.com/contest/704/submission/19712670 segment tree with lazy update solution :D if segment tree can work set should definitely work
Why my submission for problem 705a is wrong at tests 11 19688500
I have resubmitted your code again and ... it's AC!!!
So Avengers have won the match :P
What is the greedy solution for Div2D/Div1B?
First add to the current path two chairs: s and e. Then, go through all other chairs and add them one by one to the path. For each chair, find the best position in current path where it should be placed. The best position is the one for which the total time for new path will be minimal.
I literally have no idea why this works, but so far we were unable to find countertest.
Me too. But I believe there is a proof.
I was considering this solution but didn't wrote it cos I couldn't it. Still not convinced it's correct :d
Seriously? How does this work...?
It seems like, it can be proved (or disproved ;) ) by induction.
For n = 3, it is valid to insert new vertex v1 in the middle: ( s, v1, e).
For n = 4, after we've inserted v1, we can only choose between 2 configurations: ( s, v2, v1, e) and ( s, v1, v2, e).
Let's say the configuration ( s, v2, v1, e) is better than ( s, v1, v2, e). Now consider the fifth vertex v3. We have two choices:
1. Try adding v3 to the winning configuration.
2. Try adding v3 to the loser configuration.
Then we get two sets of possible configurations:
, v2, v1, e), C2 = ( s, v2, 
, v1, e), C3 = ( s, v2, v1, 
, e)
, v1, v2, e), D2 = ( s, v1, 
, v2, e), D3 = ( s, v1, v2, 
, e)
After adding v3 to the winning configuration:
1. C1 = ( s,
After adding v3 to the loser configuration:
2. D1 = ( s,
Now compare the pairs of configurations: (C1, D1), (C2, D2), (C3, D3). If configurations Ci always give better result than Di, then induction worked and solution is correct. Otherwise, we can construct a counterexample to that greedy solution.
Start with pair (C1, D1): C1 = ( s,
, v2, v1, e) and D1 = ( s, 
, v1, v2, e).
, v2) is significantly bigger than T(
, v1).
) + T(
, v1) and T(v1, 
) + T(
, v2).
) and T(v2, 
).
The configuration D1 is better than C1 only if the time of the jump T(
For pair (C2, D2) we need to compare T(v2,
And for the pair (C3, D3) we need to compare T(v1,
If you know how to proceed with the proof, please write the comment.
But how do you take delta x into consideration? It changes position by position so you can't only consider the best pair of a[]d[] or b[]c[] right?
I believe this case:
Fits the property that ( s, v2, v1, e) is better than ( s, v1, v2, e), but it also has
So the greedy still holds (as 125<130), but each comparison C_i<D_i is not true.
Ok. It means that in order to disprove the algorithm we have to find an input with the property that minimum time in the winning configuration is worse than the minimum time in the loser configuration:
min{T(C1), T(C2), T(C3)} > min{T(D1), T(D2), T(D3)}.
I think, at first it would be easier to find the case when mini{Ci} = minj{Dj} and then tweak it to find counterexample or some restriction will show up which we will use to prove the general induction step.
I tried generating random sample cases and the greedy still passes. I did observe two trends, one of which I know how to prove:
Consider this example
Consider each edge that's not drawn as very big integer. The greedy approach will build path s->e, then s->1->e, then s->2->1->e, then s->3->2->1->e. The weight of s->3->2->1->e is 2+2+2+2, but the weight of s->3->1->2->e is 2+1+2+2 which is less.
If I'm not mistaking this should be a counterexample. What do you think?
Ah, except this graph is not possible, as the cost from 1 to 3 can't be one. T(3,1)>T(3,2)=2 because of the ordering of x_i. That's why when you do the greedy out of order you get WA, but when you process them in order it works.
Here's a proof that the greedy works for a special case of n=5.
First, denote X(a1,a2,a3,a4,a5) as the total time of the past (a1,a2,a3,a4,a5).
The approach is to consider an optimal length 5. We want to show that when you remove v5, you have an optimal path length 4.
The special case is that: s=v1,e=v2, and (v1,v3,v4,v5,v2) is optimal.
Thus, since it is optimal X(v1,v3,v4,v5,v2)<=X(v1,v4,v5,v3,v2). Writing out each T, you obtain:
(x3-x1+d1+a3)+(x4-x3+d3+a4)+(x5-x4+d4+a5)+(x5-x2+c5+b2) <= (x4-x1+d1+a4)+(x5-x4+d4+a5)+(x5-x3+c5+b3)+(x3-x2+c3+b2).
Which reduces to a3+d3 <= b3+c3. However this is exactly the statement that X(v1,v3,v4,v2)<=X(v1,v4,v3,v2), if you cancel variables on both sides.
I see your point. Seems like the ordering makes a lot of problems.. I considered the problems is equivalent for the problem for random graph (positive integer weights) but actually it isn't T_T
I don't agree T(3,1)>T(3,2) because the a, b, c and d values can be set such that this is incorrect. (but still you convinced me that the whole graph couldn't be random). Seems like I should spend more time on proving / disproving.
This special case of n=5 is too specific. Do the same arguments hold for other (all) cases of n=5?
Yes I made a mistake, T(3,1) is not necessarily greater than T(3,2), but there is an ordering property. My specific example isn't terribly helpful, but it does motivate the idea of trying to compare path permutations to reduce to the result of the smaller inequality.
Thus I wrote a program to do this. It uses the same method that Pixar started. However, as I mentioned earlier, it is not true that C_i<=D_i for each i. But if you rearrange the D_i, depending on what s and e are, you can get C<=D. Here are my results and the source code:
I can explain what the output means for one example, s=1,e=2.
The five by five grids are the coefficients of a1,a2,a3,a4,a5,b1,b2,b3,b4,b5 etc. in each inequality (when it's all reduced and moved to the right). E.g. 1 3 5 4 2 vs 1 5 4 3 2
means X(1,3,5,4,2)<=X(1,5,4,3,2) which is equivalent to 0<=-a2+b2+c2-d2, which is the known inequality at the top.
At the very top is the inequality X(s,v3,v4,e)<=X(s,v4,v3,e). (If the opposite is true, all the signs below can be flipped.)
Thus this shows that C_1<=D_3 (they're equal actually), C_2<=D_1 (as this reduces to the starting inequality for a path of length 4), and C_3<=D2 (similarly).
Some observations that may be able to generalize:
There always equals i and j so that X(C_i)=X(D_j).
I believe the comparison is always a shift of D, i.e. the solution is either (C_1,C_2,C_3)<=(D_1,D_2,D_3),(D_2,D_3,D_1), or (D_3,D_1,D_2)
EDIT: After more carefully reviewing my results I observed that this second observation is not true.
Source code: http://pastebin.com/m4YPJK7t
Output: http://pastebin.com/W1kC7SeB
what do you call this!? :O
that time.....
I guess you call this a fail.
fail? korla.march is 1st bro. and his D accepted just 7s before finish!
It only shows "Hotlink is not allowed" on my side.
Now waiting for contest with DC heroes :)
CHEAT:
user "Deemo" cheated in #366. he used fakes to see if both of his solutions were right or not. and after that he submit them with his own account. Trust me. I know him and his evil plans.
Well I guess he didn't solve A fast and waited to see if he can solve B or not (and if yes submit A after that)
Auto comment: topic has been updated by PrinceOfPersia (previous revision, new revision, compare).
Compare 19711616 and 19711892, first one in java second c++.
Please could someone explain, why this 19701013 solution got AC? İt's complexity is O(n*max(ai)).
Maybe optimized by compiler
Thanks for interesting problems and kind of boring round )
This is the only contest announcement I have seen that has negative contrib :O
My oh my!
And you got positive contribution by writing about negative contribution :)
Анонсировать раунд только на английском — это свинство. Ставлю минус.
It is not good at all to announce a round only in English. Minus.
Could anyone explain why this solution got TL? (Problem C(div2) / A(div 1))
I found the reason
Guys, come on, I don't understand amount of downvotes. Tasks were nice, there were no major issues with them. Nothing bad in having challenging tasks. When did solving only those problems we are able to become hotter than facing challenges :)?
this amount of downvots are bother me more than they bother PrinceOfPersia
the tasks were superb , they were very tricky and difficult
now this is the last contest for PrinceOfPersia , here
thank you a lot AMD I will miss your contests
I don't know about you, but I feel that this was one of the best contests I have ever taken part in. It was obviously much harder than a regular CF round, but the problems felt so unique and original, and the solutions were beautiful (and not that hard to comprehend, to my pleasant surprise). Great round!
Did you comprehend the solution to the ant man problem?
here I explained my solution , hope it will help you
I agree with you...
Sorry ,I want to know where is Tutorial.
http://mirror.codeforces.com/blog/entry/46450
Thanks