antontrygubO_o's blog

By antontrygubO_o, 4 months ago, In English

We invite you to participate in CodeChef’s January Lunchtime, this Saturday; 29th January from 8:00 PM — 11:00PM IST.

The contest will be 3 hours long. There will be 5 problems in Div 1/2 and 6 problems in Div 3. It will be rated for all three Divisions.

Joining us on the problem setting panel are:

The video editorials of the problems will be available on our YouTube channel as soon as the contest ends. Subscribe to get notifications about our new editorials.

Problem Submission: If you have original problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.

Prizes:

  • The top 10 Global Division 1 users will get $100 each.
  • The top 100 Indian Division 1 will get Amazon Vouchers worth Rs. 1500 each.

Good luck and have fun!

P.S. I think that problems are interesting, I encourage everyone to try them!

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

»
4 months ago, # |
Rev. 2   Vote: I like it -11 Vote: I do not like it

Permutation chef

»
4 months ago, # |
  Vote: I like it +28 Vote: I do not like it
Meme
»
4 months ago, # |
  Vote: I like it +28 Vote: I do not like it

I am too buggy today

»
4 months ago, # |
  Vote: I like it +8 Vote: I do not like it

For PERMDEL is this on the right track?

We can only delete from the first or last two remaining positions of an array. This gives rise to the obvious $$$O(n ^ 4)$$$ dp (left extra, left end, right end, right extra).

We can optimize $$$O(n ^ 4)$$$ to $$$O(n ^ 3)$$$ by realizing the two can only interfere when there are 4 or fewer elements remaining, so something like (left extra, left endpoint, right extra) where the implied right end point is left endpoint + 1.

But I'm not sure how to proceed after that. I suspect it will involve independantly calculating (left extra, left endpoint) and (right endpoint, right extra) then iterating over all (i, i + 1) and merging it.

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    Yep that's almost it. But the iterating & merging part is a little tricky.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

    My solution had used most of these ideas.

    I solved it by fixing the middle element of the last 3 remaining elements, then counting the ways to remove the left part and right part separately (later multiply by a single binomial coefficient to account for permutations among the left and right operations).

    Counting the left and right parts themselves needed some DP and segment tree ideas.

    Unfortunately, there were some issues in my implementation during contest, which I fixed later. Really liked the problem though.

»
4 months ago, # |
  Vote: I like it +3 Vote: I do not like it

how to do think of permutation xor solution i tried n*(n+1) and alot of pairs xor kind of thing like 1 to n n,2 to n-1... plz tell solution?????

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My solution:

    First, find the nearest $$$k$$$ such that $$$2^k\leq n$$$, and then start taking XORs of pairs of the form $$$(2^k,2^k-1), (2^k+1,2^k-2), ..., (2^k+len, 2^k-len-1)$$$, where $$$(2^k+len)$$$ is equal to $$$n$$$.

    For each collection of $$$2*(len+1)$$$ pairs, the answer would be $$$2*[(2^{k+1}-1)*(len+1)]$$$. This would calculate the answer for pairings for values upto $$$(2^k-len-1)$$$, so we now calculate the answer for $$$n=(2^k-len-2)$$$ iteratively as long as $$$(n>0)$$$.

    It may happen, that $$$(2^k-len-1)$$$ is $$$0$$$ (only when $$$n$$$ is odd), so the answer for this case would be $$$2*[(2^{k+1}-1)*(len+1)-1]$$$ for the last iteration to eliminate the pairs $$$(n,0)$$$ and $$$(0,n)$$$, and instead pair up $$$(n,n)$$$.

    Link to my submission (I've tried to add explanations)

»
4 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Circular Permutation Recovery seems like just an easier IOI 2020 plants

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    You are right, I am really sorry for that. Seems like all admins have to go over all IOI problems...

»
4 months ago, # |
  Vote: I like it +8 Vote: I do not like it

CodeChef_admin Earlier there used to be 3 rated contests for Div1 users and now only two are being conducted in a month. Instead of organizing 6-7 contests for div2/div3 users, you can reduce it to 4-5 div2/div3 contests and make one contest rated for div1 users. Or even if it's not feasible then cook-off and lunchtime should have 15 days gap in between so that div1 users can have 1 contest in two weeks.

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    Instead of organizing 6-7 contests for div2/div3 users, you can reduce it to 4-5 div2/div3 contests and make one contest rated for div1 users.

    Reducing the number of Div2/Div3s will likely do nothing to improve the availability of Medium / Medium-Hard problems required for Div1 rated rounds, propose good quality difficult problems (or get others to do so) if you want more Div1 rounds.

    Also as far as I remember, the last time there were 3 rated rounds in a month was when Long Challenges were rated for Div1 and I don't believe the quality of those educational problems can be compared to Cookoff / Lunchtime problems.

    Or even if it's not feasible then cook-off and lunchtime should have 15 days gap in between so that div1 users can have 1 contest in two weeks.

    As far as I know the current layout is a remnant of the long challenges taking up the first two weekends of the month. With the two "mini challenges" currently being held on different weekends right now, swapping Cookoff to the 2nd weekend of the month would probably make stuff better.

»
4 months ago, # |
  Vote: I like it +12 Vote: I do not like it

What was the approach for Circular Permutation Recovery ( CIRCPRMRCVRY ) ? There is neither an editorial or a video solution for this problem.

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it +33 Vote: I do not like it

    My solution:

    Let's first look at the solution worth $$$50$$$ points. Do the following $$$n$$$ times, to assign positions to numbers from $$$1$$$ to $$$n$$$: Find a zero in the array, which doesn't have any other zero among the $$$k$$$ places to its left. Assign the $$$i$$$th number to this position in the answer. Subtract the values at the $$$k$$$ places to its left by $$$1$$$ and set the value at this position to infinity. If at any point there are no zeroes in the array, then output $$$-1$$$. Otherwise, output the final answer array. Try to see why this works.

    There are a few more observations needed to get $$$100$$$ points. Firstly, observe that if any value turns negative during the process, then there is clearly no answer as this value will never reach zero. So, zeroes, if they exist will have to be the minimum values in the array.

    For a moment, ignore the fact that if there are multiple zeroes, then you have to give preference to the zero which doesn't have another zero in the $$$k$$$ values to its left. We will tackle that later. Say you just want to find a zero. Then, you can just find the index of minimum value in the array and check if that is a zero. Updating the preceding $$$k$$$ values can simply be thought of as one or two range updates.

    This problem can be solved by using a min segment tree with lazy updates. Just build the segment tree over pairs $$$(\text{value}, \text{index})$$$ to retrieve the index of the minimum.

    Now, to tackle the part about choosing a particular zero if there are multiple zeroes. This part needs a final observation, why do we have $$$n \leq 2k-1$$$? Say a index $$$i$$$ dominates index $$$j$$$ if $$$i$$$ is among the $$$k$$$ indices to the left of index $$$j$$$. The condition $$$n \leq 2k-1$$$ means that for any two indices $$$i$$$ and $$$j$$$, either $$$i$$$ dominates $$$j$$$ or $$$j$$$ dominates $$$i$$$ (or both). Also, note that among multiple zeroes, we always have to choose the zero which is not dominated by any index.

    This can be achieved simply by tweaking the comparator of the pairs $$$(value, index)$$$. If the values are same, then compare the index which dominates the other index as lesser (if both dominate each other, then it doesn't matter). This comparator has the property that whenever a solution exists, the index returned by the segment tree would surely be a valid index.

    PS: Pretty problem.

»
3 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

When will the prizes be given out? CodeChef_admin