Can someone explain approach of PRFCTN using stacks
Can you please tell me the solution of Perfection(PRFCTN)
1 Like
In the problem PIBRO the constraints mentioned clearly indicates an O(N) or O(NlogN) solution should work in the worst case, but my solution1 (in python), which is O(N^2) solution passes all the subtasks, the test cases gives an unfair advantage to the contestants with a brute-force solution as well.
3 Likes
disjoint set union
Div 2 Lunchtime was easy this time or is it just me?
1 Like
How did you use dsu?
Cannot figure out a test case that would give WA for APARTS problem solution. Need help: CodeChef: Practical coding for everyone
Someone help me out with planting trees. I got partial solution ( TLE ). With O(n) complexity.
https://www.codechef.com/viewsolution/28015723
I guess it’s due to the sort. Does it become O(n^2).
@admin please note that the pizza or broccoli question has very weak test cases(gets ac in O(N^2)). You should run additional test cases on that question and regenerate the ranklist it is very unfair for ppl to write a plain brute force for such a simple question and get it correct.
In line 38, j < n - 1 should have been j < m - 1.
1 Like
Can you show a brute force solution that passed all tests?
@anon4057137 many but the best would be you write one and see it pass yourself. You can also look at @sbh69840 solution which passed.
Here is another : CodeChef: Practical coding for everyone
1 Like
Can anybody tell the test case in which my solution of compress the list (CMPRSS) problem fails (Link below), I have got the AC verdict with different approach but want to know where this one fails, it passes all the test case assumed by me. Thanks in advance 
Well yes even my solution passed easily when the worst case is easily O(n^2)
https://www.codechef.com/viewsolution/28017156
1 Like
Can anybody tell the test case in which my solution of compress the list (CMPRSS) problem fails. Thanks in advance 
Can anybody tell the test case in which my solution of Planting Trees (DEADEND) problem fails. Thanks in advance
Hello guys can anyone help me with the compress the list problem, i can only figure out multiple if else solution.
Please check my code here: Coding Blocks IDE
Thanks in advance.
stacks was just to simplify my strategy yeah but the idea was to devise a strategy in my case i observed the first number which is less that its previous. As you can only reduce the number and not increase it so if the arr[0] was less than any arr[i] i>0 then we had to reduce arr[0] to that arr[i] finally,so we consider all number greater than arr[0] and keep putting them on the stack when we get an i such that arr[i] < stacktop we know that the previous value which is greater than this have to be reduced to this so for all j<i j in stack where arr[i]<j we change those value to arr[i] val and increase count now and remove these from stack as they have been processed and made into arr[i]. Go on this way .
try to iterate the logic for 1 2 4 5 3 12 you will get it,
like 1 2 4 5 3 12
applying the strategy here 3<5 && 3<4 so you need to change both 4&5 to 3 intially but 3>2 so once you changed 4 5 to 3 it becomes
1 2 4 5 3 12 → 1 2 4 3 3 12 → 1 2 3 3 3 12
now we see 2<3 so we need to get the 3s down to 2s we can do that in one step(this was the reason to convert 4 and 5 to 3 intially and not to 1 so as to do group them together and convert them to 2 this in 1 step)
1 2 3 3 3 12 → 1 2 2 2 2 12
carry on the same process for 1 and thats how the logic builds.
Here is the code to help you out its very straightforward and easy to understand. Important part was to proof that the strategy was right.
can anyone help me with compress the list (cmprss) question, sample test output is the same but on submitting it is wrong, I tried with StringBuilder also.
link: CodeChef: Practical coding for everyone