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 to get a wrong answer on the testcase2. Then I thought and modified the third condition.

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. If there are n consecutive B's then there should be greater than equal to n consecutive A's before them.

This came from a thought that I might do some grouping in the string so that the substring that is grouped can be made using the good strings. 

Like AABAAAABBBAB can be grouped as (AAB) (AAAABBB) (AB).

But turns out in some cases even if a group is not formable from the good string then it can be formed by the good string if grouped along with the previous or the next group. 

Like AABAABBB although its grouping can be like (AAB)(AABBB) where the last group is non formable but it can be formed from (AABAABBB).

So an hour more and I was exhausted. So I took a hint and was finally able to find a great way to deal with this question. My grouping method was somewhat similar to that but complicated. 

The problem can be solved by assuming that A and B are nothing but open bracket ( and closed bracket ), deal it like a problem to check if a given bracket string is valid or not. But just with a condition that every ) should have a corresponding ( but every ( might not necessarily have a corresponding ).

I liked this a lot!

MORAL: Analogies can be made with the things that you have already studied.

Bye. Cheers!


Comments

Post a Comment

Popular posts from this blog

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