Day2

-

Monty and Ravioli both are home and I am here in hostel with Pulku. We went to the library for some work rushed back to have dinner coz we had a contest on codeforces today. My first contest on codeforces. Yes I am yet unrated. It started at 8:05PM IST, I spent the entire 2 hours on the question A. just because of a silly mistake.

 I did 1673A. on codeforces named "Subtle Substring Subtraction".

See I came up with the following three cases in a matter of 20 minutes:

1. Bob wins with string length 1.

2. Alice wins with even string length.

3. For odd string lengths Alice will remove (n-1) length of substring leaving the last or the first letter depending on the position of the letter with the max value in the string.

I implemented it, it worked on the given test cases but gave a wrong answer on the pretest2. And from here I was loitering to find the error. Which I couldn't. 

I also figured out that Bob will win ONLY with length 1 of the string and in all the other cases Alice will win. But the only thing that I did not realize is that the Alice's SCORE was also supposed to be optimized not just the gameplay was to be optimized to make her win.

So technically the third case will change as follows. 

1. Bob wins with string length 1.

2. Alice wins with even string length.

3. For odd string lengths Alice will remove (n-1) length of substring leaving the last or the first letter depending on the score that she will get on removing the substring. She will use a max operation on the score obtained from leaving the last and score form leaving the first letter and play accordingly.

MORAL: Check the optimization carefully.

Bye. Cheers!

Comments

Post a Comment

Popular posts from this blog

Day1

-
My uni's fourth semester is over and summer has started. I was all set for resuming my competitive programing (CP). I was discussing this with one of my closest hostel mates, Monty. He basically guided me for the initial steps. I would also give a detailed guide for the steps sometime later, if someone needs one from me, lmao. While we were discussing a friend of mine Ravioli also tagged along and wanted to resume her CP with me. So we technically started together from today. So the question we did was 1672B. on codeforces named "I love AAAB".  I spent 2 hours just figuring out the algo and implementing it on code. Initially I figured out 3 conditions for the string to give an output YES as: 1. The length should be greater than 1. 2. The first letter should not be B and the last letter should not be A. 3. There should not be any two consecutive B's Out of which first two conditions were correct but I had a feeling that the third one was wrong any way I implemented it ...
Read more

Day5

-
Started with debugging one of my yesterday's code of problem no. 1671A. from codeforces. One of the major learning from the past two days' problems is that never initiate the flag boolean in the starting of the code. It can be considerably harmful. Problem 1674D. of yesterday's contest was the one I solved after this. I got the logic correctly but the implementation of the logic is getting faulty somewhere. I am getting a wrong answer in one of the test cases on the preset 2. Which apparently I am not able to see.  I have tried changing the implementation 2 times, its been 3 hours now. So without wasting any more time I'll move ahead. Not much of learning done from today's question. But okay. Bye Cheers! 
Read more

Day3

-
 I just started on my own today. I did problem 1672A. on codeforces named "Log Chopping". See, the crux of the question was that the number of steps required to bring down all the logs to length 1, let that number be k. If k is even then maomao90 wins and if k is odd then errorgorn wins. Now the main task is that, given the length of all the logs we have to find the total number of steps to bring all of them down to length 1 each.  Initially  I used the following approach, We may find the log of maximum length and then find its steps of decomposition and that will be our answer coz it will take the maximum number of steps. So if the length of the log is n and n <= 2^k  (basically logarithm of n to the base 2) then k will be the number of steps to decompose that particular log. Implemented this to get wrong answer on the given test case. And immediately I caught the error. So basically for a log of length n the number of steps will not be counted using the logarith...
Read more