Can any one Explain NSA(No string attached) problem of july long challenge 2018?
1 Like
INTUITIVE APPROACH FOR EQUILIBR (with very basic maths) -
Couple of observations here -
- Forces are balanced when they form closed polygon
If a1, a2, … are sides of polygon and sum of sides is k,
the polygon is possible only when none of the sides is greater than k/2
***PROOF*** -
*For n sides to form a closed polygon, sum of any n-1 sides should be greater than the remaining one side
i.e, X1 < X2 + X3 + ... + Xn
since X1 + X2 + ... + Xn = k, substituting value of RHS in above equation
X1 < k - X1
2X1 < k
X1 < k/2
- Lets try to compute probability of loosing here
A key observation is that only one of the vectors can be given length greater than k/2
(thats because sum of other n-1 is itself less than k/2 because total sum is k)
- So if we fix vector 1 to have side greater than k/2 and probability of loosing turns out to be p,
then,
Probe of winning = 1 - n*p
(thats because there are n options to fix a vector that will have side greater than k/2)
So the problem can be solved if we find p in step 3
To find p, vector 1 needs to have magnitude greater than k/2. Lets give vector 1 a magnitude of k/2
After the we have k - k/2 = k/2 magnitude left to be divided into n vectors
This problem is equivalent of following -
Consider a number line of [0, k] with segment [0, k/2] being blocked (because given to first vector)
What is the probability of putting n-1 cuts such that all cuts lie in (k/2, k] segment
If we think logically putting each of these (n-1) cuts is independent of one another (infinitely many real numbers between any range)
Also probability of a cut lying in second half of a number line is 1/2
Hence p = (1/2) ^ (n-1)
Answer to problem = 1 - n * [ (1/2) ^ (n-1) ]
The answer here turns out to be independent of k which perfectly makes sense.
This is because k here is the length of our line segment here and the cuts are real numbers.
Since the number of REAL numbers between [a,b] and [c,d] is same (infinite), the length of line doesn’t matter here
13 Likes
Regarding Pdeliv:
for case k_i=0,
for each i,
we want min(p_j+(x_j-x_i)^2)
1<=j<=m
where x_j is position of pizzeria,x_i is position of ith customer.
=min(p_j+x_j^2+x_i^2-2*x_j*x_i)
=x_i^2+min((p_j+x_j^2)+(-2*x_j)*x_i)
Ohk so this basically forms equation of line mx+c,where m=(-2*x_j),c=(p_j+x_j^2)
So this now becomes the basic convex hull trick.
Just add all lines(by taking all pizzerias),and lets say i want the ans for the i_{th} customer,so just query the convex hull ds with x_i,lets say it returns val,so ans for ith customer is x_i^2+val
Now when k_i!=0,it means we dont want to add these lines for calculating answer for i_{th} customer.
let m=7
let d[i]:2,5
So we ans for i_{th} customer is just min(ans for pizzerias from [1:1],[3:4],[6:7])
So basically now we would like to want to query for a range[l:r],like whats the minimum value for a particular x,when the set contains only lines from l to r.
This can be done using segment tree,where each node,contains a convex hull solver(just making up the name,dont know what i should call) for the lines in that range.
Note: Regarding TL,it was very strict,so Li-Chao segment tree,and set strategy didn’t work for me.There is an offline method of doing convex hull trick which works in O(1)(or rather O(n) summing all queries),which basically processes line in decreasing order of slopes or something like this,just google it ,u’ll find that.
my solution:
5 Likes
Can someone please provide me with the approach both brute and optimal for NSA problem or an algorithm for the same?
Thank you in advance
1 Like
Regarding subway,
I got 100 pts,though my solution fails in one task that my friend said ,but the idea is the same for the correct solution with just minor modification to my solution.
first we need to know that reducing the edges to atmost 3,doesn’t change the ans -why?(just try it,if u dont get it ask(u will get it anyway 
))
What i did was just stored 2 edges (correct solution stores 3 edges anyway).
Let dp[i][j][a][b] denote the maximum possible cost on the path from vertex i to 2^jth parent of i such that the path starts with the a^{th} edge of i,and ends at the b^{th} edge to j.
we can now calculate dp[i][j+1][a][b] by merging paths,i mean in order to find max cost to 2^{j+1}th parent of i,it is basically sum of max cost from i to 2^jth parent ,and 2^jth parent to 2^{j+1}th parent.
let us say i wanna calculate dp[i][j+1][0][1],
let par=2^jth parent of i,
dp[i][j+1][0][1]=max(dp[i][j][0][0]+dp[par][j][0][1]+(0th edge to j!=0th edge from j),
dp[i][j][0][1]+dp[par][j][1][1]+(1st edge to j!=1st edge from j),
dp[i][j][0][0]+dp[par][j][1][1]+(0th edge to j!=1st edge from j),
dp[i][j][0][1]+dp[par][j][0][1]+(1st edge to j!=0th edge from j),
)
edge to j means edge ending at j along the path i to 2^{j+1}th,and starting means edge starts at j along the path i to 2^{j+1}th.
Now u can easily answer the query (u,v),
calculate ans for path (u,lca(u,v)),(v,lca(u,v)) using similar strategy ,
And then merge it again taking that 0,1 cases like before.
For the correct code u probably would have to consider all cases for 3 edges.
My solution:
3 Likes
Could anyone plz provides some insights for gears problem
Regarding Tom and jerry,
the best thing to do was consider different graph and see the pattern,u could find that the ans was the maximum clique.
Though this was kinda research problem known as visible cops and robbers game.And it has a huge proof ,saying that the answer for visible cops and robber’s game is (treewidth of the graph)+1,
Here’s the paper if u want to read about it,
http://logic.las.tu-berlin.de/Members/Kreutzer/Publications/11-games-survey.pdf
(At page 19,it is given that ans is treewidth +1)
However finding treewidth is NPC,but since this graph is special(chordal graph),we can do something.
In this :
It is given the treewidth of chordal graph+1=maximum clique
And maximum clique of chordal graph can be easily found using perfect elimination order.
U can read it here:
My solution:
3 Likes
For EQUILIBR, why don’t we calculate the probability when one magnitude is greater than k/2 ???
Did anyone solve the GEARS problem using DSU?
If so, a detailed approach will be appreciated!
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.
