Hi @vijju123 ,Kindly explain why (mod-1) is used, while calculating nCr() and mod is used while calculating power?
In response to:
https://discuss.codechef.com/questions/131430/july-18-problem-discussion/131461
Hi @coldfire8549!
The coder has used Fermat’s Little Theorem.
a^(m-1)=1(mod m) when a and m are co-prime.
If you want to calculate a^b mod m where b is very large and you can calculate b only modulo some p, then you can do so by setting p= m-1.
Problem : Gears
For the query of type 3, speed depends only on u and v.
And the sign of answer depends on whether it is connected to other vertex by odd length or even length path. Because in the connected gear system there will be alternate +ve and -ve signs of answer from given vertex.
In short you have to color the graph in two colors.
I had maintained graph and used disjoint set data structure and array for gear teeth and when you have to change the teeth value you can just change value of array.
Maintain different color for each gear and when you connect two gears just change the color of other gear.
Note: Gears will be blocked when there is odd length cycle.
for query of type 3,
Suppose you have two components in which each components may contain several connected gears.
When query of type 2 occurs and you have to connect these two components then use disjoint set data structure and change the color of smaller component according to bigger components For e.g you had used colors 2,3 for 1st component and 4,5 for other component then change color of second component (if 2nd is smaller component).
while connecting two vertices from same component just check if one of them is blocked or by connecting these vertices will there be any odd length cycle ? i.e do they have same color ? because now you cant connect them if they have same color and after connecting they must have different colors hence all the vertices from component will be blocked.
Last while answering type 3 you can check color of both vertices if they are same color : use + sign answer else negative answer.
My solution https://www.codechef.com/viewsolution/19233845
1 Like
NMNMX:
For each element of the array, I calculated no. of subsequences in which that element was min and in which it was max by using simple nCr logic. Subtracted it from the total no. of subsequences of each element(same for each). Then raised that element to this no., which could be huge so used Modular Exponentiation.
I got 20 points(AC in subtask 1).
I’m getting Runtime error SIGFPE in subtask 2. Please help, I’m a beginner coder. Please help.
Here’s the link- CodeChef: Practical coding for everyone
Thanks.
Can someone share some good resources on Lichao segment tree and convex hull trick? Thanks in advance…
It is great way to clear doubts about different approaches for problems and share approaches in a thread form as it more interactive way.
1 Like
Problem: NSA
My Solution: CodeChef: Practical coding for everyone
This problem requires a strict time complexity for complete AC solution.
I have used 2 2D arrays(S and G) of size 26*(10^5) and 1 1D array(freq) of size 26.
In the arrray S,I traversed the string from the start and stored the frequency of all the characters which have come before the ith character into the ith column of the array.
In the arrray G,I traversed the string from the last and stored the frequency of all the characters which have come after the ith character into the ith column of the array.
Both of these operations has complexity of order 26*(length of string).
For calculation of Y in initial configuration of string I have summed up all the freq stored in the array G for ith column and jth row such that j>s[i]. (This is equal to number of pairs <si,sj> such that si<sj and i<j).
Now coming to modification part, I have checked all 26 combinations for every character in the string and calculated the difference which a particular change makes.
If the new Y + X is less than min value, the min value is updated.
Complexity for this is order of 26 * 26 * (length of string).
Finally,the min value gives the solution.
1 Like
AFAIK, it was dp+LCA. I thought if we can somehow store information about cost like we make LCA table (cost to go to {2}^{i}’th ancestor), but didnt have time to code that/ 
Who did SUBWAY here? xD
Please give LINK to your solution to keep discussion neat.
Yes that was it , LCA
Understand that answer is independent of k as your choice is only to assign directions. Look at example and see how 11 and 16 are related to 5. denominator is will something of form 2^x as there are opposite directions for vectors to cancel. Guess 2^{(n-1)} is denominator and then see numerator is exactly n less. Submit and proof by AC. Best guess problem. No idea about logic though.
1 Like
Tom and Jerry seemed like maximum Clique or something to me. But I am not well versed in those algorithms. PRFRUIT seemed like clear FFT. Did you try that angle?
fuck… I only referred one new algo for this problem… and that was LCA !!!
but didn’t worked on it thinking that would be a tougher question…
polynomial multiplication means FFT.
also had an intuition that I ll need DP
Thanks for your insight @psaini72 . Lol no, its not a way to collect alternate solutions. Its just a mix of factors which prompted me to make this thread. Like, problem discussion after CF is cool, why not have it at CC as well? Then, editorials arent out and its just after the contest- many high rated coders surf discuss at this time for editorials. I think they’d love to hear and share approaches as well. The igniting point was, hearing from a friend that “I feel shy sharing my approach - people will feel I am self-publicizing.”- So there you are, why not have a fun thread with alt. soln? 