Pols_Agyi_Pols's blog

Invitation to CodeChef Starters 214 (Rated till 6-Stars) — 26th November
By Pols_Agyi_Pols, 5 months ago, In English

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:

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!

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
5 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Contest starts in 30 minutes.

→ Reply
»
5 months ago, hide # |
← Rev. 2  
Vote: I like it -7 Vote: I do not like it

Contest Start Time is extended by 15 minutes ?

→ Reply
»
5 months ago, hide # |
 
Vote: I like it +10 Vote: I do not like it

I have a question regarding the problem VTAR .

What would be the answer for this testcase:

1
10 1
1 -1 -1 2 2 3 3 -1 4 4
My Understanding:

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.

→ Reply
  • »
    »
    5 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      5 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Thanks for the kind information. But, If u could also share, what would be the correct approach to the problem?

      → Reply
      • »
        »
        »
        »
        5 months ago, hide # ^ |
         
        Vote: I like it +1 Vote: I do not like it

        I couldn't come up with a proper solution, unfortunately :|

        → Reply
  • »
    »
    5 months ago, hide # ^ |
    ← Rev. 3  
    Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
5 months ago, hide # |
← Rev. 6  
Vote: I like it +1 Vote: I do not like it

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:

  • When observed, some new elements in the original array would have moved outside the first interval, I mean to say,the elements from (endpoint [goodidx[L-1]] to endpoint[goodidx[L]])
  • These newly moved out elements only would affect the good subsegment. (reduce the good subsegment size)
  • Meaning, if our subsegment of good indices (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).
  • These newly moved out elements (bad elements outside first interval) corrsesponding mapped starting positions can be found out, and those good index pairs < starting positions only satisfy, and our R pointer of our 2 pointer approach can be moved accordingly.

  • 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]] to endpoint[goodidx[L]]) , by amortized, the time complexity is $$$ O(N log N) $$$

→ Reply