You are not logged in. Please login at www.codechef.com to post your questions!

×

July 18- Problem Discussion

5
1

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

asked 16 Jul '18, 16:48

vijju123's gravatar image

5★vijju123 ♦♦
15.5k12066
accept rate: 18%

edited 16 Jul '18, 18:32


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

  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)

  3. 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

link

answered 16 Jul '18, 20:51

megatron_64's gravatar image

4★megatron_64
224248
accept rate: 33%

@megatron_64 : I am not fully convinced with this answer of yours. Your entire explanation is based on an assumption: "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."

(18 Jul '18, 00:30) ritam7774★
1

@ritam777 : Actually that isn't an assumption
The observation in step 2 is that only one of the vector can have side greater than k/2
Let's call p(i) as probability of loosing if we give ith vector a magnitude greater than k/2
All I am saying is due to symmetry, p(1) = p(2) = ... = p(n)
Thus we can compute p(1) (which I have done above) and the probability of winning will thus be [ 1 - n * p(1) ]

(20 Jul '18, 22:51) megatron_644★

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:

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

link

answered 16 Jul '18, 21:52

vivek_1998299's gravatar image

6★vivek_1998299
1.6k29
accept rate: 23%

Can you provide the test case in which storing 2 edges instead of 3 will fail!

(17 Jul '18, 08:36) priyanshi_5★

If you have something like u -- 1 -- v -- (1,2,3) -- w -- 2 -- x , then if we store only 2 then we can get a sub optimal answer. But storing 3 makes sure that it's always possible to mitigate it

(17 Jul '18, 09:14) bhishma4★

@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

link

answered 16 Jul '18, 17:30

brij_raj's gravatar image

2★brij_raj
767
accept rate: 10%

edited 08 Jan, 12:04

@vijju123 First thanks for the letting us know the new question 3-tower (atleast new for me) and I have done it. While going through your NMNMX editorial below I was not able to figure out how the total number of ways are ${n-1} \choose {k-1} $

(17 Jul '18, 17:20) brij_raj2★
1

You have $N$ elements out of which you have to choose $k$ for sequence. Say I want to count contribution of an element $A_i$, then it means $A_i$ MUST be in sequence. Now I have rest of $N-1$ elements out of which I have to choose $k-1$. This is (n-1)C(k-1) by definition.

(17 Jul '18, 23:14) vijju123 ♦♦5★

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

link

answered 17 Jul '18, 14:30

cis_pie's gravatar image

5★cis_pie
1055
accept rate: 9%

Problem: NSA

My Solution: https://www.codechef.com/viewsolution/19173471

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.

link

answered 19 Jul '18, 16:17

ravi17bhagat's gravatar image

4★ravi17bhagat
273
accept rate: 100%

edited 19 Jul '18, 16:19

I have one question here how come one reaches to the conclusion that they have to use this way to proceed for the answer. I mean what's the intution behind the solution?

(20 Jul '18, 05:47) harrypotter04★

See it is a multi-step process. When you start solving a problem, generally you can't think of the best way in just one look. First you think of a simple way which can solve the problem mostly that is Brute Force and then as per the constraints you modify your approach. Some times it is possible and some times it isn't and you have to think of another approach.

In this ques- For the first try I used 2D arrays of n * n and also my complexity was of order n^2 and thus it didn't give complete AC soln.

(20 Jul '18, 09:57) ravi17bhagat4★

This is the beauty of Competitive Programming, many a times the answer is simple but to reach the answer within the constraints is what requires thinking.

(20 Jul '18, 10:01) ravi17bhagat4★

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

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

link

answered 16 Jul '18, 18:40

vijju123's gravatar image

5★vijju123 ♦♦
15.5k12066
accept rate: 18%

edited 16 Jul '18, 19:02

@vijju123 Please once look at my solution i have used same aproach, but there is any mistake and i am getting it partially accepted

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

(16 Jul '18, 21:46) lapmid2584★

I guess ik the mistake...

(a-b)%mod != a%mod - b%mod in c++...

use (( a%mod - b%mod)%mod + mod)%mod

(16 Jul '18, 23:26) l_returns4★
(16 Jul '18, 23:48) lapmid2584★
1

retval = (((n + 1 - i) * retval) / i) % (mod - 1);

Are you sure that this product will be completely divisible by i?

(17 Jul '18, 00:01) vijju123 ♦♦5★

U need mod Inverse there.... as "retval" is moduloed...

(17 Jul '18, 00:06) l_returns4★

(8/2)%7
is not equal to
((8%7)/(2%7) )%7
advice: avoid nCr method where u need division...

(17 Jul '18, 00:07) l_returns4★

nCk = ( (n+1-k)/k ) * nC(k-1) hence (n+1-k)*nC(k-1) will be always divisible by k (as i think), above suppose nCk=a , (( (n+1-k)/k ) * nC(k-1)) =b then i am just doing a=b% 1e9+7 i think internal division does not matter here as i am taking modulo of final value, firstly i am calculating nCk then i am taking modulo of it. internal division does matter here ??

(17 Jul '18, 01:16) lapmid2584★

It does. We do not use / in mod, we find the modular inverse for that. If $mod$ is prime like ${10}^{9}+7$, modular inverse of $k$ is ${k}^{mod-2}$. Read Fermat's Little Theorem for this.

(17 Jul '18, 01:26) vijju123 ♦♦5★
showing 5 of 8 show all

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

link

answered 16 Jul '18, 21:25

vivek_1998299's gravatar image

6★vivek_1998299
1.6k29
accept rate: 23%

edited 16 Jul '18, 21:55

Can you please explain your function-

bool bad(int a,int b,int c) { // use deterministic comuputation with long long if sufficient return (long double)(B[c]-B[a])*(M[a]-M[b])<(long double)(B[b]-B[a])*(M[a]-M[c]); }

(21 Jul '18, 18:38) vijju123 ♦♦5★

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.

link

answered 16 Jul '18, 18:31

rajankur's gravatar image

5★rajankur
533
accept rate: 0%

edited 16 Jul '18, 18:34

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 :

https://www.quora.com/In-graph-theory-when-dealing-with-chordal-graphs-what-is-a-simplicial-decomposition

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:

https://en.wikipedia.org/wiki/Chordal_graph

My solution:

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

link

answered 16 Jul '18, 22:05

vivek_1998299's gravatar image

6★vivek_1998299
1.6k29
accept rate: 23%

1

This problem can also be solved by binary search.

(16 Jul '18, 22:21) smartnj6★

Could u please explain your solution?

(16 Jul '18, 22:23) vivek_19982996★

consider test case

n=7 m=6 edges (1,2),(1,3),(1,4),(2,5),(3,6),(4,7)

root has 3 children. each children have 1 children.

size of max clique is 2 but the answer for this is 3. Even I thought of max clique but rejected it because of this example. can someone explain what's the correct answer?

(17 Jul '18, 14:36) praveenkumar125★

The ans for any tree is 2

like in ur case i would place a cat at node 1,so now the cat can be in {2,5},{3,6},{4,7}

Lets say it was at 2,then i could place the second cat at 2,

similarly other cases can be handled as well

Basically at each time we restrict the mouse in a subtree

(17 Jul '18, 16:11) vivek_19982996★
1

My bad I didn't know that cats can see position of jerry. Maybe they should've given a test case to explain that.

(17 Jul '18, 21:36) praveenkumar125★

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.

link

answered 16 Jul '18, 17:24

error_503_404's gravatar image

2★error_503_404
3107
accept rate: 5%

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?

(16 Jul '18, 17:56) vijju123 ♦♦5★

polynomial multiplication means FFT.

(16 Jul '18, 17:58) error_503_4042★

@vijju123 yes, you are right about tom and jerry

(16 Jul '18, 17:59) swetankmodi ♦♦6★

@swetankmodi - Any hints if you solved the question? Any link to tutorial etc?

(16 Jul '18, 18:40) vijju123 ♦♦5★

I don't understand your approach that you described in your answer but maybe you should check out my answer to this because I have used the series of $e^x$ there. I can give a brief explanation if you want.

(16 Jul '18, 19:01) psaini724★

@psaini72, my approach and formula is same as yours. How do you calculate the terms in denominator of g(z) where the denominator is polynomial? The doubt is what is inverse of polynomial and how to calculate it.

(16 Jul '18, 19:20) error_503_4042★
1

@vijju123 Yeah it is a maximum clique. Actually maximum cliques can be solved only in exponential time. However this is a special type of graph called chordal graph. Here it is easier to find maximum clique. Refer this page for more details.

(16 Jul '18, 19:53) sdssudhu6★

@error_503_404 Check solution to 438 E in http://codeforces.com/blog/entry/12513

One other thing I thought of to deal with this but didn't implement is to calculate Bernoulli numbers some other way because their generating function is $\frac{z}{e^z-1}$. Another advantage of doing this is that all other ntt's I did were of the same size. This can speed up the first ( rearranging ) part of the NTT.

(16 Jul '18, 19:59) psaini724★

Thank you @sdssudhu

(16 Jul '18, 20:21) vijju123 ♦♦5★
showing 5 of 9 show all

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

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

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

link

answered 16 Jul '18, 18:10

psaini72's gravatar image

4★psaini72
283111
accept rate: 25%

edited 16 Jul '18, 18:22

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

(16 Jul '18, 18:31) vijju123 ♦♦5★
2

@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?

(16 Jul '18, 18:44) psaini724★

Also, why aren't the editorials released just after ( or a few minutes after ) the contest is over, if, according to https://www.codechef.com/problemsetting, the editorials are finished even before the contest starts?

(16 Jul '18, 18:46) psaini724★

AFAIK its 50 karma for commenting on other's answers. Yes, I will add it in editorial part via links, i.e. something like "Many interesting approaches are also discussed here - ". I cant copy paste their answers - else that'd mean me getting karma which ideally belongs to them. I can give links to make sure everyone's effort is seem :)

Top solutions will be marked as accepted so that they remain at top always :)

(16 Jul '18, 18:47) vijju123 ♦♦5★

@psaini72 could you please share your integration idea. I was kind of thinking on similar lines.

I started with $n = 2$ and tried to find a pattern. For $n = 2$ the required region is the circumference of a circle centered at origin and of radius $k/2$. But I was stuck with the denominator. I was thinking like choosing 2 circles whose radii sum upto $k$. I was stuck on constructing the integral as I was modelling them as discrete structures.

(16 Jul '18, 19:00) bhishma4★
1

First, I thought of: What is the (geometric ?) condition that given n vectors ( both magnitude and direction ) that their sum is the 0 vector. Looking at the case for n=3, they can be arranged into a triangle when placing the tail of each at the head of another. Similarly, if n vectors sum to 0, they form a sort of chain. From the head of one to the tail of the next.

(16 Jul '18, 19:24) psaini724★
1

Now the question becomes, what is the probability that n vectors form a chain ( or a polygon, to be specific ). One necessary condition ( with reasoning similar to the triangle inequality ) is that no segment is greater in length than the sum of the lengths of the other segments. It turns out that this is also a sufficient condition. Just imagine placing the segments one by one. I don't really have a formal proof here.

Here, if a segment has length l, then the sum of lengths of the other segments is k-l. So, l <= k-l, l <= k/2.

(16 Jul '18, 19:25) psaini724★
1

Well, I have given you the pattern you wanted to know. I won't give you the details of the integration I'm afraid :(. Mine was too convoluted comparedd to others Ive seen. Just search for broken stick problem because it is the same as this.

The comment character limit was short so I wrote 3 comments.

(16 Jul '18, 19:26) psaini724★

I too did using integrals ,equlibrium.

evil(n integrals)

(16 Jul '18, 21:02) vivek_19982996★

why didn't u do try to submit using pypy?

my 20 pts solution submitted in pypy fetched me 50 pts :)

(16 Jul '18, 22:21) vivek_19982996★

I didn't expect pypy to be faster that's why.

The reason it passed is because the slow speed of pypy has been overcompensated by the time limit increase, but that didn't come to my mind while solving.

Also, I would have to write A LOT of pypy code from scratch having never written NTT in python before. I think my NTT in c was too slow to pass so I want to improve that first.

(16 Jul '18, 22:37) psaini724★

Basically if you take the log of g(z), you can eliminate the factor of ci or m.

(17 Jul '18, 11:31) aviroop1236★

@aviroop123 I see. Although I feel that my code would exceed TL in even more files if I tried this.

(17 Jul '18, 16:50) psaini724★
showing 5 of 13 show all

@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.

link

answered 16 Jul '18, 17:10

coldfire8549's gravatar image

2★coldfire8549
02
accept rate: 0%

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

link

answered 16 Jul '18, 17:14

error_503_404's gravatar image

2★error_503_404
3107
accept rate: 5%

Told @mgch to have a look at it. Thanks for sharing :)

(16 Jul '18, 17:18) vijju123 ♦♦5★

what is the idea behind the Reach Equilibrium problem?

link

answered 16 Jul '18, 17:48

skyhavoc's gravatar image

4★skyhavoc
1616
accept rate: 0%

1

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.

(16 Jul '18, 17:53) error_503_4042★

i had the same idea. but didnt code ...damn

(16 Jul '18, 19:05) skyhavoc4★
2

Idea is if one of the magnitude is greater than k/2 => then there is no way to get sum of vectors to zero. Alternatively, if all the magnitude is less than k/2 => There is always a way to get sum to zero.

Since the values can be real magnitude and there is a constraint, the possible values will form a hyperplane. So we need to find, what fraction of this possible solution space will have atmost one dimension greater than k/2.

For first dimension to violate the condition, it can be caluculated using integrals to be 1/2^(N-1), N different directions are there. So answer is 1 - N*(1/2^(N-1))

(16 Jul '18, 19:08) tamiliit3★

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

link

answered 16 Jul '18, 20:04

l_returns's gravatar image

4★l_returns
1.6k211
accept rate: 23%

1

this is same as this comment's solution I guess As discussed by @vijju123 too.... people got AC with same logic..

(16 Jul '18, 20:06) l_returns4★

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

link

answered 16 Jul '18, 20:36

shubham_icpcw9's gravatar image

3★shubham_icpcw9
111
accept rate: 0%

need explanation of problem statement or its 100 points soln ? Please clarify...

(16 Jul '18, 20:39) l_returns4★

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

link

answered 16 Jul '18, 21:39

shahbaz_07's gravatar image

2★shahbaz_07
101
accept rate: 0%

It is great way to clear doubts about different approaches for problems and share approaches in a thread form as it more interactive way.

link

answered 17 Jul '18, 23:21

vjvjain0's gravatar image

5★vjvjain0
91210
accept rate: 6%

Could anyone please share the approach to solve the SUBWAY problem. https://www.codechef.com/JULY18B/problems/SUBWAY

link

answered 16 Jul '18, 16:51

fmg_vishal's gravatar image

1★fmg_vishal
1
accept rate: 0%

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

(16 Jul '18, 16:53) vijju123 ♦♦5★

Yes that was it , LCA

(16 Jul '18, 17:32) smartnj6★

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

(16 Jul '18, 17:57) l_returns4★

also had an intuition that I ll need DP

(16 Jul '18, 17:59) l_returns4★

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

https://www.codechef.com/JULY18B/problems/MGCSET

link

answered 16 Jul '18, 17:01

migos's gravatar image

1★migos
11
accept rate: 0%

edited 16 Jul '18, 17:02

Someone else answered your question at https://discuss.codechef.com/questions/131430/july-18-problem-discussion/131446

My approach: If you are considering all subsequences of a sequence, you are also considering subsequences of length 1 i.e. each element. That means, that in a good subsequence, all elements are multiples of m. Also, if every element is divisible by m, then every subsequence is also divisible by m. We have found the sufficient condition: all elements are divisible by m.

If there are c elements in the array divisible by m, answer is all sequences of these elements = 2^c-1.

(16 Jul '18, 19:50) psaini724★

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; } //

link

answered 16 Jul '18, 17:07

praful8055's gravatar image

3★praful8055
1
accept rate: 0%

Please give LINK to your solution to keep discussion neat.

(16 Jul '18, 17:17) vijju123 ♦♦5★

modulo is wrong. Refer to my solution.

(16 Jul '18, 18:44) vijju123 ♦♦5★

When will editorials come out?

link

answered 16 Jul '18, 17:25

rds_98's gravatar image

3★rds_98
456
accept rate: 8%

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

link

answered 16 Jul '18, 18:43

rahul1v17_9's gravatar image

2★rahul1v17_9
232
accept rate: 0%

At every index of the string, if u have the count of each alphabet before and after the current index, you should be able to calculate the cost of replacing current index with 25 other characters.

Now the problem is computing the count. This can be done using partial sums. Think about it.

Time complexity - 26 * O(N)

(16 Jul '18, 18:57) tamiliit3★

@vijju123 nice explanation :)

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

link

answered 16 Jul '18, 18:46

milanj1's gravatar image

4★milanj1
213
accept rate: 0%

ooooooops :p . Sorry for typo. Thanks! :)

(16 Jul '18, 19:03) vijju123 ♦♦5★
1

yeah no problem , sorry can not comment there a upvote would help :P

(16 Jul '18, 23:02) milanj14★

Let's discuss PDELIV

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

link

answered 16 Jul '18, 18:47

bhishma's gravatar image

4★bhishma
2977
accept rate: 11%

`Sort pizzerias by position, and construct a segment tree of CHT (each node [L, R] contains a CHT of lines between L and R).

To get the answer for a consumer, you don't need to remove a line from your structure.

Now, supose there are 11 pizzerias, and consumer i doesn't like 3, 7 and 9. To answer this, you should get the minimum of 4 queries: [1, 2], [4, 6], [8, 8] and [10,11]. This works because the sum of forbidden pizzerias is at most 4 * 10^5 and the number of queries is about (N + M). The complexity of the query is log(N)^2 (one log from segment tree and one from CHT).`

(16 Jul '18, 19:03) vijju123 ♦♦5★

Above comment taken from here - http://codeforces.com/blog/entry/60447 had run out of chars.

(16 Jul '18, 19:04) vijju123 ♦♦5★
1

Insteadd of parabolas, we can transform problem to linear functions. Once we have done that we do CHT sqrt(n) times removing the lines that are in lower envelope. For each query if k_i>=sqrt(n) just iterate through all pizzerias, otherwise iterate through k_i+1 first lower envelopes, find the optimal position without removal and move right and left till we have pizzeria that we can use. Complexity will be O(nsqrt(n)) if we use sqrt(n) pointers and do queries offline. My AC code: https://ideone.com/wY5eto

(16 Jul '18, 19:40) tautsjasiunsas5★

Got TLE in one subtask with this approach :( ( one which @vijju123 shared)

(16 Jul '18, 19:58) l_returns4★

@vijju123 thanks for your efforts, but I'm the same guy who asked it in CF also. BTW could you please ask codechef admins to increase the character limit for comments if possible.

(16 Jul '18, 21:21) bhishma4★

Could anyone plz provides some insights for gears problem

link

answered 16 Jul '18, 22:03

araj1998's gravatar image

3★araj1998
1
accept rate: 0%

https://cp-algorithms.com/data_structures/disjoint_set_union.html#toc-tgt-11

The code given works as it is, and the explanation is pretty neat.

(17 Jul '18, 00:44) vijju123 ♦♦5★
1

So the main idea is to realize is that whenever you get a component with odd length cycle, it gets stuck.Hence every unstuck component has only cycles of even length. It can be shown that Bipartite <=> Graph with even cycles only. That's how the problem gets reduced to maintaining a DSU of bipartite components.

(17 Jul '18, 08:29) bhishma4★

For EQUILIBR, why don't we calculate the probability when one magnitude is greater than k/2 ???

link

answered 16 Jul '18, 23:24

titin_'s gravatar image

4★titin_
133
accept rate: 0%

Because even if we place all vectors ideally (in exact opposite direction to the one with magnitude greater than 1/2), we cannot obtain 0 sum.

(17 Jul '18, 00:04) vijju123 ♦♦5★

Did anyone solve the GEARS problem using DSU? If so, a detailed approach will be appreciated!

link

answered 17 Jul '18, 00:37

anujsingh14's gravatar image

4★anujsingh14
0
accept rate: 0%

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

link

answered 17 Jul '18, 11:20

coldfire8549's gravatar image

2★coldfire8549
02
accept rate: 0%

Refer to my answer for NMNMX. Then solve the question which I gave there, i.e. 3-tower coloring. If unable to solve, look at its editorial. The answer lies there- Discover it yourself for best benefits :)

(17 Jul '18, 14:02) vijju123 ♦♦5★

you can see fermets little theorem for mod-1 query

(18 Jul '18, 01:19) code__champ3★

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.

link

answered 17 Jul '18, 13:43

ankit_btech's gravatar image

4★ankit_btech
717
accept rate: 0%

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

link

answered 17 Jul '18, 16:54

sak6e's gravatar image

2★sak6e
1
accept rate: 0%

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

link

answered 17 Jul '18, 17:05

ankit_gupta_'s gravatar image

5★ankit_gupta_
11
accept rate: 0%

edited 17 Jul '18, 17:05

Try the one at cp algorithm. :)

(17 Jul '18, 17:20) vijju123 ♦♦5★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×164
×120

question asked: 16 Jul '18, 16:48

question was seen: 7,643 times

last updated: 08 Jan, 12:04