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? 
modulo is wrong. Refer to my solution.
@vijju123, that is a nice thought and a nice effort on your part. You should also add some of these answers on the actual editorial page ( if you feel they should be ) just to help anyone trying out these problems in the future, because I don’t think many people will write another answer on the editorial page.
An unrelated question:
Do you get a notif everytime someone writes @vijju123, or do you just regularly check the forums everyday?
2 Likes
Also, why aren’t the editorials released just after ( or a few minutes after ) the contest is over, if, according to Guidelines | CodeChef, the editorials are finished even before the contest starts?