So we want to keep our nodes split into $$$2$$$ sets, $$$s_1$$$ and $$$s_2$$$, so that all the edges between $$$s_1$$$ and $$$s_2$$$ are directed from $$$s_1$$$ to $$$s_2$$$. That clearly keeps the tournament not strongly connected since you can't go from $$$s_2$$$ to $$$s_1$$$. Let's start with one node in $$$s_2$$$. That means the edges incident to this node are all decided. They're all directed into it. Then, let's repeat the following: whenever we meet a flip between a node from $$$s_1$$$ and a node from $$$s_2$$$, we decide all the edges incident to the node in $$$s_1$$$, let's call it $$$u$$$. We'll choose their direction so that at the current moment, the moment of the flip, all the other nodes in $$$s_1$$$ have their edges directed into it. That effectively moves $$$u$$$ from $$$s_1$$$ to $$$s_2$$$, keeping the tournament not strongly connected. Now with the choice of base case. If you choose $$$u$$$ to be the latest node to be flipped, you'll pass subtask $$$2$$$, because the first $$$\lceil\frac{n}{2}\rceil-1$$$ flips will pass without changes, and then you can survive $$$n-2$$$ more flips. If you instead try every node to be the base case, one of them will be able to survive for $$$2n-\lfloor log_2(n) \rfloor-3$$$ flips! The proof is: you may think about our operation as follows... you start with a node, and every time a flip happens between its component and outside, its component gets extended by one node. Let's focus on the first $$$n-1$$$ flips. Let's treat the flips as undirected edges. Then, one of the components has to be a tree. Let's get the latest flip on that component. Before it, the tree was $$$2$$$ components, one of them at most half as big as the original tree. You can see by induction that this means some node's component will only get extended at most $$$\lfloor\log_2(n)\rfloor$$$ times! That obviously means you can survive $$$2n-\lfloor log_2(n) \rfloor-3$$$ flips with this node as the base case.
Open questions:
Can you improve the analysis of the solution or find a case that pushes it to the limit I found? The smallest case I found that breaks it has $$$2n-4$$$ flips. If it helps you, you may think about it as finding a graph with the smallest number of edges such that every pair of nodes have a path with increasing weights. (UPD: solved, the solution indeed works up to $$$2n-5$$$ flips.)
Let's look at the inverse problem: what's the shortest sequence such that no tournament can survive? The shortest I could find has length $$$2n-3$$$. It's just the sequence $$$(1,2)$$$, $$$(1,3)$$$, $$$\ldots$$$, $$$(1,n)$$$, $$$(1,2)$$$, $$$\ldots$$$, $$$(1,n-1)$$$. The proof no tournament can survive is: it's well-known every tournament has a hamiltonian path. Let's look at the sub-tournament that doesn't contain node $$$1$$$; let the hamiltonian path in it start with node $$$a$$$ and end with node $$$b$$$. It's sufficient that the edges $$$(1,a)$$$ and $$$(1,b)$$$ are directed in the way that closes a hamiltonian cycle. You can see that this sequence of flips achieves that at some moment. So now since you can always survive $$$2n-5$$$ flips but can't survive $$$2n-3$$$, what's up with $$$2n-4$$$?
Hope the timing doesn't get changed like the last codechef Lunchtime
Congrats on reaching red!
Aww thank you :D
XOR missiles on their way, btw congrats on reaching red
*number theory missiles
Thank you :D
Problem's arranged in sorted order of difficulty ?
Attending lunchtime contest in dinner time :D
How to solve
Chef Likes Good Sequence
??Have there any way to solve only subtask.1 for Q=1 ??? I tried but failed.
You are looking for a subsequence not a subarray.
HINT: It can be done greedily.
Thank you sir..
subsequence not a subarray
its solved the problem <3The video editorials to the problems are uploaded on Youtube
Can COPAR be solved using binary search?
I tried but got WA Submission
5
5 2 7 11 2
I don't think it's possible.
My reasoning: say l is a valid splitting point, then there's no guarantee that either l + 1 will also be a valid splitting point
Ex:
2 3 7 49
as we can see we can split as : {2, 3} and {7, 49} but not {2, 3, 7} and {49}
How to solve last problem?
All problems in division 2 was based on some cool observations and I really liked it. Managed to solve all problems. I personally liked COPAR, cool NT problem.
I think that this time, the lunchtime was not balanced and as always the problems were not sorted according to difficulty, which I think should be improved in the further contests.
Why should it be sorted according to difficulty ?
Most people who are not that good don't have a sense of how hard the problem so it is good If they are sorted.
Sometimes I am not able to solve div2B and there is always a thought in the back of my mind that the problem is not that hard and I do solve after sometimes If problems were not sorted by difficult I would have left them after some time.
Can't you judge the difficulty by the number of solves? There are other contests out there (like ICPC i think) that doesn't order its problems, you just have to find the easiest one to solve. Being able to find the problem you can solve quickest is a skill in itself. Most people who are not that good aren't really under any time pressure to solve fast anyway, so judging by solves is fine. I still do that, because I suck at judging the difficulty of a problem.
agree :)
Fine for probably division 1, not for division 2. Just look at round 679. C was harder than D, even till 1 hour, C had greater number of solves than D. So, some guys tried D late, if they tried early, D could have more solves.
ICPC and Olympiads come in mind when people go in div1. So, div2 contests would be sorted by difficulty
The only rush is for the first problem and after like 5 to 10 mins everything is sorted, also when you are in div2 its easy to spot the easy problems.
Problems which are additional in div1 are the easiest one for div2. :)
what's with CodeChef not explaining the sample case and problem statement for Chef Likes Good Sequences was just garbage. I did not understand the question and was not able to solve such an easy problem.
Same for me bro ..I solved the next one which solved less than this :(