WPC #3 was held on this sunday. http://aca.cse.iitk.ac.in/public/
Problems have been moved to spoj.
Editorials: (these editorials are merely hints, You need to work things yourself for final answers)
Hope you will like them. Leave a comment if something is unclear or needs to be modified, Also leave your opinion about the contest.
eg. s = "ababbbaaa".
s = "ababa". Replace bbb with b and aaa with a.
You need to do this in O(n).
2.Gopu and Validity of Arrangement: (http://www.spoj.com/problems/SPCU/)
You can easily prove that if answer exists then it is unique, Only condition you need to check that any ith indexed person does not say that $\ge$ i persons are before him. You can relate this problem with permutations.
3. Gopu and Digits Divisibility: (http://www.spoj.com/problems/SPCU/)
You can easily do a brute force. Think about it why this works, Hint: for checking divisibility by 9, sum of digits should be divisible by 9. (Though hint is not of great use in the proof).
4. Gopu and Function: (http://www.spoj.com/problems/SPCM/)
Value of n will be atleast halved in each computation of f. As Take the best cases when n = 2*p where p is prime, Sum of divisors is 2 + p which is 2 + n / 2. In other cases, sum would be even less than n/2. For finding prime divisors of n, use simple sqrt algorithm. Final complexity would be O($\sqrt[2]{n}$ logn).
5. Gopu and Create Collections Part two (http://www.spoj.com/problems/SPCJ/)
You can use dp over the tree for solving this. You can use a greedy algo also. Sort the numbers in increasing order, go from right to left and for each number K if you find a number K/2 which is not yet taken then take it and add it to answer.
You can also use greedy algorithm by constructing the binary tree explicitly and then going from leaves to the root of the tree.
6. Gopu and Combinatorics on Graphs: (http://www.spoj.com/problems/SPCE/)
This is standard problem. You should know http://en.wikipedia.org/wiki/Cayley%27s_formula. Then figuring out things wont be tough. I dont want to give formulla as I want you to work it out.
7. Gopu and Counting bitwise prime numbers: (http://www.spoj.com/problems/SPCO/)
This problem had one slow solution:
use dp(i, tight): where i denotes the position in the binary representation of the number (i goes from most significant digit to lower), tight denotes wheteher the current number has overshoot the number n or n. See my slow code http://ideone.com/numnIE.
You can optimize it slightly and get it passed. Basically think in terms of combinatorics, You will get the idea.
Problems have been moved to spoj.
Editorials: (these editorials are merely hints, You need to work things yourself for final answers)
Hope you will like them. Leave a comment if something is unclear or needs to be modified, Also leave your opinion about the contest.
1. Gopu and Palindromes: (http://www.spoj.com/problems/SPCS/)
Consider the string s. Let it has some consecutive characters of length
L, Then you can directly replace L by just 1 character. After such
replacements just check if the string is palindrome or not?eg. s = "ababbbaaa".
s = "ababa". Replace bbb with b and aaa with a.
You need to do this in O(n).
2.Gopu and Validity of Arrangement: (http://www.spoj.com/problems/SPCU/)
You can easily prove that if answer exists then it is unique, Only condition you need to check that any ith indexed person does not say that $\ge$ i persons are before him. You can relate this problem with permutations.
3. Gopu and Digits Divisibility: (http://www.spoj.com/problems/SPCU/)
You can easily do a brute force. Think about it why this works, Hint: for checking divisibility by 9, sum of digits should be divisible by 9. (Though hint is not of great use in the proof).
4. Gopu and Function: (http://www.spoj.com/problems/SPCM/)
Value of n will be atleast halved in each computation of f. As Take the best cases when n = 2*p where p is prime, Sum of divisors is 2 + p which is 2 + n / 2. In other cases, sum would be even less than n/2. For finding prime divisors of n, use simple sqrt algorithm. Final complexity would be O($\sqrt[2]{n}$ logn).
5. Gopu and Create Collections Part two (http://www.spoj.com/problems/SPCJ/)
You can use dp over the tree for solving this. You can use a greedy algo also. Sort the numbers in increasing order, go from right to left and for each number K if you find a number K/2 which is not yet taken then take it and add it to answer.
You can also use greedy algorithm by constructing the binary tree explicitly and then going from leaves to the root of the tree.
6. Gopu and Combinatorics on Graphs: (http://www.spoj.com/problems/SPCE/)
This is standard problem. You should know http://en.wikipedia.org/wiki/Cayley%27s_formula. Then figuring out things wont be tough. I dont want to give formulla as I want you to work it out.
7. Gopu and Counting bitwise prime numbers: (http://www.spoj.com/problems/SPCO/)
This problem had one slow solution:
use dp(i, tight): where i denotes the position in the binary representation of the number (i goes from most significant digit to lower), tight denotes wheteher the current number has overshoot the number n or n. See my slow code http://ideone.com/numnIE.
You can optimize it slightly and get it passed. Basically think in terms of combinatorics, You will get the idea.
nice problem set
ReplyDeleteFor 3, can you given some sort of outline as to why brute force should work?
ReplyDeleteThis comment has been removed by the author.
DeleteThe number of Niven/Harshad numbers less than X is approximately equal to 1.1939*X / log(X) when X is large. for X=10^18 this is close to 2.88e16. I know that this does not ensure that the gaps are not very large but this works for this problem.
Deletesir can u help me for this problem http://www.spoj.com/problems/SPCE/
ReplyDeleteI got WA again and again