Invitation to CodeChef Starters 110 (Rated till 5-stars) — 29th November
We invite you to participate in CodeChef’s Starters 110, aka Shaastra Programming Contest , conducted by Shaastra IIT Madras and sponsored by KLA+, this Wednesday, 29th November, rated till 5-stars (ie. for users with rating < 2200).
Time: 8:00 PM — 10:00 PM IST
Register here to be eligible for the offline finals where there are prizes worth 60000 INR.
Joining us on the problem setting panel are:
- Setters: Ashwin Subramanian Alpha_Ashwin007 Murugan, Shanmukh Raj Scintillator_Sha MSS, Patibandla akshitha_175 Akshitha, Kunal KG26 Agrawal
- Tester: Shreyan Dominater069 Ray
- Text Editorialists: Nishank IceKnight1093 Suresh
- Statement Verifier: Nishank IceKnight1093 Suresh
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!
what is error in this https://www.codechef.com/viewsolution/1032623090 for Tom and jerry problem
I know i am using n*n time so it should give TLE But it gave WA
In the problem "World Cup", any pointers as to why the following idea doesn't work?
Since:
$$$y$$$ clearly depends on selecting all matches with length $$$\lt y$$$.
For a fixed $$$y$$$ and |S|, we want to maximize $$$\sum_{x \in S}{h_x}$$$ by picking the largest remaining possible values.
From (1) and (2), any optimal set of matches consists of a combination of the $$$i$$$ shortest matches and the $$$j$$$ longest matches.
So we can just iterate over the values of $$$i$$$ and $$$j$$$ and find the minimum value of $$$i + j$$$ which satisfies $$$(i + j + 1) \cdot a_{i + 1} - 1 + \sum_{x = 1}^{i}{h_i} + \sum_{x = 0}^{j - 1}{h_{n - j}} \geq H$$$.
I feel like I'm misunderstanding something key about the problem or approach.
For a short while, this was the intended solution. But it doesn't work since "the j largest matches" have to satisfy another constraint, which is that the sum of all the chosen h_i should be <= H. Surprisingly, this throws a huge spanner in the works, and it is actually not true that the optimal set is a combination of some shortest and some longest matches.
Also, why the "- 1" in the LHS?
Ah, got it. If I have h = [1, 1, 3, 9, 10] and H = 15, the only optimal choice of matches is $$$[3, 10]$$$.
Regarding the "-1", when considering the $$$|S| + 1$$$ gaps around the $$$S$$$ elements, keep in mind we can only make the gap as large as $$$y - \epsilon$$$, so the total integer length we can cover is $$$(|S| + 1 \cdot y) - 1$$$, right?
The answer to this given test case should be $$$2$$$, my Greedy solution is also giving $$$2$$$ as the answer, but I am getting WA.
Can you please tell the test case where I am getting wrong, or could point out mistake in my code.
Yup, precisely. In fact, slightly generalizing the example you've given, if you have a bunch of 1s, then the problem effectively becomes a Subset Sum problem on the other elements (hand-waving a lot), which is of course NP-Complete.
Regarding the -1. Yeah, my bad. Misread your inequality as strict.
i was also doing the same now I realised why it would not work. Can u explain the sol for this problem?
https://discuss.codechef.com/t/spcp8-editorial/114415
Why in the world a $$$dp[N][2][2]$$$ solution gives TLE in tetris?
You must be re-evaluating the $$$dp$$$ array inside every test case. But the answers from previous test cases can also be used.
So just don't make the $$$dp$$$ array filled with $$$-1$$$ for every test case.
My Submission
I tried that , but instead of last as 1 to 4 , i took it as boolean if last = 4 or not,there not re-initializing my dp gave WA.
There is no constraint on $$$\sum {N}$$$ over all test cases.
At least for my $$$dp[N][2]$$$ state (lines filled, cur player), the answer is just the sum of the states $$${[L - 4][0], [L - 3][0], [L - 2][0], [L - 1][0]}$$$. So just precalculating up to $$$10^5$$$ (the max possible value of $$$k$$$) solves the issue.
Cant understand why this is wrong . please help ! https://www.codechef.com/viewsolution/1032506038
for a = 9 and b = 5 you will output 3 but the answer is 2 9 — 2 -> 7 5 + 2 -> 7 The transfer can take both ways.
Thanks! got it