satyam343's blog

Invitation to CodeChef Starters 144(Rated for All) — 24th July
By satyam343, 7 weeks ago, In English

We invite you to participate in CodeChef’s Starters144, this Wednesday, 24th July.

It will be rated for all and is my last contest as contest admin.

Time: 8:00 PM — 10:00 PM IST

Joining us on the problem setting panel are:

On the difficulty

The Division 1 problemset features problems with difficulties from div2A to div1E. We expect the contest to be interesting enough for LGMs as well.

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
  • +143
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

finally satyam343 round

→ Reply
»
7 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

Counting is fun once again !

→ Reply
»
7 weeks ago, # |
  Vote: I like it +21 Vote: I do not like it

satyam343 Orz

→ Reply
»
7 weeks ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

try to make it more balanced. Last few contests there is huge gap between the difficulty level of 2nd and 3rd question.

→ Reply
»
7 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

OMG ORZ satyam343 I AM YOUR BIGGEST FAN

→ Reply
»
7 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

satyam343 orz

→ Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Yayy!! rated for all :)

→ Reply
»
7 weeks ago, # |
  Vote: I like it +52 Vote: I do not like it

→ Reply
»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Orz satyam343

→ Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Hey, for the sake of humanity, please stop providing solutions to the cheaters.

    → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

satyam343 orz

→ Reply
»
6 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

As a div1 participant, why am i restricted from the contest?

→ Reply
»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Remainder: Contest starts in less than 60 minutes.

→ Reply
»
6 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

MINIMISEINV is a repeated problem from codechef,if you google the problem statement ,you will reach the editorial here . What's even more funny and shocking is that satyam343 tested this problem and provided the solution as seen in the editorial page.

Nice last contest.

→ Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    this question unrated then?

    → Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Bruh,

    The contest should definitely be unrated then.

    → Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is indeed funny, I did not remember it.

    Nice last contest.. Just to be clear it was my last contest on CodeChef (:

    → Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Previous problem needs O(n) time complexity but today's problem intended solution is O(n*k). So easier and harder version of same problem based on constraints.

    → Reply
»
6 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

//

→ Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    that's $$$O(n^3)$$$ as $$$n * ones * (n - ones)$$$ is of the order $$$n^3$$$

    → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

in minimum inversion problem why it's not optimal to make some prefix $$$000...$$$ and suffix $$$...111$$$

→ Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is optimal, you just have to determine how long of a prefix to set to $$$000...$$$ and how long of a suffix to set to $$$111...$$$. You can do this by brute forcing it in $$$O(n^2)$$$.

    → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i tried both $$$O(n)$$$ and $$$O(n^2)$$$ both gave WA2 is there any edge case?

      → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

in the problem Minimise Inversions, I did remove the leading zeros and trailing ones

then count the number of 0's and 1's in the remaining string

if the number of 0's is greater than 1's, then I will flip the first K ones

else, I will flip the last K zeros

does anyone have a test case which my approach doesn't work with it ?

I made this approach, but gives me WA on test 2 :(

→ Reply
»
6 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

"interesting enough for LGMs as well" should not mean there is a tedious problem and the contest duration is too short, I suppose.

I'm so poor to able to read only 4 problems, sorry. CNTISFN343 is nice though, thanks!

→ Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    there is a tedious problem

    I assume you are referring to TREESAREFUN.

    I used euler tour to count the number of intersecting pairs. I really liked the idea. So I discussed it with one of the testers. He liked it too.

    I didn't find the implementation tedious, although it is a bit tricky. The tester had a similar implementation, so I didn't get the impression that it's a tedious problem.

    Here is my implementation for reference.

    I thought BANGER was pretty nice too. That is why I thought the contest should be interesting for LGMs.

    I should have kept the contest to be of 150 minutes though.

    Glad that you liked CNTISFN343.

    → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you describe the solution for problem BANGER?

      → Reply
      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it +15 Vote: I do not like it

        All editorials of CodeChef can be found at https://discuss.codechef.com/c/editorial/5. This is totally free of charge. The only part that is premium is the fact they appear directly on the problem page.

        → Reply
      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        Let us see how to find $$$Score(b)$$$ quickly.

        We can see that optimal $$$c$$$ should be $$$[1, 1, \ldots 1, 2, 3, \ldots k]$$$.

        Now there should an index $$$i$$$ such that $$$c_i = b_i$$$. Otherwise $$$[1, 1, \ldots 1, 2, 3, \ldots k+1]$$$ could have been a valid $$$c$$$ too. Now it is clear that we only care the largest index $$$i$$$ such that $$$c_i = b_i$$$. So the number of distinct elements in this case is $$$b_i + m - i$$$.

        This leads us to the observation that $$$Score(b) = m - \max(0, \max_{i=1}^{|b|} i-b_i)$$$.

        Now we have to solve original problem.

        Let us just have an array $$$d$$$ such that $$$d_i = \max(0, i-a_i)$$$.

        Suppose $$$l_i = \max_{p=1}^{i} d_i$$$.

        Now if $$$Score(a[j,i])$$$ is.
        1. $$$i-j+1$$$ if $$$l_i < j$$$.
        2. $$$i-l_i$$$ if $$$l_i \ge j_i$$$.

        $$$l_{i+1} = \max(l_i,d_{i+1})$$$.

        So we can see that we just care about how array $$$l$$$ looks after each update.

        Let's divide the array $$$d$$$ into $$$sqrt(n)$$$ blocks.

        Say we are in some block, and it covers indices from $$$x$$$ to $$$y$$$. After the update, either $$$l_i$$$ $$$x \le i \le y$$$, will be changed to $$$l_{x-1}$$$, other there will be an index $$$z$$$ such that all $$$l_i$$$ $$$x \le i \le z$$$ will be changed to $$$l_{x-1}$$$, and subarray $$$l[z+1,y]$$$ will be unchanged.

        So we can update the answer for each block in $$$O(t)$$$, where $$$O(t)$$$ is the time taken to find the smallest index $$$v$$$ greater than $$$x-1$$$ such that $$$d_v > l_{x-1}$$$. In editorial mentioned above, editorialist described the $$$O(logn)$$$ way to find $$$v$$$.

        It is possible to find $$$v$$$ in $$$O(1)$$$. It is possible to have a ds which supports update in $$$O(sqrtn)$$$ and query in $$$O(1)$$$.

        Now only one thing is left.

        How to find $$$\sum_{i=x}^{z} \sum_{j=1}^{i} Score(a[j,i])$$$, given that $$$l_x = l_{x+1} \ldots l_y$$$. It can be found in $$$O(1)$$$.

        Here is my $$$O(n sqrt(n))$$$ implementation for reference.

        → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Thanks for the comment. Yes, about TREESAREFUN for me.

      The word "tedious" might not for suitable for what I meant, sorry, but I meant the total work needed for AC instead of the final code length. Maybe I should have said just time-consuming (comparing with the time to feel it is solvable in $$$O(N \cdot \mathrm{poly}(\log(N)))$$$ time). I finished implementing and I guess mine is not too far from yours.

      Most importantly, the solution involves some amount of case work (right?) while the sample output is essentially $$$0,0,0,1$$$, so we normally have a tough debugging time.

      Having weak samples is an option but in that way I guess 150 minutes were just about right for the first 6 problems (considering the speed of today's top participants).

      → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

after how much time rank gets updated?

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Largest K if it was of subsegment instead of subsequence.

→ Reply
»
6 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Why my strategy for MINIMISEINV is wrong.

I am trying to calcuate flipping which number will most optimal each time (by checking the delta for each char).

Code
→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve "minimum inversion" problem if it is mentioned exactly k flip need to be done?

→ Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We do exactly k flips only in cases where our suffix array is constant(from n-1 to 1) and same when our prefix array is increasing ,so I think we can maintain another array temp to store indices where increment occurs according to same logic as at most k and just count and if index<k then return 0.

    → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

getting wrong answer in Minimise Inversions code why getting wrong answer

→ Reply