# July 18- Problem Discussion

Hey guys,

July Long is done and I hope we have a lot of things to discuss before the editorials are up This thread is made for everyone to ask and answer doubts related to this contest, as well as to share approaches which they used to solve the questions. I look forward to you guy’s eager participation :). You can also use this thread to discuss and/or give your opinion about problems- any general discussion is fine.

EDIT: What do you guys think of having one such thread after every contest? Usually if editorials are out, then alternate solutions get discussed there - perhaps this thread might not be needed then, but for other cases it seems good (provided discuss isnt closed xD)

Regards
@vijju123

5 Likes

Could anyone please share the approach to solve the SUBWAY problem.

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

I couldn’t get the MAGIC_SET problem solved. Insights?

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 = (res*x) mod;
y = y>>1;
x = (x*x) % 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;
}
//

@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

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.

1 Like

Told @mgch to have a look at it. Thanks for sharing 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

When will editorials come out?

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

1 Like

Yes that was it , LCA

what is the idea behind the Reach Equilibrium problem?

1 Like

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