### Neumann's blog

By Neumann, history, 5 months ago, ,

Greetings Codeforces Community! CodeChef September Long Challenge is just around the corner. Everyone is encouraged to partake starting 6th September till 16th September. It is an occasion to put to test your exceptional programming skills.

The problem statements will be available in English, Hindi, Bengali, Russian, Mandarin and Vietnamese.

Accompanying me on the problem setting panel are:

In despite of having two chess "world champions" in the judge panel, this time there are no chess problems.

Hope to see you participating!

• +70

 » 4 months ago, # |   0 In problem DODGERS I have a doubt in getting l,r from x,y if(s==0) l=(x-1)%(N+1) and x is in range of [1,N] then l will be in range of [0,N-1] is it correct or i am understanding it wrong.Please help
•  » » 4 months ago, # ^ |   +31 You added parentheses that aren't in the statement. It's modulo $N$, then plus 1, as normal precedence rules say.
•  » » » 4 months ago, # ^ |   0 ohh shit, how can i miss that.Btw thanks
 » 4 months ago, # |   +28 The challenge is over.Congrats to the winners!Div 1. narry .I. (The cf logo coder) wmoise wrong_answer_1 zhouyuyang Div 2.
•  » » 4 months ago, # ^ |   +52 Are you sure thats CF logo?
•  » » 4 months ago, # ^ |   -8 Alekhine Chef Designed a Network: CHEFK1 . I think author solution is wrong for this problem . Critical test case: 22 242 . Ans should be 22 . But my code passed which shows output 21 . My connections: https://ideone.com/1xUKm4If you have better answer give me the connection . Not only 22 242 . It does not follow pattern for n=22 ,24,25,28,34,37,38,39,40,42,44,45,46,48,49,50,52,54,55,56,58,59,60,62,6364,65,66,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83 .My bruteforce code: https://ideone.com/ahag0pMy Accepted code: https://ideone.com/3vklml
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 ans is 21 construct without self edges with degree 20. hence, 2E = 20 * 22 => E=220,that is max number of edges we can built if degree is 20. now add self loops which are atmost 22 adding 1 degree to each edge. so net required is 21.
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   0 You can not count same edges twice. How can 22 nodes all have equal and unique 20 edges i can't understand. Let me understand, please write a printf code to show me which are the connections you are counting.
•  » » » » » 4 months ago, # ^ |   +8 do u know this 2*E <= n*degree, if not then google.you could also work on paper, its very simple.see one edge contributes to degree of two nodes. for building of graph that you have to do on your own, and you will able to it easily one you understand above equation.
 » 4 months ago, # | ← Rev. 2 →   0 can someone please explain their approach for DODGERS and DOOFST?
•  » » 4 months ago, # ^ |   +17 DOOFST:Subtask 1: Everyone hates each other, so everyone has to be in different groups at some point. Divide the bit string in half, left half gets all $0$, right half gets all $1$, then recursively divide each half again. You get something like 00001111 00110011 01010101 Subtask 2: In short: it should be a complete k-partite graph for some k.In not-short: If there is no edge between some pair of people, then these people must belong to the same group every time. Let's "invert" the graph, in every pair where there was an edge, now there's no edge, and vice-versa. Find the connected components in the inverted graph, you get this problem.After we've found the inverted connected components, let's return to our original graph. If there is any edge that connects two nodes in the same inverted connected component, then answer is $-1$. Otherwise we can consider each inverted CCs as a single node, every inverted CCs hate each other, so now the problem is literally subtask 1 again.
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 more related problem than connected components, https://codeforces.com/problemset/problem/190/E after building connected components, we just have to build complete graph. using divide and conquer and maintain address of parent.
•  » » » 4 months ago, # ^ |   0 Hello! First of all thanks a lot for such a nice explanation. I implemented the solution but got WA in just 1 test case. If possible then Can you please help?solution
•  » » » » 4 months ago, # ^ |   +3 I think you missed case $M = 0$. Should be $0$ operations.
•  » » » 4 months ago, # ^ |   0 Can you please explain me this a little more.
•  » » » » 4 months ago, # ^ |   0 Can you please explain me your question a little more? :)I don't know which part you are not understanding. It is simply "subtask 2 = subtask 1 + 920E or 190E". Take a small test for example: 3 1 1 2 We can see here that $1$ and $3$ don't hate each other, so every time the hate-inator fires, they have to be in the same group. $2$ and $3$ must also be in the same group. Since $1$, $3$, and $2$ must be in the same group every time, it's impossible to get $1$ and $2$ to hate each other, so the answer is $-1$.With the same reasoning we can invert the graph and solve with the exact same idea as 920E or 120E.
•  » » 4 months ago, # ^ | ← Rev. 3 →   0 I couldn't solve DODGERS, but I liked DOOFST a lot. Try to think for a few minutes, before opening each successive hint. Hint 1If there is no edge between two people, then it means, they were in the same set for all operations. We shall call $u$ and $v$ disconnected, if they have no direct edge between them. Hint 2If $u$,$v$ are disconnected, and $v$,$w$ are disconnected, then $u$,$w$ must be disconnected. ProofSince $u$ and $v$ are disconnected, they were always in the same set ( say A ). Since $v$ and $w$ are also disconnected, they were always in the same set ( say B ). But $v$ was in both, so A = B. This might not seem very convincing, so you might want to prove by contradiction, assuming that $u$ and $w$ are connected. That is easy. Hint 3If we think about the transpose graph ( if there is a edge remove it, and if there is no edge add it ). Then we basically have transitivity from Hint $2$.Claim: Transpose graph will be a Cartesian Product of some number of Complete Graphs ( Cliques ). FinalAll this is fine, but what about calculating answer. Let's say you find the total number of cliques in the transpose graph, say X. Claim: Minimum operations required is logX ( first power of 2 >= X ). Think about what the operation should be when you are in the transpose space.
•  » » 4 months ago, # ^ |   +27 DODGERS: Let's solve subtask 1 first.For each guest, let's find the closest left and closest right to that guest that they dislike. Now each guest can be represented as an interval $[Lguest, Rguest]$ in which they'll think the game is fair iff only the guests in that range are invited. We want to know how many guest think the game is fair for each query $[L, R]$.Let's think of it another way. Let's think of each query $[L, R]$ as points $(X, Y)$ on the 2D plane $(X = L$ and $Y = R)$. We have $O(N^2)$ possible points. For each guest, they will answer YES for a specific set of points. These points form a rectangle. So we have $N$ YES-rectangles, each corresponds to a guest. Let's get back to our question: "Given a query $[L, R]$, how many guest say YES for that query?". We rephrase the question as "Given a point $(X, Y)$, how many YES-rectangles does this point lie in?". This is now solvable offline with a line sweep + a range addition/point query data structure in $O((N+Q)logN)$. Fenwick is very fast.Subtask 2 is just subtask 1 with persistence.
•  » » » 4 months ago, # ^ |   0 can you please explain the first part a little more? How you are finding [Lguest, Rguest]?
•  » » » » 4 months ago, # ^ |   +1 $Lguest$ is the closest to the left guest that they dislike, and $Rguest$ is the closest to the right that they dislike.For example, if guest $1$ dislikes guest $4$ and $5$, then we only really care that $1$ dislikes $4$, since they'll say "NO" to parties $[1, 4]$ or $[1, 5]$ or anywhere further anyway. To find the closest left and closest right guests that they dislike, you just DFS once to find the order of befriendings. Then for every guest, you just go through their adjacency list and find the closest left and right by index that they dislike. Basically follow the statement."Go through their adjacency list" for all the guests takes $O(sum\ of\ vertices'\ degrees)$ in total, which is just $O(M)$
•  » » » » » 4 months ago, # ^ |   0 Sorry to disturb you again but can you please show a little how to add persistence to this to solve the subtask 2?
•  » » » » » » 4 months ago, # ^ |   +3 Have you solved subtask 1?For subtask 1 we want to query how many rectangles that contain a certain point. We can solve offline, so let's sort the queries by $X$ first. Then let's do a line scan in increasing $X$. We have to do the following: Whenever the scan line encounters the start of a rectangle, update the $Y$-range in which the rectangle lies in. Whenever we encounter a query point, just query the corresponding $Y$. Whenever the scan line encounters the end of a rectangle, update the $Y$-range in which the rectangle lies in (again). Therefore we need to support these operations: Update some range by $+1/-1$ What is the current value of an element? The easiest way to do this is by using a fenwick (but segment tree does work): When we want to update some range $[L, R]$ by $1$, we update $arr[L]$ with $+1$ and $arr[R+1]$ with $-1$ When we want to find out the value of $arr[P]$, we simply query the sum of $arr[1..P]$ No need for lazy propagation and goes very well with persistence.Now, for subtask 2, since we're solving online, we can't actually sort the queries. But we can still pre-process all the rectangles. Now the operations we need to support becomes: Update some range by $+1/-1$ What is the value of an element at some past version of the array? This is where persistent data structures come into play. It allows for us to query at a specific version of the DS.A little bit about persistent DS: the main idea is that instead of modifying the value in the DS, we create a new version of it without actually deleting the old version. We exploit the fact that very little $(O(logN))$ changes are made during each update, so we don't have to build the entire thing anew. There are two common ways of building a persistent DS: path copying (creating new root node, copy the entire new path) and fat node (turn every nodes into a dynamic array, store every value along with their version, and binary search for the most up-to-date version to the version we query) . There are plenty(1) of(2) tutorials(3) online.
 » 4 months ago, # | ← Rev. 6 →   +2 I was stuck at last two questions ( excluding Challenge question ).For PSUM, I thought about going from some state of $a^k + b^k + c^k$ to $(a+val)^k + (b+val)^k + (c+val)^k$, but that requires $O(K^2)$ time, using binomial expansion and precalculating factorials and inverse factorials. I think it was FFT based question, but I couldn't figure out how to apply FFT here. I thought maybe we can do transition between states in $O(KlogK)$. What I want to know here is, what's the correct way to think about something when you have some idea that, ok, maybe FFT could be used here? In this case, I didn't know how FFT works before I read this problem. I just knew FFT is something that can multiply polynomials in $O(KlogK)$ compared to the naive $O(K^2)$. I tried to read a lot of blogs of FFT, but I guess I was too focussed on bringing $O(K^2)$ down to $O(KlogK)$ whereas maybe we had to do something else.For DODGERS, if we look closely at the three conditions, you see that there is no point in graph structure ( please correct me if I am wrong ). If some guest has number outside $[L,R]$, then he won't be invited. If among all guests in $[L,R]$, we just find how many are directly connected ( friends ), then among all those there will always be one person who became friends with Dodger before other. i.e. problem reduces to find number of edges with endpoints in $[L,R]$. For each edge between $u$ and $v$, if $u$ finds it fair, then $v$ has to find it unfair. So we can drop the whole graph representation, and don't even need $DFS$. We just need for query $[L,R]$, how many intervals ( consider input $a$,$b$ as interval ) lie completely inside it. But I tried mergesort tree and fractional cascading too ( Credits: ifsmirnov for blog ). But it was too slow, and was giving WA on some cases. What am I doing/assuming wrongly here?UPD: Trying to clear its_aks_ulure's doubt, I got what I am doing wrongly! I was counting unfair because maybe people who think it is fair, overlap, i.e. They come before multiple people. But forgot to think same for unfair. For unfair also, there might be overlaps, thus counting edges from one person twice is wrong.
•  » » 4 months ago, # ^ |   0 For DODGERS, shouldn't it be how many intervals, lie completely inside it or lie partially intersecting ?
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 Partially intersecting doesn't matter, because if one end point is outside $[L,R]$, then that person wasn't invited ( only guests from $[L,R]$ are invited ). Did I understand something wrongly in the question?
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   0 I think so it actually matters, for example consider a Query [l, r] like [2, 5] say. The segment [L, R] for person 2 is say [1, 3], then surely person 2 is not happy because he has person 3 in the same set tho the segment [1, 3] is not completely inside query range [2, 5]
•  » » » » » 4 months ago, # ^ | ← Rev. 2 →   0 Oh, it seems you didn't read my whole post. The input given as edges $x$,$y$ is "considered" as "intervals".Then for query $[L,R]$, we need count of how many "intervals" are completely inside $[L,R]$. Because for each of those "intervals", it means that both persons ( end points ) are inside the query range, which makes sure both are invited. And both are connected ( friends ), because the "interval" exists ( we're not making up intervals on our own ). And finally, since time stops for no one, for a given "interval" which we now like to think of as an edge, out of the endpoints, Dodgers would definitely have become friends with one person before other, and other person will find it unfair. We count number of such "intervals", which gives number of people who think unfair, and subtract this from $R-L+1$.
 » 4 months ago, # |   +3 Can anyone share their approach for PSUM?
•  » » 4 months ago, # ^ | ← Rev. 2 →   +3 First let's solve it in O(SKN * logK). We have dp[i][j][k] = including i first elements, we have sum of cost j, and chose k elements. In other words, dp[i][j][k] = sum for ii < i for possible sequences seq of size k with elements that we chose at least once summing up to j and elements we chose 0 times having seq[x] = 0 of (value[ii]^s[ii] / (s[ii]!)). dp[i+1][j+cost] is (the convolution of 1 + (val[i]*x)^1 / 1! + (val[i]*x)^2/ 2! + ... and dp[i][j]) + (dp[i][j+cost]). The answer is sum of dp[i][j<=S][k] * k!. LinkBut that wasn't enough for my ntt code to pass, even though it should have been :PWith my ntt being too slow for this problem I managed to optimize it to a slightly better complexity. We can use 2D FFT/NTT to convolute matrices and solve this problem convoluting matrices of groups of size X. So for each group of size X we'll compute all the subsets that it has and put the proper things in the matrix, then we convolute it with what we had before. This has complexity O(2^X*K*(N/X) + (N/X)* SK * logSK). Choosing X as log(S * log(SK)) we can get complexity O(SKN) * O(log(SK) / log(S * log(SK))) and that's slightly better than the previous solution. Link. Actually, I didn't calculate the complexity before getting AC, I just plotted the function of the complexity in google and chose the minimum from there :P
•  » » » 4 months ago, # ^ |   0 Thanks a lot. And yeah,codechef time limits can be irritating at times.
•  » » » » 4 months ago, # ^ |   0 The solution above is a major overkill, read the editorial : https://discuss.codechef.com/t/psum-editorial/37796
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 Wrong !
•  » » » » 4 months ago, # ^ |   0 Uh... both the setter's solution and the tester's solution look like NSK*logK to me, they have O(N) loop with O(S) inner loop with a call of ntt/mutiplication of size O(K) so it's O(NSK*logK)
•  » » » » » 4 months ago, # ^ | ← Rev. 3 →   0 The editorial mentions a neat trick to solve it in O(NSK)Copy Paste from official editorial. SpoilerSo, instead of multiplying polynomials over and over again in $O(K \cdot \log K )$, we should use $O(K)$ point wise addition / multiplication of evaluations over the roots of unity instead to obtain evaluation of the required polynomial.Update: It's wrong. Now removed from editorial.
•  » » » » » » 4 months ago, # ^ | ← Rev. 2 →   +8 That's incorrect because multiplication over roots of unity is cyclic convolution so the coefficients get messed up. That's the reason why the actual solutions don't use that.
•  » » » » » » » 4 months ago, # ^ |   0 Indeed, ur right, I'm sorry, the intended complexity is $O(NSK \log K )$
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 tfg — Can you please tell what do seq[i] and s[i] represent in your explanation?
 » 4 months ago, # | ← Rev. 5 →   +18 Could somebody share their test generator for challenge? The 4-th test set is confusing me: the way it is described:"After generating the triples, try again if any of them have equal elements."seems to run very long for me. Even checking right after each triple seems to take forever. So instead I did some weird search:"After generating each triple, if the triple has equal elements, try again and add +1 to count_mistakes. Start again from scratch if count_mistakes > 64."Now it generated the test fast, but it felt like my local 4-th type tests were somehow very different still compared to the one visible test of 4th type. (sometimes very different scores)My generator: http://ideone.com/H144pL
•  » » 4 months ago, # ^ |   +8 I found that confusing as well. Did not really have the time to for good scores, but the way I understand it is this: if the three registers are always added to the list in a fixed order and in the end we take every third element of the list, that means that really we are just listing all the values of a single register during the run of the program. If an instruction does not change that register, we get consecutive equal values, so in order to get a list of valid triples, the program needs to change the register on at least 2/3 of its instructions, which explains why the fully random generation takes so long.
•  » » 4 months ago, # ^ |   0 I don't think I can help with this as long as there isn't a mistake in the description — I just edited what I was given and didn't check if it makes sense or works nicely. Spending hours on generating tests in special problems isn't that rare.
•  » » » 4 months ago, # ^ |   0 There was more discussion about this on codechef: threadTL;DR: the description was wrong — the real generation process was more like "Make 3 moves, shuffle registers, then add all 3 registers as a triple, repeat." (yes, can be solved using 60^3 brute force per triple) rather than what pwild described.
•  » » » » 4 months ago, # ^ |   +8 Bleh. For reference, this is the original text: - 20% : - pick three random 64-bit unsigned integer and assign those different registers - do this 3*$N$ times : - pick random two register, and picking randomly between the whole and the lower half part of the register - apply xor, and, or, add or sub instruction on the two register as operands - add the three register to the list - select every third item from the list - if the triplet is not valid than try to generate a new one with the same method