We invite you to participate in CodeChef’s Starters 214, this Wednesday, 26th November, rated for 6 stars (i.e. for users with rating < 2500).
Time: 8:00 PM — 10:00 PM IST
Joining us on the problem setting panel are:
Contest Admin: Archit Pols_Agyi_Pols Kumar
Tester: Vaibhav kingmessi Khater
Setter: Archit Pols_Agyi_Pols Kumar
Statement Verifier and Text Editorialist: Nishank IceKnight1093 Suresh
Written editorials will be available for all on discuss.codechef.com. Pro users can find the editorials directly on the problem pages after the contest. The video editorials of the problems will be available only to Pro users.
Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here. Hope to see you participating.
Good Luck!
Contest starts in 30 minutes.
Extended by 15 min....
Contest Start Time is extended by 15 minutes ?
I have a question regarding the problem VTAR .
What would be the answer for this testcase:
Here, the answer should be "Yes" as the person2 and person3 would vote for 1 as 1 has the highest frequency. Later on 8th person won't vote for anyone as more than 1 element (2 and 3) has highest frequency. So, the answer should be Yes.
Please help me know where am I going wrong in my understanding of the question? If my understanding is correct, then the above testcase can be used as a hack where most of the accepted code fails for the above testcase.
The greedy solution simply doesn't work. I was so confused, but I could come up with a counter-example. You could find more people coming up with test cases here: https://discuss.codechef.com/t/vtar-editorial/124598
Thanks for the kind information. But, If u could also share, what would be the correct approach to the problem?
I couldn't come up with a proper solution, unfortunately :|
IceKnight1093 can you clarify the question SCAM.
In the question it is mentioned that is there any rearrangment such that K will win.
Given a member X, determine whether there exists any valid rearrangement of the known values such that X receives the unique maximum number of votes (i.e.,X wins without tying anyone else).
but for this test case
1 10 1 1 -1 -1 2 2 3 3 -1 4 4
ans should be Yes right, but editorial ans is printing as No.
Can you clarify this part.
I had a alternative solution to the last problem of Div 1 (with simpler implementation) sadly solved it few mins after the contest.
Beautiful subsequence also be solved in O(NlogN) with 2 pointers Submission
Almost the exact same idea as editorial, but since only consecutive good indices (pairs with N-1 distinct elemnts between them) matter, we shall do 2 pointers, just like a trivial problem of finding maximal good subsegment.
Say for a given good index L, we have [L....R] as maximal good subsegment, for this L. (i am iterating backwards in my 2 pointer approach)
To extend this for finding maximal good subsegment starting at L-1, we shall do this:
endpoint [goodidx[L-1]]toendpoint[goodidx[L]])(L-1,R)gets violated, it is because of any bad element (elements which do not have N-1 distinct in between its pair) who all occurences show up in the answer, (i.e, there exist 2 good index intervals, where this bad element occurs exactly once in both of them, so this bad element has to be picked by both the good intervals).For every movement of L pointer, say L to L-1, the new bad elements which may affect our current good segment, lies in from (
endpoint [goodidx[L-1]]toendpoint[goodidx[L]]) , by amortized, the time complexity is $$$ O(N log N) $$$This can be solved in $$$O(N)$$$, Submission