Всем привет!
Мы рады пригласить вас на общий рейтинговый раунд 586.
Этот раунд является отбором на кружок ФПМИ МФТИ и ЦРИТО по олимпиадному программированию. В этом году мы запускаем три дивизиона для школьников любого уровня: от начинающих до призёров и победителей всероссийской олимпиады. Кружок будет проводится как очно, так и заочно. Первое очное занятие состоится 28 сентября в 15:30 в центре исследований и разработки компании 1С по адресу Москва, Дмитровское шоссе, 9. Для учеников заочного отделения будут доступны записи занятий и онлайн-консультации преподавателей.
Подробнее о кружке можно узнать в посте по ссылке. По всем вопросам можно также писать в наш чат в Telegram. Если вы хотите попасть на наш кружок – нужно всего лишь заполнить форму и принять участие в отборе!
Задачи для контеста готовили Alexponomarev7, adamant, lesswrong, wrg0ababd, VeryLonelyRaccoon, CepryH9, msmlkm и я, SerezhaE. Большое спасибо координаторам 300iq и cdkrot за советы и помощь в подготовке контеста, а также отдельное спасибо MikeMirzayanov за платформы Codeforces и Polygon.
Контест начнется 18 сентября в 19:05 по Москве и продлится 2 часа. Надеюсь, каждый найдет для себя интересную задачу :)
Удачи!
UPD. А вот и разбор!
P.S. Для тех, кто хочет попробовать что-то новое, мы также запускаем кружок по Computer Science. На нём будут обсуждаться интересные задачи из данной области. Подробнее про кружок можно почитать в статье. Мы с радостью ответим на любые ваши вопросы в Telegram-чате.
is it rated?
I think copy pasted part has been skipped.
I asked the question when post didn't mention it. Now it's updated.
2 back to back contests! Reason we all like codeforces.
More like 4 except for a one-day gap.
Right! :))
This will be what, the 4th combined division round in a row for me? 5th if I count virtual Global Round 4.
Did you account for up coming round "Dasha Code Championship"? :)
I think combine round is different from separating them. People usually earn more and lose less rating. :)
Only accounting for rounds I know I can participate in.
You can't have everyone earning more rating if the sum of ratings is non-increasing (which it should be, extra rating comes from new users). It should be that high-rated contestants can lose more rating if they clearly underperform and low-rated can gain more thanks to that. There are more participants, which allows for more extreme situations.
But one clearly advantages of Div.1 + Div.2 combined rounds is to prevent people from quitting the rounds. In Div.1 only rounds, some guy can read a problem, find it too difficult and quit the round without losing any ratings. While in combined rounds, he always solved some very-easy problems first and can't quit the round.
Combined rounds should be used only for events (usually with prizes). Normal rounds are much better. Problems fit participants more and hacking is more balanced.
The time really fits Chinese! I love it!
It's literally midnight (i.e. 12 AM) in China when this starts
I hope the statement will be short and nice like the announcement :D
Why does a new problemsetter prepare a Div.1+2 contest?
Good luck to all particopants and thanks for the contest!!!
А сколько задач надо решить, чтобы я смог попасть в кружок?
How many problems?
Maybe around 8, I guess.
It will be a fun contest! :)
There are known knowns, there are things we know we know. We also know there are known unknowns, that is to say we know there are some things we do not know. But there are also unknown unknowns, the ones we don't know we don't know.
:|
What about score distribution?
Hi everyone, today we are going to play HungerGames mode in Minecraft. Guys, would you like to join us????
1AM over here in Korea! Willing to give up tomorrows class for this contest :)
I guess "problemes" is not the appropriate word!
300iq <3 contest .
а у вас координатора чтоле не было? почему у вас нет обяснений к примерам? нет объяснений, что такое "лексикографически меньше" и "двудольный граф"? почему в Е я сам должен рисовать граф из примера и путь в нём? я пишу контест в макдоналдсе без бумаги и ручки, скиньте мне пожалуйста граф из первого примера в Е
Вот
Спасибо, друг, ты вовремя
Поорал в голос с формата вывода в A:
"Выведите максимально возможное число в двоичной системе счисления. Выводите двоичные цифры, разделяя их пробелами." — это единственное, что надо знать про авторов.
this is my best contest ever !!!!!!!!!!! :)))))))) thank you so much SerezhaE
Слишком много теории графов.
Графов много не бывает
How to solve B ?
you have the results of: a1*a2,a1*a3,a2*a3
a1*a2 = r1
a1*a3 = r2
a2*a3 = r3
a1*2 = r1*r2/r3 --> a1 = sqrt(r1*r2/r3)
Hope it works after test
Can we use gcd?
I think GCD would give an approximation for each column, could you provide the context of using GCD?
using GCD I think would have to do special work for 1
EDIT: I mixed GCD and LCM :(
(For n=3 example)The first row is 0 a*b,a*c so if we get gcd(not including 0), we at least get a, but this is the problem here, if gcd(b,c) is not equal to 1, it becomes a problem. I could not figure it out for bigger value of n
Thinking in solving 3 unknown variables using 3 equations is much simpler, but for GCD you would need to do second iteration to validate values, I think you could do it that way
Thank you.
you are welcome
I have used GCD of a column... but then also to avoid some corner cases I have checked all the divisors of the GCD value for which the matrix becomes valid... https://codeforces.com/contest/1220/submission/60795097 Here is the code.
Your codes are very well written i wish only if i could also write such codes.
Thank You. IslamOmar
why im so stupid to use gcd ?
i used the most stupid form of gcd ( gcd all of the line thing ). then make up my mind and skipped B.
Well. You're not... because I've also used GCD and actually solved B using it... The only extra part was, I checked all the divisors of the GCD value for which the matrix can be valid... https://codeforces.com/contest/1220/submission/60795097 So the idea was not wrong, just needed a little modification... This is the fun of problem solving, there are so many ways to solve it. So never underestimate that. ^_^
my hero
How to solve D?
I'm not sure but... If we have A and B, where A is odd and B is even we can create a cycle with odd length. So we will use recursion There are two possible ways: delete all even numbers in an array and leave recursion or delete all odd numbers, divide all numbers left by 2 and do recursion again. We continue recursion and divide by 2 because there can be something like this: 2, 4. We can create cycle 0 — 2 — 4 — 0. So we can solve this problem with O(n log n)
you have to realize that:
A and B can be in S if and only if the maximum power of 2 that divides A is equal to maximum power of 2 that divides B.
why problem D example 1 i can't simply delete vertex 1 and 3, the problem only states that we can connect 2 vertex if it absolute value after subtract each other belong to set B, so if it in the example we should have a triangle and it doesn't matter which vertex we choose cause it gonna turn into a bipartite graph anyway
It asks you to delete the minimum number of vertex, so you could delete either 1, or 2.
You can't delete vertex 1 and keep 3.
Draw the graph for vertices 2, 3, 4, 5, 6 and B = {2, 3} and you will see it's not 2-colorable.
It's not a traingle. 3 elements in set B doesn't mean there are 3 vertices. There are infinte vertices actually
prabalsingh24 are there infinite vertices marked from $$$-\infty$$$ to $$$+\infty$$$. I am misunderstanding the statement.
how to solve D. I only know O(n^2)
Can you please tell O(n^2) approach?
One fact is you can only pick two numbers that are divisible by same power of two (for example you cant pick 6 and 40 but you can pick 10 and 22).
Start from a arbitrary number and find the next time that two integers from B can both reach to another number. that number is LCM of those two number and simply you can see if they are not divisible by same power of two then you can find an odd loop.
We want lcm(a,b)/a + lcm(a,b)/b to be an even number, so either both terms should be odd, or both should be even. let a = 2^x * ..... and b = 2^y * ....
If x > y then (lcm(a,b)/a) = 2^(x-x) * ... and (lcm(a,b)/b) = 2^(x-y)*.. so, the first number is odd, while second number is even.
If x < y then (lcm(a,b)/a) = 2^(y-x) * ... and (lcm(a,b)/b) = 2^(y-y)*.. so, the first number is even, while second number is odd.
If x = y then both are odd number.
Hi , is this an observation or is there some mathematical proof behind this? Why cant 4*a and 2*b (where a and b are odd numbers) be in the set? sorry if its a noob question , but i am not able to find a proof for this.
Consider this example :
0 2b 4b 6b ... 4ab (Theses 2a numbers make a path because of having 2b in the set)
0 4a 8a 12a ... 4ab (Theses b numbers make a path because of having 4a in the set)
So you can see it makes a loop with size of 2a+b and that's an odd number so graph is not bipartite.
The loop is like this : 0 2b 4b ... 4ab 4a(b-1) 4a(b-2) ... 4a 0 .
how to solve problem D?
in the set there can only be numbers of the form
2 ^ s * i , where i — any odd number, and we can iterate s
Can you explain why
I explained it here .
Awesome problems, Really like them .
Nice job!
Wow, second round in a row I'm f**king with epsilons in geometry for no good reason. Just wow.
AAAAAAAAARGH
Maybe it's finally time to write a geometry library using bigints only. Or something. -.-
(At least it's gonna be useful on GCJ geometries.)
I tried something like: consider several small primes, get possible values of X and Y modulo them, combine it using CRT. I didn't have enough time to think it through but maybe it is the intended solution.
Can it solve the problem for n=2? If so, it seems reasonable to be (part of) the intended solution.
Just doing all calculations mod $$$MOD=10^9+7$$$ suffices. Suppose that we want to find the intersection of two circles in the form $$$(x-a_i)^2+(y-b_i)^2=c_i\pmod{MOD}$$$ where $$$i=1,2.$$$ First subtract the two equations to find the radical axis. Then substitute for $$$x$$$ in terms of $$$y$$$ (unless $$$a_1=a_2$$$) and solve the resulting quadratic with modular square root.
(Code: 60845080)
Better way (No quadratics) to find intersection of circles: Wolfram link From Wolfram link you can find how to calculate intersection $$$(x;\pm y)$$$ if centers are $$$(0,0)$$$ and $$$(d,0)$$$. If centers are $$$A$$$ and $$$B$$$, treat them as complex numbers, then intersection points are $$$A+(B-A)*(x/d\pm i*y/d)$$$. I have doubt about my solution, because I only checked 20 distances to other points (if it is subset of given multiset it passes). How it doesn't get WA? (Code: 60952855)
Checking if distance from center of mass is exactly as needed makes solution faster. After this check you can try about 100 points around the intersection and not get TLE.
Having finally solved this, I want to strangle the next person who mentions geometry to me in person. I tried so hard to make calculating cos() from cosine theorem precise enough, but in the end, I gave up and did all subtraction in bigints.
thanks for weak pretests for B! 4 hacks, yay!
I'm scared for system tests now.
Can someone tell me what is the 12th test in problem D ? :(
No.
In problem D. when you finally notice $$$i,j\in N$$$. not $$$\in B$$$... :(
What? Really? Noticed it right now :)00)
I think the statement was very poor in problem D :/
I agree. And I talk the statement to people knowing nothing on math and programming, they think that's for integers in B. By the way, I have checked manually the first example during the contest, the result is OK for this understanding as well...
I would say its nothing about knowing math or programming, its about the confusion that the problem statement has. Notice that even a lot of candidate masters were confused.But you are absolutely right, the statement supports the both way of thinking.
[Deleted]
I spent 1 hour thinking a different problem :c I didn't notice that until now xD
Ow maan, but, $$$i, j \in \mathbb{Z}$$$...
Awesome problems, really like them.
Nice job!
How to solve E? My idea was to continuously remove vertices with only one remaining neighbor (except the source), compress the rest of the graph into one component, then restoring the removed vertices find the path with largest sum starting from the component/vertex where S is. What is wrong with this or did I just do something stupid?
any node in a cycle or in the path from $$$s$$$ to the cycle, can be always taken by $$$s$$$->cycle back-> $$$s$$$. all the nodes can be treated as $$$s$$$. so remaining graph is a tree. find longest path to some leaf.
Yes, that's what I do. Probably I have some stupid implementation bug ...
What do you do in this case?
The optimal path is (s) -> (compressed graph) -> (node on the left). Are you sure you don't for example count the weights between (s) and (compressed graph) twice?
No, I (at least in theory) compress S, the middle node, and the compressed part together. So the final graph looks like
A — B — (S+middle+compressed)
What a huge gap between C and D !!
How to solve F ?
Notice that element $$$a$$$ is an ancestor of an element $$$b$$$ when it's minimum on a subsegment from $$$a$$$ to $$$b$$$. Count amount of ancestors for every element in initial permutation. Now, when you remove element $$$l$$$ from the left, all elements between it and the leftmost element smaller than $$$l$$$ now have one ancestor less. When you move it to the right, all elements between it and the rightmost element smaller than it have one ancestor more. You can store amounts of ancestors in a segment tree with lazy propagation. Solved.
How to solve C??? Use suffix array???
Just consider the smallest char already seen. The game will not last longer than 1 move :)
Hi, I understand that there will be only one move in the game. Can anyone clarify why we are comparing only the first character with the substring?
Only thing that matters is the first character on the left that is smaller than s[k]
The game either has 0 moves or 1. If a smaller alphabet occurs before the start pos, ans is Ann, else Mike.
Not sure though.
Thanks everybody. It was seriously difficult problem...
Instead of choosing smallest alphabet, what about choosing smallest suffix before current index? Doesn't it work similarly?
It does, but it's harder than intended solution
I think it doesn't as I first used suffix array and failed on test "abas" for k = 3.
Well actually it didn't...
I first used suffix array but failed on test as "abas" as for k = 3 the answer is Mike not Ann but using suffix array would print Ann as suffix "as" is bigger than "abas" but after that I realized the simple solution considering the minimum char already seen!
That's absolutely right!!! Now I understood why my approach got WA. Thanks a lot!!!
Couldn't you give some actual samples in F? Especially in order to distinguish rotating to left and right xd.
^ This.
I think I've seen F in a atcoder round, not sure. I do remember the trick of storing $$$X_{i} + Y_{i}$$$ in a segment tree, where $$$i$$$ is the longest decreasing sequence starting from $$$i$$$ to the left, and $$$Y_{i}$$$ is the longest decreasing sequence starting from $$$i$$$ to the right. Then the depth of the cartesian tree is the maximum of $$$X_{i} + Y_{i} - 1$$$ in the interval, and $$$X, Y$$$ are easy to update.
Seems completely doable without that to me. Duplicate the permutation, then for each index, calculate the depth the tree rooted here would have if it covers everything between the closest smaller elements to its left and right (excluding these). Finally, for each index, calculate the depth of the tree we'd get if we took everything from the closest 0 to the left up to this element, using these precomputed simpler depths; same for closest 0 to the right.
I almost managed to code it in those 20 minutes I had left after getting E passed... damnit.
Another solution — if we add an element to the right, the depth can only increase and if we delete one from the left, depth can only decrease. So we can binary search to find the points where the depths of the left and right subtrees are closest.
The answer is non-decreasing with respect to expanding the interval. So, you can binary search on the answer, and for a fixed $$$k$$$ find the maximum interval to the right of $$$1$$$ that has depth $$$k-1$$$. Now simply check whether the rest (to the left of $$$1$$$) can also be done with depth $$$k-1$$$. Complexity is $$$\mathcal O(n \log^2 n)$$$, but quite fast in practice.
We can actually simulate the entire process as well and get depths of all cyclic shifts.
Moving from one cyclic shift to the next will require simple range updates.
Объясните кто-нибудь. Почему в задаче В, на тест с условия ( n = 3 ), я вывожу : 19998, 5000, 4999 — я получаю WA ( 19998 != 9999), когда этот ответ тоже есть правильным ? В ответе задаче сказано: если есть несколько ответов, выведите любой. Тогда в чем причина ?
5000 * 4999 != 99980000
Позиции 2 3
5000*4999 != 99980000
Что-то не так с буквой B. То ли условие бывает непонятным, то ли авторское решение неправильное, то ли претесты слабые. Слишком слабые претесты. Не видел до этого, чтобы у стольких красных падала задача B.
Made one wrong assumption for D, got stuck the whole contest: I assumed that the set of elements taken finally for forming bipartite graph,say has minimum element k, so all other numbers of set must be odd multiples of k. Anybody made the same mistake ? :(
yes
And which version is better? I know people preferring either.
I prefer second version but without weird version of $$$\leq$$$.
I don't care too much about scientific notation vs lots of 0s, but I think the horizontal line ≤ and ≥ look much nicer.
Is WA in case 49 (problem B) an overflow? (using Int instead of Long Long Int)
Yes probably. You need 64-bit integers to solve the problem.
I took me 15 minutes to find out from my first submission :v
Правильно ли я понимаю что в задаче Е можно было использовать одну и ту же дорогу дважды?
Почему тогда в условии написано "ни в какой момент времени"?
Лёша считает, что его поездка по стране будет интересной только в том случае, если ему ни в какой момент времени не придётся ехать назад по дороге, по которой он только что проехалИмелось в виду, что из текущей вершины нам никогда нельзя возвращаться в ту вершину, из которой мы в данную прибыли пройдя по обратному ребру.
Автор выбрал самый запутывающий из всех возможных способов это объяснить
What is test 46 in E?
It is generated test with a tree and many loops of size 3 added to it.
It contains some cycle with zero weight.
In problem E statement, this sentence make me confuse:
"Alex believes that his trip will be interesting only if he will not use any road twice in a row."
and the phrase "in a row" can be viewed as "continuosly". So I totally misunderstanding this problem (I think a edge can be use twice)
for alex and julian question d, for given input 5 10 20 ,erasing 10 is sufficient but why answer is 10 and 20
It's not sufficient to erase 10.
5 & 20 create odd cycle which is not bipartite:
My solution for B: 60809853. I get the gcd of all elements in first row, this results in $$$a_1 * constant$$$. For every divisor of this value, I try to see if this is "valid".
The validation assumes that the divisor is $$$a_1$$$, I can get $$$a_2$$$, ... $$$a_n$$$ from the first row. then using these values, I check if $$$a_i * a_{i+1}$$$ matches the given table. Could somebody tell me why this is sufficient?
Может хватит бухтеть и дестабилизировать ситуацию на Codeforces? Есть инфа от знающего человека, что у нас на сайте скоро ожидаются реальные изменения. После того, как стабилизируют ситуацию с серверами. Тогда везде будут нормальные претесты. B-задачу поднимут и будут держать, системное тестирование ничего не сможет сделать. Сейчас главное не бухтеть. От нас требуется сидеть тихо. После того, как все сделают, все будет у нас хорошо.
Can anyone explain how do we decide a substring is lexicographically less or not in problem C? Please help.
Here
Thank you very much
Can you clarify why we are comparing only the first character with the substring?
Since the first substring to use is $$$s[k,k]$$$ it's just a letter, and it can only be beaten by a string that differs in the first letter. Thus, if no $$$s[i,i]$$$ can beat $$$s[k,k]$$$ in the possible range ($$$[1,k-1]$$$ or empty set if $$$k = 1$$$), then there is no possible move (Mike wins). Otherwise, our best choice is to move to the minimal $$$s[i,i]$$$ since the other player won't be able to make a move from there (because it's the minimal) (Ann wins).
Сережа Ещкере лучший проблемсеттер из Саратова!!!
How to solve D?
nice contest! There is one problem with no solves while all the other problems were solved by the top contestants in under 40 minutes.
I have got an message from codeforces telling that one of my answer is matching with some other user. But I have not copied or not given my code to any other user. As far as I can understand maybe the other user has copied my code from ideone.com, i have valid proof of that. If someone can help please let me know and what would be the consequences that i have to face if it's not resolved.
I don't understand, did you publish your solution? But why
Some contestants hacked in problem B after contest and before rate change by dorijanlendvaj and the scoreboard does not change for them .Could anyone explain me why ?
https://codeforces.com/blog/entry/68204
Hacks made after the contest has ended don't affect the verdict(probably so that the scoreboard stays the same as at the end of system testing)
Got WA on D in test 54 because I didn't know (1<<n) is an int from what I understood. How do you make it a long long then?
http://codeforces.com/contest/1220/submission/60799996
1ll<<n
(1ll<<n) 1(ll — means long long)
When will be the editorial?
I think problem D is one of the coolest C/D problems of CF rounds. So, I just want to put a detailed solution here :P, if anybody is interested...
Take two numbers $$$x$$$ and $$$y$$$. When two numbers cannot be in a bipartite sequence (the complement of required output)? If they both are in the bipartite sequence, we can find a cycle of length $$$\frac{x}{\gcd(x,y)}$$$ + $$$\frac{y}{\gcd(x,y)}$$$, which must not be odd. Also, both of the terms cannot be even (otherwise gcd could be doubled). Only fuss is when one of them is odd and other one is even. This essentially means that their least significant bits are different. Now, we already have a necessary condition — group numbers by their least significant bits, if two numbers are in the bipartite sequence, then they have to be in the same group. Wait, but can this be sufficient, meaning, can we take a whole group (the maximum sized one)? Trying not to be saviour of the human race, seeing that this is a Div2D, I quickly infer(?) that this has to be sufficient! Voila, AC! After the contest I proved it as follows: Let the chosen bipartite sequence be $$$S$$$ and $$$k$$$ be the lsb of all numbers i.e. $$$\forall x \in S, 2^k \mid\mid x$$$. Suppose, there is an odd cycle $$$c_1, c_2, c_3, \ldots, c_m$$$. Take a look at the values of $$$c_i \mod 2^{k+1}$$$. This value must be alternating between $$$0$$$ and $$$2^k$$$. So, if there is an odd cycle, it has an odd number of nodes, thus that cycle cannot afford this alternating property. Contradiction.
It can be proven more easily.
If two numbers in the set are $$$(2a+1), (2b)$$$, then $$$2*(2a+1)*b$$$ makes contradiction. That means that all numbers are either odd or even. If odd -> we have a bipartite set of odd/even numbers. If even -> divide all numbers by 2.
As for me, memento's proof is more interesting as it has some reasoning on how such an answer was obtained. In author's solution we as well started from $$$x/gxd(x, y) + y/gcd(x, y)$$$ to see that any pair of numbers with different lsb give contradiction and then we saw that if lsb is same, we can divide all numbers with it.
Yours is, indeed, simple, but once again I'm confused with the fact that someone who tried to explain something and didn't make any mistakes while doing so gets downvoted.
But the short proof also has reasoning. You start by looking for an obvious case where we get an odd-length cycle (odd+even), which gives two cases you need to analyse and notice that one is "ok" and the other can be solved recursively.
CF.
mathforces
G has a lot in common with P5 from Romanian Master of Mathematics 2011: https://artofproblemsolving.com/community/c6h393848p2188641
Namely, following the same reasoning as in that mentioned problem (which is basically using a Steiner theorem or as some would prefer to put it — simple tricks on formulas) we get a conclusion that all candidates lie on a circle whose center is center of mass of antennas with some known radius.
They're pretty similar indeed. Well, I'm not any kind of maths Olympiad guy, so I totally missed it. And yes, simple tricks on formulas is the way I prefer to call the intended solution :D
Btw, are you talking about parallel axis theorem?..
Yes, I am talking about exactly this theorem. When we shave off all that physics blabbering about some moments of inertia what we get is that
where $P_i$ are some points on the plane and there are $$$n$$$ of them, $$$C$$$ is their center of mass and $$$Q$$$ is some arbitrary point what immediately gives us $$$d(Q, C)$$$, what means that all hypothetical candidates for point $$$Q$$$ are on some fixed circle.
Hey, moments of inertia are cool actually! Why would we shave them off? >:(
I knew the theorem from the Physics, by the way, but couldn't relate it with the problem this time. Kind of shame for me, since it seems to be third programming challenge I give somewhere based on something near inertia moments :D
Well, yeah. Moments of inertia are just symmetric bilinear forms after all, getting to a circle from that isn't tough. Even in experimental physics, if you want to know moments of inertia for any axis, you just need to measure 3 principal ones (corresponding to eigenvalues+eigenvectors) and use the fact that all moments of inertia lie on an ellipsoid.
.
Is the editorial published??
Yes
Sorry, but where can i find it? Could you share the link, please?
Now I realized that I misinterpreted D. I read "let all integer numbers be vertices" as "let all integers in the set $$$\bf B$$$ be vertices," and struggling with completely different problem...
Really? I understand the same as you. Waiting the editorial for the analysis ...
Will the editorial be published?
Thanks for fast editorial.
have you found it? Publish the link pls
I hacked my solution E after the contest. submission:60808754(https://codeforces.com/contest/1220/submission/60808754)
I hope everyone is able to picture the meme that should be posted as a reaction and we can move on. You can save your upvotes for the poor.
Can you please tell which case was missing?? k24
Got it!
Please make an editorial. Or at least answer whether there will be an editorial.
Editorial is out now. Thank you!
how to solve problem C?
the thing is when is you start with L=R=i you can never make R=R+K,K>0 as it will always increase the sequence lexicographically, also you only move to any L=L-K,s.t., a[L-K]<a[L],so it will decrease the sequence,so you have many options, but as first player wants to win he will place L for the leftmost possible,else the second player wins,always.
Hello everyone, I was wondering how accepted solution of problem D is solved. I was going through teh solution and noticed that i cannot come out with the same output as those accepted solutions. I think test cases are too weak for this problem. 2 1 4 My answer is 0 as both are disconnected and hence bipartite. But accepted code's output is : 1 4... Can any please explain where am i getting it wrong? SerezhaE
Perhaps you are making the same mistake as me. Maybe you are thinking about a graph consisting from two vertices (1 and 4) and no edges, right? Actually, it's wrong. You have to think a graph with infinite vertices, among whom every pair of vertices whose difference is 1 or 4. Therefore, there exists a cycle of odd length, $$$0 - 1 - 2 - 3 - 4 - 0$$$, which means that this graph is not bipartite.
I think the problem statement was ambiguous for some participants, and it was virtually impossible for those who misread to realize it, because sample cases on the problem statement was too small and has no explanation.