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 asked 16 Jul '18, 16:48

INTUITIVE APPROACH FOR EQUILIBR (with very basic maths) 
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  If we think logically putting each of these (n1) cuts is independent of one another (infinitely many real numbers between any range) Answer to problem = 1  n * [ (1/2) ^ (n1) ] The answer here turns out to be independent of k which perfectly makes sense. answered 16 Jul '18, 20:51
@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)
1
@ritam777 : Actually that isn't an assumption
(20 Jul '18, 22:51)

@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 answered 16 Jul '18, 17:30
@vijju123 First thanks for the letting us know the new question 3tower (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 ${n1} \choose {k1} $
(17 Jul '18, 17:20)
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 $N1$ elements out of which I have to choose $k1$. This is (n1)C(k1) by definition.
(17 Jul '18, 23:14)

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 answered 17 Jul '18, 14:30

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. answered 19 Jul '18, 16:17
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)
See it is a multistep 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)
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)

My solution for NMNMX  First, try solving this problem  https://www.hackerrank.com/challenges/tower3coloring/problem Now, look at my version of problem What is the contribution of each element? Simple! ${A_i}^{k}$ where $k=$ Number of subsequences 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 frequencyprefix array. Now, $K=Total$ $WaysBad$ $Ways$ 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 answered 16 Jul '18, 18:40
@vijju123 Please once look at my solution i have used same aproach, but there is any mistake and i am getting it partially accepted
(16 Jul '18, 21:46)
I guess ik the mistake... (ab)%mod != a%mod  b%mod in c++...use (( a%mod  b%mod)%mod + mod)%mod
(16 Jul '18, 23:26)
@l_returns still getting partially correct
(16 Jul '18, 23:48)
1
Are you sure that this product will be completely divisible by i?
(17 Jul '18, 00:01)
U need mod Inverse there.... as "retval" is moduloed...
(17 Jul '18, 00:06)
(8/2)%7
(17 Jul '18, 00:07)
nCk = ( (n+1k)/k ) * nC(k1) hence (n+1k)*nC(k1) will be always divisible by k (as i think), above suppose nCk=a , (( (n+1k)/k ) * nC(k1)) =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)
It does. We do not use
(17 Jul '18, 01:26)
showing 5 of 8
show all

Problem : NMNMX No Minimum No Maximum answered 16 Jul '18, 18:31

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.tuberlin.de/Members/Kreutzer/Publications/11gamessurvey.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: https://en.wikipedia.org/wiki/Chordal_graph My solution: answered 16 Jul '18, 22:05
1
This problem can also be solved by binary search.
(16 Jul '18, 22:21)
Could u please explain your solution?
(16 Jul '18, 22:23)
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)
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)
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)

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. answered 16 Jul '18, 17:24
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)
polynomial multiplication means FFT.
(16 Jul '18, 17:58)
@vijju123 yes, you are right about tom and jerry
(16 Jul '18, 17:59)
@swetankmodi  Any hints if you solved the question? Any link to tutorial etc?
(16 Jul '18, 18:40)
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)
@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)
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)
@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^z1}$. 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)
Thank you @sdssudhu
(16 Jul '18, 20:21)
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_ia_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^z1)^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 ? answered 16 Jul '18, 18:10
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 selfpublicizing." So there you are, why not have a fun thread with alt. soln? :)
(16 Jul '18, 18:31)
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)
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)
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)
@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)
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)
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 kl. So, l <= kl, l <= k/2.
(16 Jul '18, 19:25)
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)
I too did using integrals ,equlibrium. evil(n integrals)
(16 Jul '18, 21:02)
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)
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)
Basically if you take the log of g(z), you can eliminate the factor of ci or m.
(17 Jul '18, 11:31)
@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)
showing 5 of 13
show all

@migos Hi Magic set problem , you need to find number of subsequences such that the sum of the elements in each of its nonempty subsequences is divisible by m. Since requirement is that "sum of every elements in each of its nonempty 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. answered 16 Jul '18, 17:10

The test case for GEARS problem was weak. It did not contain even a single test case having starlike 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. answered 16 Jul '18, 17:14
Told @mgch to have a look at it. Thanks for sharing :)
(16 Jul '18, 17:18)

https://www.codechef.com/viewsolution/19243665 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... answered 16 Jul '18, 20:04

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 answered 16 Jul '18, 21:39

It is great way to clear doubts about different approaches for problems and share approaches in a thread form as it more interactive way. answered 17 Jul '18, 23:21

Could anyone please share the approach to solve the SUBWAY problem. https://www.codechef.com/JULY18B/problems/SUBWAY answered 16 Jul '18, 16:51
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)
Yes that was it , LCA
(16 Jul '18, 17:32)
fuck... I only referred one new algo for this problem... and that was LCA !!!
(16 Jul '18, 17:57)
also had an intuition that I ll need DP
(16 Jul '18, 17:59)

I couldn't get the MAGIC_SET problem solved. Insights? answered 16 Jul '18, 17:01
Someone else answered your question at https://discuss.codechef.com/questions/131430/july18problemdiscussion/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^c1.
(16 Jul '18, 19:50)

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=n1;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] = valb[i]; //for(i=0;i<n;i++) cout<<a[i]<<" : "<<b[i]<<" "; ll ans=1; loop(i,1,n2){ ans= power(a[i],b[i]); ans = ans%mod; } cout<<ans<<endl; } return 0; } // answered 16 Jul '18, 17:07
Please give LINK to your solution to keep discussion neat.
(16 Jul '18, 17:17)
c++: https://www.codechef.com/viewsolution/19241248 python: https://www.codechef.com/viewsolution/19243244
(16 Jul '18, 17:27)
modulo is wrong. Refer to my solution.
(16 Jul '18, 18:44)

Let's discuss PDELIV Did anyone solve sub task 3 using Li Chao segment tree. answered 16 Jul '18, 18:47
`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)
Above comment taken from here  http://codeforces.com/blog/entry/60447 had run out of chars.
(16 Jul '18, 19:04)
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)
Got TLE in one subtask with this approach :( ( one which @vijju123 shared)
(16 Jul '18, 19:58)
@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)

Could anyone plz provides some insights for gears problem answered 16 Jul '18, 22:03
https://cpalgorithms.com/data_structures/disjoint_set_union.html#toctgt11 The code given works as it is, and the explanation is pretty neat.
(17 Jul '18, 00:44)
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)

Hi @vijju123 ,Kindly explain why (mod1) is used, while calculating nCr() and mod is used while calculating power? In response to: https://discuss.codechef.com/questions/131430/july18problemdiscussion/131461 answered 17 Jul '18, 11:20
Refer to my answer for NMNMX. Then solve the question which I gave there, i.e. 3tower coloring. If unable to solve, look at its editorial. The answer lies there Discover it yourself for best benefits :)
(17 Jul '18, 14:02)
you can see fermets little theorem for mod1 query
(18 Jul '18, 01:19)

Hi @coldfire8549! The coder has used Fermat's Little Theorem. a^(m1)=1(mod m) when a and m are coprime. 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= m1. answered 17 Jul '18, 13:43

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. answered 17 Jul '18, 16:54

Can someone share some good resources on Lichao segment tree and convex hull trick? Thanks in advance.. answered 17 Jul '18, 17:05
