July 18- Problem Discussion

Problem :- NMNMX No Minimum No Maximum
My Solution :- https://www.codechef.com/viewsolution/19152448
Verdict :- AC (100)
Execution Time :-0.07 sec.
Explanation :- Question says we need to find product of all subsequences of length k without (max && min) in each of them.Now first of all let’s think to solve the question in required time if it is just to find product of all subsequences of length k.The approach is to find exponent of every number in the final product. Let’s say array ={10,4,8,6,2} & k=3. So,power of 2 = 4 = 6 = 8 = 10 = 4C2 . We can think this as you have to make array of size 3 where one element is fixed whose power you have to calculate. So,out of remaining 4 elements you can choose 2 elements.
Now,the actual problem was not including maximum and minimum in subsequence. So, basically for every number you have to find number of subsequence it will be maximum and minimum.
Let’s go back to same array ={2,4,6,8,10} & k=3.First of all sort the array as it won’t make difference to the answer. Now take element 6.
6 can be maximum only for those subsequence which will lie to the left of 6 in sorted array and similarly 6 can be minimum only for those subsequence which will lie right to 6 in sorted array.
So, in array = {2,4,6,8,10}, power of 6 in maximum case = 2C2 && minimum case = 2C2. Similarly power of 2 in maximum case = 0 & minimum case = 4C2. So,total power of 6 = 4C2-(2C2+2C2) ,2 = 4C2-4C2.
So,you can find all powers of element in O(n) traversal. Now question demand answer modulo(10^9+7).
One thing to know before computing modulo is in x^y modulo M if y is very large then you have to do
y = y modulo (M-1).{I can prove this but you will get detailed info about this on net so please refer to it}. Here, y is power of every element which will be in terms of nCr which will be very large for large test cases. Since M-1 is not prime so you can not apply Fermat theorem directly.
To compute this, I have applied Chinese Remainder Theorem. It basically says in context to nCr that in order to find nCr%p where p is not prime then factorize p into its prime factors and take modulo of each with nCr which is called remainders and apply the theorem. Now if you notice M-1=1000000006 is 500000003*2 ( both primes ). So, our task is easy and just find nCr modulo for both of them and apply the remainder theorem in it. I would suggest to look at my code whose link I have attached above to get better idea how to implement remainder theorem after finding the remainders.
This was my approach, if you find any difficulty in understanding or any suggestion then please do comment.


My solution for NMNMX -

First, try solving this problem - https://www.hackerrank.com/challenges/tower-3-coloring/problem

Now, look at my version of problem-

What is the contribution of each element?

Simple! {A_i}^{k} where k= Number of sub-sequences in which A_i is neither max nor min

Now problem boils down to calculating k - which is very easy. To make sure that A_i is neither maximum nor minimum of the sequence, find number of “bad ways”. If A_i is maximum, it means all elements are picked from elements < A_i, and if A_i is minimum, then it means that all elements are picked from elements >A_i. Count of these elements can be easily obtained by frequency-prefix array.

Now, K=Total Ways-Bad Ways
={n-1 \choose k-1} -{a\choose k-1}-{b \choose k-1}

where a and b are count of elements < A_i and >A_i respectively. Product of contribution of all elements is the answer :slight_smile: .

Solution link: https://www.codechef.com/viewsolution/19111524


Can anyone tell me the approach to solve NSA (No String Attached) problem from division 2? Thanks.

@vijju123 nice explanation :slight_smile:

I think in the total ways it should be n-1Ck-1

Let’s discuss PDELIV

Did anyone solve sub task 3 using Li Chao segment tree.


Here are my implementation for pizza delivery… got TLE in only 1 subtask for 100 points… Can anyone help in making it more efficient to pass ???

I made a segment tree with each segment containing a Convex hull trick of lines which that segment contain…

Difference between these solution is cht…

1 Like

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 -

  1. 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 
  1. 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)

  1. So if we fix vector 1 to have side greater than k/2 and probability of loosing turns out to be p,
    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


Regarding Pdeliv:

for case k_i=0,

for each i,

we want min(p_j+(x_j-x_i)^2)


where x_j is position of pizzeria,x_i is position of ith customer.



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:



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 :slight_smile: ))

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:



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,

(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:



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:

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

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- https://www.codechef.com/viewsolution/19235686

Can someone share some good resources on Lichao segment tree and convex hull trick? Thanks in advance…