Codeforces Round #543 F(Div2) (Compress String)

Hi Everyone,

Writing a post after long time, encountered a nice question this week and thought of writing a post about it. Here it goes:

Problem Statement:
Given a string S, you need to encode it such that cost of encoding (definer later) is minimum. Cost of encoding is defined in below two ways assuming our S is encoded into k substrings (t1_t2_t3_t4__tk).
1. Cost is A if |ti| = 1
2. Cost is B if |ti| > 1, you can only do this if "ti" is substring of "t1_t2_t(i-1)".
For more understanding please look at : https://codeforces.com/contest/1121/problem/F

My Approach:
I started from how to build encoded string. If we observe that first substring "t1" must have length 1 because there is no "t0". Thus for first substring we need to pay A amount.
Now what happens after "t1", we have some subtring "t1_t(i-1)" when we are choosing ith substring, what would be best case scenario here? If length of our "ti" is maximum, that is best deal we can get by giving amount B, now how to find maximum length of substring which we can add using B amount of money? Let's try to observe:
We had "t1_t2_t3_t(i-1)" and we need "ti", if we try to come back to string S, we are at some index "idx" and want to find max "j" such that substring of S from (idx to j) is already present in substring of S(0 to idx-1). Basically we need to find S(idx to endOfString) in S(0 to idx-1) and if it's not present, find maximum match which was there. This can be done very easily in O(n^2) for every index. But we need to do better as O(n^2) for every index will become O(n^3) and will give TLE.
Is it somewhat similar to finding if a string exists in another string? We need to find S(idx to endOfString) maximum prefix present in S(0 to idx-1). So if we perform same KMP here and find out the maximum length of prefix present in S(0 to idx-1), we will know what maximum length we can have for "ti".
But still we have two options:
1. Add all these characters one by one using A amount every time.
2. Add all of these in one go spending B amount once.

So depending on what is minimum we should choose our option.

How to Implement:
We can maintain a simple 2-D DP having two values for every index, first will be answer if we chose A amount to add this character and further solved for next indices, second will be if we chose B amount to add maximum length substring which we can add and then solved further.

Implementation:

Let me know if there is any mistake in the post or anything is not clear. Thanks for reading.

Setting up Sublime Text in Windows 10 for Competitive Programming in C++

Hi, I switched from ubuntu to Windows recently and found it really tough to get some simple document stating "How to setup sublime for C++ in Windows 10". Somehow I successfully did it after so many trials and thus I have decided to document it myself.

1. First of all you need to download MinGW compiler for windows as it doesn't come with C++ compiler like ubuntu. You can go to MinGW website and download it. I have also shared it on my google drive and you can go and download it from there. All following steps will be as per version I have shared in my drive. There may be little changes in latest versions so you can explore and figure them out. Google Drive Link for MinGW
2. After download is successful, extract this file in one of folder e.g. I have done that in C:\ drive. Also I have named this as MinGW. So path in case of my computer is C:\MinGW
   
3. Now you need to add environment variable for this. Click on start and type Environment Variable, you will get "Edit the system environments variables", click on that.
4. Go to Advanced>Environment Variable, and click on it. You will see all environment variables present in your system. Click on New
5. Now you need to add g++.exe path from MinGW folder. Usually that is present in bin folder under MinGW i.e. for me it is C:\MinGW\bin\g++.exe . Put this in variable value and save it.
   
6. Now your windows is set up with C++ compiler. Now go to Sublime Text for further settings.
7. Open "Tools>Build System>New Build System". 
   
8. Copy and paste below content in build and save it with some name such as "my_cpp_build". Just make sure to change 'path' to your system's path. I have set it as mine PC's path.
9. As you can see in above file. I have set input file name as 'inputf.in' and output file as 'outputf.in'. Please make sure that you have these files in folder where your cpp file is present for which you want to compile and see output giving some input. Use 'Ctrl + B' for build and run.

With above 9 steps you should be all ready for coding in C++. Please feel free to comment if you have any doubts regarding this. Happy Coding.

Codeforces Round #505 C : Plasticine zebra

Hi Everyone, today we will be discussing Problem C of recently concluded Codeforces #505 (Div1 + Div2) contest. I couldn't get idea behind this during contest but then solved it after the contest.

Problem Statement:
You are given a string containing two types of characters 'b' and 'w'. Your task is to modify string is such a way that it contains longest substring having alternate characters (let's refer it as zebra length). Modification can be done by one step, which is to cut string in two halfs (possibly zero length for one of half) and merge them again after reversing both the halfs. You can access problem at http://codeforces.com/contest/1025/problem/C

My Approach:
Initially I though it will have lot of corner cases as we can cut string from any place and transformed string again may be cut at any place. We can't be concrete about what index's cut on or what order of cuts will give us maximum zebra length.
But if you imagine this closely, what exactly are we doing in modification each time? We are cutting some point, and then merging after reversal of both parts, right? So basically only way answer can be increased from this first modification is if first character and last character (which will be together now) are alternate and they make a larger zebra length. Now if you do modification again, will it change anything? As per me, no. That's because now first and last were together before last step and if this could result in better zebra length, then it can't be more than original string.
One more way to analyze is to see that we are not changing anything if we take string as circular. We cur at some point in circle, reverse it (doesn't make any sense to reverse a line if you have to join it in end) and join it. So in short, zebra length remains same for circular string with same operation.

How to Implement:
We can simply append current string with same string and check for longest zebra length in this string. But this has a corner case. Suppose string given is already zebra length of even length, in this case circular will have 2*length as zebra length which can't be true if maximum can be equal to length. So we need to take care of this separately.

Implementation:
Please feel free to drop a comment if you have any doubts.

Codeforces Round #505 A (Doggo Recoloring) and #505 B (Weakened Common Divisor)

Hi Everyone,

I have decided not to make different editorial for every problem of a single contest. From now on, I will be writing solution for problems which I could solve in contest in a single post (mostly next day if time allows :P ) . Other solutions I will be uploading after upsolving.

So today we will be going through two problems of yesterday's contest, A and B. Here it goes:

Problem A: Doggo Recoloring

Link: https://codeforces.com/contest/1025/problem/A

Statement: 

Basically problem gives us a string having all lowercase Latin characters and allows us to do one type of operation say "OP1". We can perform "OP1" any number of times. We are asked to check if we can get a string having all equal character after some number of "OP1". 

Operation OP1 is given as: Choose a character having more than two occurrences and replace all these with some random lowercase character x. 

My Approach:

Idea to solution was simple but good one. Basically condition for "OP1" is to have at least two equal characters. Now assume we have a character which is there for greater than or equal to 2 (>=2) times. Just start processing from this character, take this up and convert it to some character having any number of occurrence (>=1) in string. What will happen now? See that count of character in which you transformed is now changed from earlier (>=1) to (>=1+count of changed charater). So it will surely be greater than 2 and you can perform your operation on this character. Thus we can see that this process can continue until all the characters are equal. 

Thus a solution always exist when some characters have a count more than 2 and doesn't exist otherwise. BUT one corner case for non-existence would be when string has length of one. See that we have no character having length greater than one but string already has all same characters.

I hope my code resolves other doubts.

Implementation:

Problem B: Weakened Common Divisor:

This was quite good for a B problem as far as relative to contests I have given. I tried to find some simple solution even after getting a little 'tough to implement' approach but had to go with tough one only in the end. That's why code is little ugly but I will try to explain it as good as possible from my side.

Link: https://codeforces.com/contest/1025/problem/B

Statement:
Quite simple statement. You were given n number of integer pairs and were needed to find some integer (greater than 1) which divides at least one element in every pair.

My Approach:
Ultimately we need to find an integer, say 'x' which divides at least one element of every pair. What does this imply? Can we say that it will surely divide one of elements from first pair too? Yes? So whatever be out answer, it will divide either of (A1,B1) assuming (Ai,Bi) is ith pair. Now if a number say y, divides A1, it can be prime factor of A1 because if it's not (y*z), it won't help us in any way, because it can only reduce chances of dividing other pairs' elements. Why? Take it as a task :p .
So we can conclude that our answer y will always be one of prime factor of A1 or B1. Now once we get all prime factors of these two numbers, we can iterate over all the pairs and find which one is the answer.

Why this won't result in TLE?
Maximum number of distinct prime factors for number upto 2e9 is 10. Now even if we have distinct for both A1 and B1, we will have max of 20 distinct candidates for answer. Now for going to all numbers it will take O(n) time, resulting in maximum O(20*n) for checking. But we also need to calculate distinct prime factors for A1, B1. We can do that using pre-calculation of all prime numbers upto sqrt(2e9) and then dividing every number from continuous prime numbers until it becomes one of it becomes a prime number.
You can find prime factors by any other efficient way you are comfortable with. Some of them are discussed here: Find Prime Factors Efficiently

I hope you will be able to understand from code better (Other than calculating prime factors, please refer to any way you are comfortable with for finding out prime factors).

Implementation:

I hope you liked the solutions. Please feel free to drop a comment in case of any doubts.

Codeforces Round #504 A : Single Wildcard Pattern Matching

Hi Everyone,

This time I will be discussing problem A from yesterday's contest CF #504. It has quite a lot corner cases and that resulted in less AC submission than B and C of same contest. Let's cover them all.

Problem Link:
http://codeforces.com/contest/1023/problem/A

Problem Statement:
We are given two strings "S" and "T" of length "n" and "m" respectively. Ask is to transform "S" into "T" by inserting any string into "S" in place of a character '*' if and only if '*' is present.

My Approach:
Initially this seems that we need to tackle lot of corner cases as '*' may be present in start, end, middle, or not present at all in string "S". So I decided to tackle them one by one initially but at later point I thought we can keep two pointers in "T", one in start and one in end, and compare them with "S" through doing appropriate increment, decrements. I will explain how:

• Case 1: When no '*' is present. You can simply check if two strings are equal and return answer. This was reason of many WA on #71 test case, in which no '*' was present and thus if you check thinking '*' is always there, you will get WA. Test case was: S="a", T="a"
• Case 2: Length of "S" - 1 (n-1) is greater than Length of "T" (m). This will always give us "NO" because we can't insert anything in "S" to make it "T" as length of "S" is already greater than "T".
• All other Cases: Now we are sure that '*' is present in "S". Let's keep one pointer start pointing to initial position in "T", now we can check by moving forward in both "S" and "T" till we encounter '*', all characters should exactly match till '*' other wise we won't be able to make "T" from "S" as we can only insert new character in '*' place, we can't remove a character which mismatched before '*'. See image below to get more insight. Once we encounter a '*' in "S", we keep position of start stored. Now let's take another pointer end which points to last index in "T", again we will come backward in both "S" and "T" until '*' and check for every index's validity. Now at point of again encountering '*', we need to check for only one validity, which is [start<=end]. Why? Because it means that we have matched in "T" until an index start from starting and an index end from ending. Thus we can insert T[start+1, end-1] in S['*'] and "S" will match to "T".

Why it doesn't work in case of mismatch:

It is little hard to explain very clearly but I hope code will resolve some more doubts. I have commented it as well as I could.

Implementation:

I hope this editorial has helped a little. In case you have any doubts, please feel free to drop a comment. Have a Good Day!

Codeforces Round #504 C : Bracket Subsequence

Hi Everyone,

I will be discussing one of problem from yesterday's contest CF #504.
You can access problem at http://codeforces.com/contest/1023/problem/C

Problem Statement:
Given a regular bracket sequence "S" of length "n", find another regular bracket sequence "T" having length "k" such that "T" is sub sequence of "S". Also "n" is strictly greater than "k".

Constraints:
2<=k<=n<=200000

Approach:
Basically we need to take out some of characters from "S" such that it remains regular bracket and meanwhile length reduces to k. Thus we need to remove [(n-k)/2] pairs of [()] from "S" to make a valid "T".
I decided to make a stack of characters and processed "S" keeping count of remaining pairs which we need to remove. So if at any point we encounter "(" in "S", we can simply put it in stack while if we encounter ")", we can be sure that current top of stack is "(". Thus we can pop that character from stack, ignore current ")" and continue as if we didn't have this "()" pair at all. This reduces our remaining variable by 1.
Gradually we will remove all required pairs. Now we will have some elements in stack which will be all "(". Thus we need to have a string will same number of "(" as size of stack. All other elements in out answer string will be remaining character of "S".

Implementation:

I hope code helps in clearing further doubts. Please feel free to drop a comment in case you are not able to understand approach.

Codeforces Round #151 D : Colorful Graph

Hi All,

I will be providing editorial for one of the problem from CF #151 today.
Link of Problem: http://codeforces.com/contest/246/problem/D

Problem Statement: All the nodes are given some color between [1-1e5]. Our task is to find one color having maximum different kind of neighbors. As per my approach, I though of making a map of 100000 size. What we can do is that on getting every edge, if both vertex has different color, we can put this in our map.
Now as we want lexicographical smallest value of vertex having same cardinality, we traverse our map in sorted order of vertexes. We simple pick the one with highest cardinality and lowest vertex number.
Hope code will resolve doubts in case you have.
Implementation:
Feel free to comment in case you are not able to follow up.