problem : http://www.codechef.com/COOK39/problems/PPLUCKY My idea :
If I get digit 4 , then this 4 will not effect any 7 before this position.
If currently i get 7 and i have one or more unused 4, then i will have a pair 47 in any iteration . Now, I have to find in which iteration i will get this pair.
I can get this iteration number greedly and can get total number of pair erased before this position using RMQ.
My implementations :
http://pastebin.com/7RBu4Gs5 1. http://www.codechef.com/viewsolution/2863273 2. http://www.codechef.com/viewsolution/2859710
No idea , why WA . Need critical input ........
Thanks in advance
I don't know how helpful this is to you, but I'm pretty sure your code gives WA on this test case: 1
183
47477747474747444447447777747474447474747777474444447 447474744747474747474747474777477474474747474747 4747474747474747474747474747474747444447777747474747474744747474747474444474774777
(I had to put the string on multiple lines because CF formatting)
As you give a different output than my AC code: http://www.codechef.com/viewsolution/2861034 Here's my code: http://ideone.com/M8inkK Here's your code: http://ideone.com/XyIoYh
Correct output should be 6857, while you print 6883. I couldn't really find any smaller cases that gave WA, sorry about that. Good luck debugging.
P.S. My solution relied on the fact that after simulating the first set of deletions, you will only need to check the numbers before and after the deletions, since they are the only ones affected. There are at most N/2 deletions, so this is a O(N) algorithm.
EDIT: Fixed spacing issues.
Thanks.