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:
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.
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:
No comments:
Post a Comment