Разбор задач
Всем привет!
Codeforces Round 467 (Div. 1) и Codeforces Round 467 (Div. 2) пройдут в воскресенье 25 февраля в 17:35 по московскому времени. Раунды основаны на задачах Олимпиады Университета Иннополис для школьников по информатике, но совпадают с ней не полностью. Просим участников олимпиады воздержаться от участия в раундах и обсуждения задач до конца раунда.
Задачи подготовили: niyaznigmatul, pashka, vintage_Vlad_Makeev, VArtem, burakov28, budalnik, YakutovDmitriy, dusja.ds, GreenGrape, tourist. За прорешивание и вычитывание спасибо demon1999, craborac, the_art_of_war, qrort, .31, izban и julsa.
Удачи!
UPD: Раунд пришлось подвинуть на 1.5 часа вперед, чтобы избежать пересечения с квалификационным этапом VK Cup 2018.
Hope the problem statements are as short as the announcement!! :D
There are some users who regestered in div.2 round before the rating change of round 466 and now they are div.1
did they ever fix the one where the educational round let div1 participate in div2
It wasn't a bug to be fixed. It was totally intentional.
So it's intentional that a purple user can farm rating in contest strictly for < 1900? Where did they ever say that's intentional?
The results of educational round was announced after div 2 contest so it was made rated for everyone who were div 2 before the educational round. Participants want to know whether it's rated or not before they participate in contest. The only fair way to ensure this was to make it rated for everyone who were div 2 before educational round. As you say you can't simply "farm" rating. I actually dropped from div 1 back to div 2 after that contest. Whoever had rating increase totally deserved it.
official comment (http://mirror.codeforces.com/blog/entry/57819?#comment-414872)
looks like I was wrong, my bad
Anyone in particular you have in mind? I only see a handful of >1900 people in the div2 results and it doesn't look like the competition counted towards their rating.
Почему бы не сделать раунд во время олимпиады?
Тогда и возможность нечестного участия тех, кто уже видел задачи, была бы исключена.
This round will be held in usual time. It's good for someone.
It's the first time ever I've seen a contest with 10 distinct writers :O
Let's hope for a quality contest with no interference from DDoS and server issues ;)
Round# 467 is a prime number while contest(div. 2) 937 is a prime number, too!
Problem A:
What's happened to you people :|
I have found the name tourist in the problem setter section :D
10 problem setters , sir tourist is also here , i think this contest problems are too much perfect and malleable , too much excited :)
Hopefully the number of problems is less than 10 considering there are 10 problem setters xD
My brain singing "I want something just like this" :p
How many problems are expected? There are many setters
So is contest starting at 16:05 UTC now?
Edit: I realised later I can see the time in Contests tab.
Hope a round whose time is good for East Asia users!!!
Please make this round visible in a "Pay attention" section (can't see it in RU version) and include it into the list of upcoming events! I found this round only accidentally.
tourist as setter in Contest #2 of 2018 (Contest #1 — Hello 2018).
It is not good to change the timings at the last moment as all my plans are getting disturbed.
labib attacked by chikunguniya :D please pray for him ;)
:D
So sad it delayed.It is 12:05 UTC+8 now :( I know I'm not that good at programing,but I just want to join in the contest for fun... (Unhappy Chinese pupil)
BTW,will my comment be hidden because too negative feedback?
I'm sad, too. ;( And about your comment, it won't.
The comment is hidden because of too negative feedback, click here to view it
中国迎来了帝制，我无比的伤心。
Why the delay...? I want to know what those "other events" are?
so what about score distribution?
Got up early on a Sunday morning for a contest and found it delayed like.
I can't participate in this contest because it delayed. But I have registered. So the question is: will my rating be influenced if I don't participate. If yes, what should I do?
No. If you do not submit any code, your rating will not change. And you can also unregister your registeration.
Unregister.
find yourself in the (http://mirror.codeforces.com/contestRegistrants/937),and press the "X" after it.
I know how to do now. Thanks!
An Chtholly lover! WOW!
А что, вчера не было известно, что с квалификацией пересечется?
UPD Письма тоже не было. Очень некрасиво так делать, пишите тогда прямо причину — думали, что можно два контеста одновременно проводить, оказалось — нельзя.
I know the event today.
it's VK Cup 2018,not tourist's marriage.:-)
But in the Contests page, it shows that VK Cup 2018 is on Mar 10th?
switch to russian version dude
thanks, I get it now.
Although I was very busy at work but came home earlier for the round, and see that the scheduled time is changed. For next rounds, I suggest to change date or time at least a day before the round.
Events like Chelsea VS Manchester United :)
original time would have been better, I would have been able to watch Man City vs Arsenal! much better than chelsea vs united
Mike is a Chelsea or ManU fan :V
Haha!!
I'm too worried about codeforces server errors during the contest. Let's that it'll not happen again.
please post the new score distribution.
Hate the time delaying. The new time conflict with my sleeping time
I hope this contest will make me green !.. I just need +75 rating to become a green coder...
yeah, Against all odds, finally you got your prize ! :)
Yess...I became a green coder now...!!!
Yes..
Исправьте
Hopefully it will be a cool contest.
I hope, systesting of VK cup will be turn off during the round.
UPD: So you haven't done this...
I think all of you guys should stop arguing. Codeforces is a programming website, not a quarrelling website!
finally we got rid of ppppppppppppppp
Came here to read funny comments but man wtf?!
to CF Server : DON'T FREEZE.
@
I never freeze
@
froze
From my school years I remember this olympiad as a trash. Seems like not much have changed. No offence.
But it was offensive
Btw why?
Cause it's just my opinion, and I don't wanna be rude or something. Just really don't like it.
Low problems quality. When I participated, it was 4 very-very easy (like div2 A) problem with a lot of stupid coding, and one hard geometry problem. So the places were distributed by points in only one problem (on olympiad there are problems with subproblems, you get points for solving subproblems, no time/resubmit penalty). This time they are harder, but still boring/stupid.
Yesterday's difficulty distribution was good though :)
I don’t know which problemset you are talking about. Any link would be helpful.
You are welcome to become one of the problemsetters, if you have "not stupid/not boring" problem ideas in your mind.
Don't be angry because you can't solve them
Unrated Round cy >(
fucking long queue!
What is this? There is 10 pages long queue. (~700 submissions only in div2)
Make this round unrated >.>
Today's day is so good : I am performing wonderful in the contest and queue is helping me in it :)
Hope it doesn't get unrated.
what is this? This much Queue
goodness me there is a 10 page+ long queue. Please fix it asap!
13 page long queue ! what is this !
You know the queue is so long when you're in Div.1 and the "In queue" verdicts' region is wider than a 50-line page...
70-lines to be exact.
Shit man! I really hope the round won't be unrated because of the long queue.
It's taking a very long time to process submissions...
Seems to be fixed now.
The judge is running too slow . so frustrating at times .. look into it
Tomorrow is my Exam but still i'm giving the contest to get away from the stress situation but these long queues of codeforces are giving me more headache than my syllabus did.
Are DIV 2 Contests getting harder or I'm the one who is getting dumber ??
Both
you are not true Rick :D
What the hell is pretest 10 in C?
how to solve DIV2 : B?
Check if there is number from y to y-300 that is not divisible by any number from 2 to p. 300, because prime gap is at most 300 in this number range
prime gap is 300?
Yes, maximum distance between two primes is a bit less than 300 in range from 1 to 10^9
"because prime gap is at most 300 in this number range" can you please elaborate it a little?
You can find it on wikipedia, just search for prime gap
thanks mate! I have wasted my 20 mins on this:(
since p can also be of order 109 checking in
[2, p1 / 2][2, min(n1 / 2, p)] is enough.Please explain a little why we check only till sqrt(p)
If P has any divisors, it can be written as a*b. Now, if a is less than sqrt(P), then b must be greater than sqrt(P). Therefore, either a or b is greater than sqrt(P). So, if divisors exist, we only need to check up to sqrt(P).
Thank you
can u help me to figure out why this is wrong my submission
You are only checking divisibility up to mn = min(1000LL, p); but should be sqrt(y), since y could be 1E9, whereas 1000*1000 = 1E6.
why 1000?
my bad :( got it!! thanks
prime gap: https://en.wikipedia.org/wiki/Prime_gap
what if p is 10^8 or greater. wont it get TLE
You check for prime divisors of i where y-300<=i<y. If divisor is less than or equal to p, i is not the answer. So you check for sqrt(i) numbers
i checked for all divisors of i (sqrt(n)) upto i — 500 and if yes print
Then why is this solution wrong ?
https://ideone.com/3YAlQZ
case 2, 9 answer is 9
check 2 9 output should be 9
the solution need not be prime everytime. The only condition it must satisfy is that in the range [2, p] it doesn't have any factors!
Thanks guys. Silly bugs everywhere :(
You don't need to do calculate any prime gaps, just work backwards from y. Because you know that there won't be a huge prime gap, you are sure to find something pretty quickly. http://mirror.codeforces.com/contest/937/submission/35691076 Just be sure to leave the loop once you find it and to only check up to sqrt(y) when searching for divisors
How to calculate the time complexity of your code WolfBlue
In the worst case, outer loop runs until we find a prime number, so when calculating the complexity you need to use prime gaps, but you don't need to actually know the exact value to implement it, just know it is relatively small. Let P(n) be the largest prime gap. Complexity will be O(P(y) * sqrt(y)). Because you are checking up to sqrt(y) to find divisors, and you are doing this at most P(y) times.
How to solve Div-1 C?
First turn the string into a permutation, that we want to transform into 1,2,...,n. Then, starting from n/2, start constructing the string. In a single step, do: 6789...5... --> ...6789...5 --> 5......6789 --> 98765...... This reverses the string we've built, and adds the number we wanted to add to the end of the reversed string. Use this to append small and large numbers alternatingly. It takes 3*n = 6000 operations.
I had similar idea to other one.But I wanted to share my way of thinking.I could easily come up with 4*n steps for building from one corner to another. But the 4*n was coming because each time the string was coming reversed so that wasted n steps to straighten in it. So doing from middle and adding a letter on each side we can get rid of straightening here.
4*n approach: assume u have come to this form S.... S is suffix of required string . Now I will describe a method to convert it to Y.... where Y is bigger suffix by 1 than S. So now we find character before S in t and flip it there so now ....Y... we have.Now we have to bring Y to start for that we reverse whole string(...rev(Y)...) and bring rev(Y) to end (....rev(Y)) and now flip from just before Y giving Y..... . So main idea is getting rid of reverse whole string by doing operations from both sides.
I extend the prefix like you do in your 4N approach, but each time I add a letter from a different end considering that s[0] and s[n-1] are adjacents. At the end the string may need to be reversed and/or rotated. Reversing it is simple: op(n). Then if it needs to be rotated X times, you can do that with 3 operations: op(x), op(n-x), op(n).
Problem E is fucking awesome (no sarcasm)
Again a good problemset... Thanks codeforces.
What is hack test for Div.2 D???
Something like
4 4
1 2
2 3 4
0
1 2
1
You can't win, but you can draw by cycle 2->4->2
My code gives the right answer, thanks :D
I was fearing something harder
You can check also odd length cycle, then you must win.
too many bugs in my solution, yet it passes pretests.
seems like bad pretests
Suppose, it was against invalid back path construction. It is not enough to build back path until start vertex is found, the additional condition of stop must be the first player in start vertex.
Otherwise for the path like (1)->(2)->(3)->(1)->(4)->(5) the first player can win in case of complete path walking, but back path construction, with mistake mentioned above, brings to only (1)->(4)->(5) which is not the win of the first player.
What were the hacks for B?
What was the solution for DIV2.B?? was there primality check involved?
Hack
May anyone tell me the core issue to raise a TLE in pretest 4 of Div1B/Div2D? ;)
Here is my last solution, sorry for the code being so messy...
Maybe you didn't judge the condition when there is at least one circle in the graph,but there don't exist anyway to get to a point with a 0 outdegree,then in this case he could at least draw?
I didn't pass all the pretests until the end of the contest(it may be something wrong with the output of the path),but I failed on pretest 4 previously,and after I found this condition and judged it I passed pretest 4...
Hope it can help you,and sorry for my bad English
Well, seemed like I got the issues. I did check for such, but I was totally careless when handling my condition-checker in
returncommaands.Not sure if it could save me from TLE-ing, but at least it was wrong.
Thanks ;)
MATH, MATH, everywhere MATH.
Hack for D div 2:
Expected :
What is the answer? Edit: You already edited your comment. Thanks !
Sorry I forget to write the answer ... I edited it
Thanks, i hope my solution is right.
how the answer can be win ? when petya moves from 1 to 2 vasya will move from 2 to 5, as both will play optimally. so how can petya win?
They don't play optimally, Petya plays for both of them.
ohh ! I wrote the condition for optimally well. As i thought that petya checks whether he will win the game no matter what vasya will move after sleep, or make it draw. And how did it pass the pretests ? As the checking condition itself is entirely wrong
pretests are weak in this one, probably intentionally. which is a good idea for div1-B but not good for div2-D.. but i guess thats a disadvantage of mixed round.
pretests are weak. But the checking condition itself is entirely wrong.
coincidence
Your solution fails for this:
3 3
1 2
2 1 3
0
1
Answer is Draw.
Idk how you passed pretests, I guess they are weak
It fails for all cases as my checking condition itself is entirely wrong, as i misunderstood it.
https://postimg.org/image/ts93ksg85/ still waiting :)
Can someone please explain the logic for solving Div2.D/Div1.B ?
You need to reach a childless node in an odd number of steps to Win. You can track the parents of all nodes that can be visited starting from s in an odd and even number of steps and their in a 2*n array.
If one childless node can be visited in an odd number of steps, you win. Else, you draw if there is a cycle attainable from s. Otherwise, you lose.
Edit : my condition for cycle detection was wrong. You have to check explicitely for cycles starting from s to differentiate draw from loss
Nice. Thanks !
Not really. If a cycle has a way in and a way out, which lead to a childless node by an odd number of steps, you can still win.
Also, if a cycle has an odd number of sides, any path from it to an arbitrary childless node can lead to victory as well.
how to check if there is an odd cycle?
(Actually, I wasn't able to solve it probably — it got TLE verdicts).
Since I can't handle cycles properly, I used Kosaraju's algorithm and divided vertices into SCCs.
Then, the condition to call each DFS function is to check if there has been a path from s to that vertex with odd/even number of edges (based on the oddity of the currently working-on-vertex).
can u tell me why my code is wrong http://mirror.codeforces.com/contest/937/submission/35735167
For the failed case, Someone else marked vis[node] = 2; for node = 45.
So, when you tried to end game by visiting 45, it was already visited in some path so it was never even tested.
Basically, you aren't trying certain paths once that node is visited in some other path.
If you (implicitly) create a bipartite graph G', with twice the number of the original graph, one vertex for each (vertex, parity) setting, and the same relative neighborhoods and perform a DFS on that graph, this case will be treated without having to explicitly detect odd cycles.
Hi, Can you suggest some readings/problems based on the similar idea? A lot of programmers have used this technique, is it well known?
My algorithm will go at most twice through every edge : once when you reach him with an odd number of steps, and once when you reach him with an even number of steps.
I believe this takes care of these two cases
How do u calculate if a childless node can be reached in odd number of step(I mean there could be cycles)?
Thanx in advance!!
Is this solution correct?
We have to reach the start node from childless node in odd number of steps.So lets say we color the nodes starting from the childless node.lets say i color the childless node with black.So i'll color its adjacent white.So the question comes that whether the source vertex can coloured white.
So just do a sort of bfs with two visited array ,vis1 to denote if it has been coloured black,vis2 to denote if it has been colored white.
push all childless node and start the normal bfs,i mean if i am black and my adjacent are not white then push them,else dont.
each time you visit a node, mark all his children to be visited with the opposite parity, if they have not been visited with this parity. You'll find out in O(n+m) if each node can be reached in an odd or even number of steps, then you can check the childless nodes one by one
will this handle the cases where there is an odd cycle in the path from s to any vertex?
Could anyone give any hint to solve div2 D?? Thanx in advance!!
Just replace any vertex v to vertex (v, 0), (v, 1) and any edge u -> v to two edges: (u, 0) -> (v, 1) and (u, 1) -> (v, 0). Now you can do simple Dijkstra from (start, 0).
If you pass pretests on a submission and then get compilation error on the next, does the accepted solution go through system testing or does cf take the last submission even if it gives WA/compilation error?
In div-2 D, when I tried to hack and got unsuccessful attempt, I realize I misunderstood...
I thought the real Vasya starts after some point, So for have a draw, in every possibility they cannot get out of the loop .
3 3
1 2
2 1 3
0
1
my answer is Lose for it although the real answer is Draw :(
Another hack for B. Although i din solve D, as i found the test case in which it will fail 35 min before the end and i could not find the solution, this is it. 8 8 1 2 1 3 2 4 6 1 5 1 1 1 7 1 8 0 4 ans is win and 4 5 1 2 3 6 7 8
Спасибо за интересный раунд, надеюсь на + к рейтингу
For div2d ..
if: find any path to a leaf and it's vasya's turn --> win
else if: cycle --> draw
else: --> lose
What's wrong ?
Edit: never mind. My code contained a bug
else if: cycle --> draw
You must also check if you can reach that cycle.
also, any path can contain itself contain a cycle (might not be required to traverse same cycle more than once though, not sure)
The fact is that while traversing if you en-counter a odd length cycle, it can be used to change the parity and reach the same state with the other parity of the solution.
How people could solve problem C in 1 minute? Like LoDThe.
idk
its fking impossible
Possible because questions were from some innopolis olympiad.
in D div 2, assuming both petya and vasya play optimally well right?
Vasya doesn't even play how he can play optimally lol.
No we have to favour petya (check test case 1) vasya can move 1 -> 2 -> 5 but we favour petya thats why 1 -> 2 -> 4 -> 5
since petya plays first, how will he wants to lose. And what i thought is petya is checking whether he will win, if tomorrow vasya gets up from sleep and play optimally. AND by the way how did it pass the pretests ?
you are checking petya can win or not irrespective of how vasya will play, if vasya will play optimally there is no way petya can win in first test case.
He can. if petya goes to 3, instead of 2, He will definitely win, As petya moves first.
yes if petya will play 1->3 than vasya can't, but both the moves were made by patya, so petya is playing optimally, and vasya's moves always favouring petya
In problem D : my codes second one is correct :( :(
Unable to parse markup [type=CF_TEX]
https://www.diffchecker.com/FXKB7hnMUPD : second one also wrong ! :))
long queue but nice round, hope rated!
4 4 2 2 3 1 4 1 4 0 1 hack for div2 D: ans is lose
Doing the hard work but getting WA due to wrongly implementing cycle detection as in a non directed graph = priceless
pretests were too weak.. i was using 0 indexed vertices instead of 1 indexed vertices in dfs and still it passed the pretests
Can anybody tell me what is the time complexity of this code for DIV2 B.
around 300 * sqrt(10^9)
Late hack announcement! Little too late!!!
I submitted Div1B in 01:22:38 and it was hacked in 01:31:59. Room
But I didn't get any hack announcement notification during the contest time. I checked my submission couple of times in Room standings and Common standings but didn't see that it had been hacked. Even, I refreshed the main Problems page and standings page after the contest had ended, till then it was in "pretests passed" state instead of "hacked". I only got a hacked notification during the system testing. I didn't take any screenshots for proof as now I think I should have (sorry). Now I am thinking, how much a late hack announcement/update can affect a contestant? Also had anyone else experienced this?
My Div1B was also hacked without giving me a pop-up notification whereas it should be given immediately right after a submission is hacked in normal practice.
Luckily, in my case the verdict showed correctly with "hacked" in "My submission" page. As a result, I was not affected by the missing of the pop-up notification after all.
Poland stronk!
Tanks in advance!
Ooops! Something has broken down in Codeforces :<
In Div2 problem C: what is the correct output for this test case: 999999999999999999 999999999999999998 1000000000000000000
1000000000000000000.93750000000
i got 1000000000000000000.93750000000 and 1000000000000000000.00000000000 and 1000000000000000001.00000000000 from different accepted codes
hmm.. I think its something about the precision. Mine returns the .9375 one
Thats because mod(x-y)/max(1,y) should be less than pow(10,-9) which is true for all accepted code
x,y are expected and actual output
I am getting 999999999999999998
1000000000000000001 here (on AC code).
1000000000000000001 to be exact, but just 1.0E18 works
How did LoDThe solved div2A at 00:02:12 and div2C at 00:03:38 in div2?
No one in the top20 positions in div1 solved div2C in under 4 minutes, and he even solved A before!
He took part in offline part. Just cheats and no more.
P.S. His name is Igor Balyuk
Shouldn't this be taken care of? Because it'd affect the rating change. I mean if he took part in the actual contest before, then it's not fair.
hope :p
Of course it wasn't fair. I believe somebody should fix it.
And the rating has been updated, they won't fix it :( And I'm only 2 short from being a Candidate Master :( It's not fair. I would have been Candidate Master if he didn't participate :( I'm so frustrated now...Can't anything be done?
I write to niyaznigmatul and KAN about this problem and don't get any feedback. Lets think it's legal to cheat on rounds.
D went from ~400 ACs to ~70. E F F C Y C L E S
I got WA for problem DIV2 D on test 28 which was:
Participant's output
Win
233 971 277 477 871 502 673 37 219
Jury's answer
Win
233 864 714 151 370 604 141 233 971 277 477 871 502 673 37 219
what was wrong ?
Your answer is an odd length, the correct answer must be even length...
To win you have to have a path of even length
I made a terrible mistake while printing path :(
If it makes you feel any better, I made the exact same mistake. :(
Well, to win you need go from 233(turn First Player) to 233(turn Second Player).
Why am I getting the wrong answer for div2B. I used the segmented sieve and I am getting the correct answer when I run it on my pc.Here is the code..
You mean to say you're getting the correct answer for the case that is failing?
Testcases for E are too many..
Currently, Div.1 contest doesn't have a final result yet, because of this.
If molamola.'s solution for Div1E is correct, he/she will make it to the 3rd place. Cheers! ;)
UPD: Accepted. Congrats!
Thanks!!
В div2 минут 10 как дорешивание открылось, а в div1 всё еще проверяется одна единственная посылка по Е... хорошо, наверное, что только одна)
i got wrong answer in C-Div2 because the output number was in double format like that 7.67538e+017 insted of 767537647587662141 , so is that my fault or the judge fault
If you are using cout use cout<<fixed
Running the same code on the computer gives different results from that when it's run from the judge! Link
In this function:
You didn't handle the case when x is a prime number. It is an undefined behavior, therefore the result it returns may differ from varied compilers.
totally agree with u, in my computer I get -1; So I change this code a little bit, 35711545 , It passes test 1.
Hope it is helpful @ LouaiZahran
Thanks a lot! AkiLotus Wavator
Rating changes take forever when you want them to be quick.
You may use this site to get an approximation https://cf-predictor-frontend.herokuapp.com According to it you'll become purple with an increase of 150 points Congratulations :)
Yes.
Never purple again! Congrats!
Hmm.. Feels like someone was writing div1 and div2 contest in the same time http://mirror.codeforces.com/contest/937/submission/35707300 http://mirror.codeforces.com/contest/936/submission/35706280
It doesn't make sense. Why did he do that? I could understand testing div1 solutions on div2 pretests, but he submited div1 earlier than div2...
Can somebody please tell me why my code for D gets a TLE at pretest 4? Link- http://mirror.codeforces.com/contest/937/submission/35711753
For some reason, the DFS function is running into an infinite loop- but according to me that shouldn't be, as I am using the recur[u] to act like visited[u] in a way. I used the fact that, the only way when recur[u] will be 0 again after becoming 1 is when the DFS of the subtree of u ends- else its a cycle which we detect and exit such visited nodes.
Any test case or help is appreciated. Thank you :)
(I know this can Time out for larger cases, like, vertex s leading to n/2 nodes, and all those n/2 nodes leading down to same chain of length n/2. Like a long-tailed kite. But why is it getting TLE at pretest 4 with n=50 is bugging me :( )
After done With current node you are allowing others to come back to the same node later on. Many node can come back which points to this node causing infinite’s loop.
Hi guys, while you are waiting for editorial, I'll try to help you to solve problem D.
So, our task is to find a uneven route to a leaf-vertex (a vertex that has no edges coming from it)
The answer is Draw, if the graph doesn't contain leaves at all.
If the graph has a leaf (leaves). But a route to each is only even, we need to check whether the graph has a cycle. If it does — the answer is Draw else the answer is Lose.
If the graph has a leaf with an odd route to it the answer is Win.
Now our task is to output the way to our leaf. We should be careful with it and not break a while(probably :P) cycle if our route at the moment is even!
How can we code the written above? I think, that one of the easiest way is to write a bfs and check the following:
"If we can reach a V-vertex with an uneven route then we can reach TO-vertex with an even route. And vice a verse"
My solution is here. Feel free to ask me some questions. GLHF
dfs on 2-layers graph looks simpler)
We can save sequence at once we found that answer is "Win".
Too eager to know solution for Div2 E/ Div1 C.. help required
The cleanest solution I've seen is if you perform the operation on x = n, then on x = i, then on x = 1, you move the ith character to the front, e.g. if we want to move the c to the front:
-> kacb|c|tnorf (x = n) -> frontkacb|c| (x = i) -> |c|backfront (x = 1)
Using this operation, you can repeatedly build the string in reverse order, using at most 3*N < 6100 steps.
Oops formatting:
front|c|back
-> kacb|c|tnorf (x = n)
-> frontkacb|c| (x = i)
-> |c|backfront (x = 1)
Thanks. Got it . xD
I think it would be x=i since after the first operation the character is in the n-i'th position.
Got it man. Thanks. by the way your last ans is wrong. it should be |c|frontkacb
I am seeing some pretty complicated submissions for problem B — Vile Grasshoppers.
The main idea is that the distance between consecutive primes upto 10^9 is never more than 300 or so. This allows us to start from y and keep decrementing, till we get a number who's smallest factor is greater than P. Worst case, we will not have to do more than 300 root(n) factorisations.
Explanation and code.
Lost ~1300 points because I didn't use std::fixed in the output of Div2/C...
me too :( now my rating change is -35 instead of predicted +35.
Can anyone tell me why my solution is failing at test 28?
http://mirror.codeforces.com/contest/936/submission/35722758
Cause in your solution you do not consider paths like 1->2->3->1->4->5 when you can return to previously passed vertex and still win, I guess so.
Check this out:
5 5
2 2 4
1 3
1 1
1 5
0
1
If it returns "Draw", your solution is wrong.
Тем, кто участвовал в Бишкеке результаты олимпиады не сказали. Они есть вообще где-нибудь?
P.S.: футболки и прочие приблуды до Бишкека тоже не доехали. Вот печаль-беда =(
Результаты
Вроде и не должны были доехать. Площадки соревнований создаются для удобства участников, как минимум чтобы им не приходилось искать большое финансирование на поездку. К сожалению, кроме отправки приблуд есть ещё много организационных проблем. Приезжайте на основную точку проведения финала :)
When can we expect editorials ?
Hey in the C problem of div. 2 one of my friend's code got accepted and as I was going through the test cases I found this(refer link). How is this possible? https://drive.google.com/open?id=1scjEnYJuRpkfcu2gPGvJRpBm94NcH1sH
Everyone who solved C has this problem, but the answers are definetely right
How to solve Div2 C?
Our goal is to find how long will be a chicken in a fast mode and in slow :D.
So, in first k minutes chicken will be prepared for ((k/t)*100)%.
fastMode=((k/t)*100)
Now we need to find a moment of time when Julia will again switch chicken to fast mode. This moment will be f:
f=ceil(k/d)*d => (f-k) minutes chicken will be in a slow mode and will be prepared for ((f-k)/(2*t)*100) %.
slowMode=((f-k)/(2*t)*100);
So total time of that cycle is k+(f-k). After each cycle our chicken will be ready for fastMode+slowMode%.
Now let's find out how many full cycles we will be able to "put" in our 100%. That is floor(100/(fastMode+slowMode))
At that moment our answer=floor(100/(fastMode+slowMode))*f
Finally we need to check how many percent of chicken preparation left left=100-floor(100/(fastMode+slowMode))*(fastMode+slowMode). If it is equal less than (k/t)*100 then we just add to our answer (left/(fastMode))*k, else ans+=k, left-=fastMode and then ans+=(left/(slowMode))*(f-k)
Yeah, I see it looks quite complicated , but you are free to ask questions. Maybe my solution could also help.
** P.S. When I was using % (multiplying by 100) i received a WA on test case #32. On codeforces compiler answer was "nan" while on mine it was OK :( **
UPD Corrected a formula
If d > k then your algorithm will give f = 1 => f-k = 1-k(negative for k > 1) minutes chicken will be in slow mode. Isn't it undesirable? BTW thanx for great explanation.
Yeah, I did a mistake Correct is: f=ceil(k/d)*d
Thank you for your answer.
This solution is correct but the formulas can be simpler:
Indeed, the chicken is cooked in fast mode for k minutes then, for d — k mod d minutes. Indeed, after k + (d — k mod d) minutes, you will be on a multiple of d. So the lenght of a cycle is of k + d — k % d. The formula for the number of cycles : cycles = t / (k + (d — k%d)/2)
When I ran your code for k = 2, d = 5 and t = 10 it outputs 14 whereas the answer should be 12, shouldn't it? or am I missing something?
The correct answer is 14.
After first cycle: chicken is prepared for 4/20+3/20=7/20; TimeTaken=5;
Second cycle: chicken is prepared for 14/20. TimeTaken=10;
Third cycle onlyFastMode: chicken is prepared for 18/20. TimeTaken=12;
We need to prepared chicken for 2/20, while using fullSlowMode we will prepare it for 21/20. That's why we need to use only 2/3 of our SlowMode. So the time of this part of SlowMode will be 2/3*3=2.
TimeTaken=12+2=14
As d = 5 when Julia goes to kitchen at t = 5 she will find the stove to be on. So she will not do anything and return. So The time period of one cycle comes out to be = 10.
I guess you have taken time period of your cycle = d(= 5) which I think is be wrong in this case...
How I visualized it is as follows
When the clock is high it means gas is on and when it is low it means gas is off.
You misunderstood the problem. The stove turns off by itself, but only Julia can turn it on. When t=4, who turned it on on your graphic?
Yeah my bad I misunderstood the problem. Anyway thanx for helping me.
Editorial?
17 people contributed to this contest and there is no editorial after one day!!
UPD1 : a semi editorial is posted,hope to see the complete one!
Perhaps Brooks's law applies to writing editorials, too?
although i had to use wikipedia to understand your comment's meaning, but i'm agree with you :D
I think it's more of bystander effect.
I wouldn't call this round an accident. I quite liked problem C.
Why 35710602 WA ? Div2D
Your problem is that you overlooked the case when you have a cycle with odd number of vertices where you should transverse the cycle to change the turn from Petya to Vasya and vice versa.
Consider the following testcase:
This corresponds to a graph that has a cycle 1->2->3->1 but it still had an answer 1->2->3->1->4->5 Your Code gives a wrong answer in that case as it prints "Draw" instead, you just didn't handle the cycles with odd number of vertices case.
i was waiting for editorial but after a day now i decide to ask my question here...
how to solve Div2.D(Div1.B)?
Editorial
thanks... better than nothing!!
where's the tutorial to the problems ?
pls, upload the editorials...
niyaznigmatul Div. 1 E doesn't appear to be viewable.
I'm having the same trouble.
niyaznigmatul Could you fix it?