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:
Setters: Kanhaiya notsoloud1 Mohan, Satyam satyam343 Kumar Roy
Tester: Apoorv tyr0Whiz Kumar
Statement Verifier: Kanhaiya notsoloud1 Mohan
Text Editorialists: Nishank IceKnight1093 Suresh
Contest Admin: Satyam satyam343 Kumar Roy
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!
is it rated?
satyam343 orz
satyam343 orz
I hope you liked the problems!
Congratulations to Alpha_Q for AKing Div 1.
T H E K I N G
Here is how I solved all problems except COMBIISFUN
For D1E, I had a completely different solution than yours, so just briefing it here as an alternative.
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].
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).
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).In the end, we have to sum up answer for all ans[i, n], 0 <= i < n. Complexity O(n).
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?
Please explain this https://www.codechef.com/problems/LEXILARGEST