July 18- Problem Discussion

general
,
4

Can anyone tell me why i am getting tle in only last two test cases for subtask 2nd , for ques NMNMX
code:
//ll binomialCoeff(ll n, ll k)
{
ll res = 1;
if ( k > n - k )
k = n - k;
for (ll i = 0; i < k; ++i)
{
res *= (n - i);
res /= (i + 1);
res = res%mod;
}
return res;
}

ll power(ll x, ll y)
{
ll res = 1;
x = x % mod;
while (y > 0)
{
if (y & 1)
res = (resx) % mod;
y = y>>1;
x = (xx) % mod;
}
return res;
}

int main(){
go;
ll t;
cin>>t;
while(t–){
ll i,j,n,k;
cin>>n>>k;
ll a[n+1]={0};
ain(a,n);
sort(a,a+n);
ll b[n+1]={0},z=n,val=0;
lop(i,n){
val = (binomialCoeff(z,k) * k)/ z;
b[i]+=val;
z–;
if(val==1) break;
}
z = n;
for(i=n-1;i>=0;i–){
val = (binomialCoeff(z,k) * k)/ z;
b[i]+=val;
z–;
if(val==1) break;
}
val = binomialCoeff(n,k);
val = (val k)/n;
lop(i,n) b[i] = val-b[i];
//for(i=0;i<n;i++) cout<<a[i]<<" : “<<b[i]<<” ";
ll ans=1;
loop(i,1,n-2){
ans= power(a[i],b[i]);
ans = ans%mod;
}
cout<<ans<<endl;
}
return 0;
}
//

5

@migos Hi
Magic set problem , you need to find number of sub-sequences such that the sum of the elements in each of its non-empty sub-sequences is divisible by m.
Since requirement is that "sum of every elements in each of its non-empty subsequence (i.e.single elements subsequence also) therefore the subsequence should only contain those numbers which are divisible by m
so that requirement is met for every subsequence , that will be created from such a subsequence.

1 Like
6

The test case for GEARS problem was weak. It did not contain even a single test case having star-like structure, i.e. having no gears as blocked.

My solution will get TLE on such case where I iterate over all edges attached to the added vertex to check the graph is 2 coloured or not. So, if edges are added in the form “1 x” where “x” is any vertex and then randomly type 1 or type 3 queries come, my solution will easily get TLE. I just tried to optimise the brute force by handling case by case operations in O(1) and using small to large merging if possible but still couldn’t optimise one operation as stated above. Maybe similar test case is added to practice section.

@vijju123 @admin @mgch

1 Like
7

How to solve PRFRUIT? I thought about using moments to calculate expected value and then using polynomial of e^x to multiply polynomial (using divide and conquer and idea of geometric progression to reduce the degree of polynomial) but couldn’t proceed furthur as it required idea of inverse of polynomial which I couldn’t understand. Can someone explain their approach and tell if the problem was solvable using my approach or not? If yes, what is inverse of polynomial, please explain with an example. Thanks!

Also, I had no idea of tomjerry and subway problem, how to solve them. I liked the overall problemset except glitches in challenge problem.

2 Likes
8

When will editorials come out?

9

@migos.
In magic set problem, you have to select the good sequences (but actually it is sub sequences)

X_1, X_2, \cdots X_N

such that sum of each and every individual subseqences, let say the subsequences of

X_1 are X_{1a}, X_{1b} \cdots and so on

obtained by the good sequences, are divisible by m.
I know it is sounding a bit confusing but let me clear it up
first I am considering the sample input output itself

$

2,3\
1, 2\

$

if you are thinking that if we take consider the good sequence (which is a wrong idea)
\{1,2\} cause 1+2 = 3 is divisible by 3, wait and think. We have to see the sum of all subsequences individually

\{1,2\} has subsequences (ignoring empty) as

\{1\} Sum = 1 which is not divisible by 3

\{2\} Sum = 2 which is not divisible by 3

\{1,2\} Sum = 3 which is divisible by 3

We could have taken last one, but the all the subseqences of {1,2} didn’t satisfy the given conditions. So there are 0 good sequence

Now in 2^{nd} i/p

$

2,3\

1,3
$

We can consider a good sequence as \{3\}
Since all susequences of \{3\} = \{3\} Sum is divisible by 3. So the answer is 1

One thing you notice you can only form good sequence which each element divisible by m or every element of good sequence must be a multiple of m as their sum has to be divisible by m. You can easily prove it if not then ask.

Now taking a another example

$
7,3\

3, 6, 9, 10, 11, 12, 13

$

So you have to select every sequences in which each and every element is a multiple of m which is 3
How many sequences can be there
\{3\}, \{6\}, \{9\}, \{12\}, \{3,6\}, \{3,9\}, \{3,12\}, \cdots and so on. You can see the pattern here.

Or the the simpler way is to make the largest subsequence possible which is \{3,6,9,12\} and count all its non empty subsequences as it will include all possible subsequences and which is the answer.
Or 2^{Size\,of\,Largest\,Subsequence} - 1 = 2^4 - 1 = 15
I hope you get it. See code CodeChef: Practical coding for everyone

2 Likes
10

what is the idea behind the Reach Equilibrium problem?

1 Like
11

I will share my approach to PFRUIT.

The answer can be written as \displaystyle \frac{nu}{de} where de = \displaystyle \prod_{i=1}^n (b_i-a_i+1)^{c_i}

I found a relatively nice closed form for a function g(z) where the coefficient of z^i is \displaystyle \frac{nu_i}{i!} where nu_i is nu for k = i.

\displaystyle g(z) = \frac{\displaystyle \prod_{i=1}^n (e^{(b_i+1)z} - e^{a_iz})^{c_i} }{(e^z-1)^m}

What I did was just calculate this function till k terms to find nu.

However my solution got TLE for the very last test file in subtask 3.

I also am convinced that the intended solution is one where neither m nor any c_i is used to calculate the complexity. Only their value modulo the given prime matters I guess.

If anyone knows this other solution or got AC using my approach please share. :slight_smile:

Also, @vijju123, is this codechef’s way to collect alternate solutions before the editorials are released? :stuck_out_tongue:

Oh and did anyone even solve an integral like I did or did you just guess the solution for EQUILIBR ?

2 Likes
12

Problem :- NMNMX No Minimum No Maximum
My Solution :- CodeChef: Practical coding for everyone
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.

5 Likes
13

My solution for NMNMX -

First, try solving this problem - Tower 3-coloring | HackerRank

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: CodeChef: Practical coding for everyone

5 Likes
14

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

15

@vijju123 nice explanation :slight_smile:

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

16

Let’s discuss PDELIV

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

17

https://www.codechef.com/viewsolution/19243665
https://www.codechef.com/viewsolution/19244713

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
18

Can any one Explain NSA(No string attached) problem of july long challenge 2018?

1 Like
19

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,
    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
20

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:

https://www.codechef.com/viewsolution/19134059

5 Likes
21

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
22

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:

https://www.codechef.com/viewsolution/19146084

3 Likes
23

Could anyone plz provides some insights for gears problem