Tux Coder 2014 Editorials

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

7 Likes

For Problem 2, Superstitious Sreeni Huddle

Why does this solution give Wrong Answer? Here, I go about rotating the characters of string2 about the indices and checking if the strings match.

http://www.codechef.com/viewsolution/3717046

Can someone please explain problem 3( Surathkal SuperStars)? How is Wilson’s theorem applied on the given question?

1 Like

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.

6 Likes

The objective of the problem Surathkal Superstars is exactly same as the problem of Boring Factorials(DCEPC11B) on SPOJ. Here’s the link of the problem :

Boring Factorials :http://www.spoj.com/problems/DCEPC11B

Even the sample testcases of both the problems are same.

Your answer for the test case BBLLAAAAW LLAAAAAWB gives NO while the expected answer in yes. Infact, it gives Wrong Answer for all test cases except for one. Please do check your code once again

1 Like

@ani94 Yes, it should give NO! There’s only 1 B in the second combination of your test case! If Guru’s reported order is LLAAAAWBB or BLLAAAAWB instead, my program aptly gives yes! Please check the test cases!

Very sorry gave a wrong test case. Try these cases of two strings already being same: https://ideone.com/5FrXHm .

Oh yeah!!! Strings already being same!!! My bad @ani94

Why is this http://www.codechef.com/viewplaintext/3715896 getting TLE?

@gautam94 dude its giving TLE for the test case A A . I don’t exactly know why, probably a small bug or part of the code you have neglected.

1 Like

@gautam94 The simplest approach to solve the problem is to concatenate the same string at the end and then search for the second string in the concatenated first string,

1 Like

@ani94 yes I read that in the editorial and its also faster. but still i want to know why my solution failed to pass the tests.

@knb_dtu Yes. Both problems are based on the same concept of Wilson’s Theorem. The contest was mainly organized for 1st and 2nd year NITK students and you will see all prizes are also only for them. These people have recently been introduced to competitive programming as part of the NITK Codechef campus chapter. This is a pretty useful theorem and we wanted to introduce them to this concept. Even though the sample test cases are same, all the internal test cases were generated by us.

1 Like

Can you provide some problems based on wilson’s theorm?