satyam343's blog

Invitation to CodeChef Starters 104 (Rated till 6-stars) — 18th October
By satyam343, 7 months ago, In English

We invite you to participate in CodeChef’s Starters 104, this Wednesday, 18th October, rated till 6-stars (ie. for users with rating < 2500).

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

Read about the recent judge migration here.

Joining us on the problem setting panel are:

Additional Note about the contest:

  • All the tasks of the Div 1 problemset are authored by Satyam satyam343 Kumar Roy

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

»
7 months ago, # |
  Vote: I like it -61 Vote: I do not like it

is it rated?

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

satyam343 orz

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

satyam343 orz

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

I hope you liked the problems!
Congratulations to Alpha_Q for AKing Div 1.

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

Here is how I solved all problems except COMBIISFUN

→ Reply
  • »
    »
    7 months ago, # ^ |
    ← Rev. 3   Vote: I like it +11 Vote: I do not like it

    For D1E, I had a completely different solution than yours, so just briefing it here as an alternative.

    1. I processed the array considering every suffix, i.e., I used the the answer for suffix[i + 1, n] to find answer for suffix[i, n].

    2. The only new element we have in suffix[i, n] is a[i]. If a[i] is 0, then we can prepend it in every LNDS for subarrays in suffix[i + 1, n] which starts at i + 1, in short every LNDS increases by 1, so ans[i, n] = ans[i + 1, n] + (n - i).

    3. If a[i] is 1, then we can observe that it will increase LNDS only till those indices j > i, such that zeroes(i, j) <= ones(i, j). This means, if we make prefix sums, considering 0 as -1 and 1 as +1, then we have to just find the next smaller/equal prefix value after i. Let's say there are k such indices, so ans[i, n] = ans[i + 1, n] + k. I used sparse table and binary search for this in contest, however later I realized I can just use stack (the author).

    4. In the end, we have to sum up answer for all ans[i, n], 0 <= i < n. Complexity O(n).

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

      If my subarray from $$$[i+1,j]$$$ is $$$[0,0,0,1,1,1,1]$$$, then LNDS $$$[i+1,j] = 7$$$, also zeros $$$[i+1,j] \le$$$ ones $$$[i+1,j]$$$, however, if $$$a[i] = 1$$$, then LNDS $$$[i,j]$$$ still remains $$$7$$$ (not increased by $$$1$$$)? Can you elaborate your claim?

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

Please explain this https://www.codechef.com/problems/LEXILARGEST

→ Reply