Editorials for TUXCODER 2014 - organized by Web Club NITK SURATHKAL and NITK Codechef Campus Chapter.
//Update : Problems have been added to Practice Section. Links to the problems are given below.
//This question is marked as Community Wiki. Please feel free to contribute and improve this Editorial.
Problem 1 : Balanced Team
Practice : link
Problem Setter and tester : Aditya Kadam
This was the easiest problem of the set. The balance of a team is simply the difference between the maximum and minimum value in the price of a team.
You can store the auction prices of all 15 players single team in an array and find the difference between the maximum and minimum value in the array. Since there are a total of 10 teams you need to do this for all 10 teams and output the minimum among these values. Care should be taken in the case when more than 1 team has the least balance, you should print the index of the team with highest index value among these teams.
Problem 2 : Supertitious Sreeni Huddle
Practice Section : link
Problem Setter : Manasa S
Problem tester : Anirudh R
In this problem, you are given 2 strings S1 and S2 of equal length. You are asked to check if the 2 strings are cyclic permutations of each other i.e. whether you can obtain the string S1 from S2 by performing rotations of S2. Eg. Consider 2 strings S1= ‘BBLAW’ and S2= ‘LAWBB’. In this case rotating S2 once will give you ‘BLAWB’. Rotating S2 once more will give ‘BBLAW’ which is same as S1. Hence the 2 strings are cyclic permutations of each other.
There is a nice O(N) solution for this problem but the limits set for this problem allow O(N^2) brute force solution to pass. Let us consider a simple brute force solution, take the first character of the first string and check if the second string matches, then go to second character of s1 and again check for s2. Continue this till you find a match or till you reach end of s1. While matching you should again return back to the first character after reaching the end of the string. This can easily be done by taking modulo with the string length i.e var % String_length.
The O(N) solution is requires a little ingenuity. If you concatenate the string s2 to itself then you can find any cyclic permutation of s2 in the string s2+s2. This is because instead of cycling back to the first character you can now continue from the end of the second string.Once you have concatenated s2 to itself, the question reduces to finding whether s1 is a substring of s2+s2. This can be done in O(N) time by using KMP string matching algorithm.
Problem 3 : Surathkal SuperStars:
Practice Section : link
Problem Setter and Tester : Tushar Makkar
The question asks you to find the value of N! modulo P where P is a prime number close to N. This problem is can be solved directly using Wilson’s Theorem.You can read further about Wilson’s theorem Wiki page.
Thank you to @yoyosonu for this additional explanation: According to wilson’s theorm (n-1)! mod n =(n-1) if n is prime. given n and p. n and p is very large but abs(n-p) is around 1000. 2 cases case 1. n>=p so p will be somewhere in the expansion of n!. so n!%p=0. case 2. (n<p) (p-1)!=(p-1)(p-2) … (n+1)n!=p-1 calculate (p-1)(p-2)…*(n+1) mod p and take modular inverse to find the ans.
You can refer to the solutions to have a look at the implementation details. Editorials for other questions will be put up in some time.
//Edit : All problems have been added to the practice section:
Here are links :
1) Little Chefs Team : [TUX02](http://www.codechef.com/problems/TUX02)
2) Run Or No Run : [RONR](http://www.codechef.com/problems/RONR)
3) IPL Stadium : [TUX01](http://www.codechef.com/problems/TUX01)
Links to the other problems are given in the Editorial