### Nanako's blog

By Nanako, 3 months ago,

Idea by m_99

Hint 1
Hint 2
Hint 3
Solution
Code (m_99)

Idea by m_99

Hint 1
Hint 2
Solution
Code (Nanako)

## 1770C - Koxia and Number Theory

Idea by triple__a

Hint 1
Hint 2
Hint 3
Hint 3.5
Hint 4
Solution
Code (Nanako)

## 1770D - Koxia and Game

Idea by m_99

Hint 1
Hint 2
Hint 2.5
Hint 3
Solution
Code (Nanako, DSU)
Code (zengminghao, DFS)

Idea by m_99

Hint 1
Hint 2
Hint 2.5
Hint 3
Solution
Code (Nanako)

Idea by m_99

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Hint 6
Solution
Code (errorgorn)

## 1770G - Koxia and Bracket

Idea by huangxiaohua and errorgorn

Hint 1
Hint 2
Hint 3
Hint 4
Solution
Code (errorgorn)

## 1770H - Koxia, Mahiru and Winter Festival

Idea by SteamTurbine

Hint 1
Hint 2
Preface
Solution (sketch)
Solution (details)
Code (SteamTurbine)
Visualizer (Python script)

• +243

 » 3 months ago, # |   -8 I thought I did pretty bad this contest(Problem A harder than B and C) but still managed to get a positive delta.
•  » » 3 months ago, # ^ |   0 i was not able to solve any questions , got stuck in problem A But by this contest i will get to learn a lot for sure and will improve in next contest
•  » » » 3 months ago, # ^ |   -6 same happened to me
•  » » 3 months ago, # ^ |   -17 same :)
•  » » » 3 months ago, # ^ |   -6 Same same
•  » » 3 months ago, # ^ |   -6 my rating delta is 0 T_T
 » 3 months ago, # | ← Rev. 2 →   +3 C can also be solved in O(50 * n) as for a prime to fail it should have at least 2 * p indices.(min(cnt0,cnt1,…,cntp−1)≥2). but as n <= 100 we can have p <= 50. my submission
•  » » 3 months ago, # ^ |   +5 I missed that observation, I checked all primes under 1000 because it I thought it would be reasonably high enough.
•  » » 3 months ago, # ^ |   0 Actually, you can solve the Question with max upper bound of 25 primes since the 26th prime is 101 which can't become unavailable for x since max elements are 100
•  » » 3 months ago, # ^ |   +18 n/2 = 50 is actually O(n), so this solution (O(n^2)) is not better than tutorial
•  » » 3 months ago, # ^ |   0 When we say an algorithm is O(n^2), it means it grows quadritically with nLets take n = 1000, your algorithm will need O(500*n) then, do you see why your algorithm is still quadriatic wrt n?
•  » » » 3 months ago, # ^ |   0 Bro I realized few seconds after posting, but I think we cant delete So left it like that :(
 » 3 months ago, # |   0 I misread B, I thought that the cost is sum(c), not max(c). Somehow I still got AC.
 » 3 months ago, # |   +31 I loved the problems of this contest. They were enjoyable to solve. Still amazed...
 » 3 months ago, # |   +4 Why the constraint for $n$ in problem C is too low? Since the complexity is $O\left( \dfrac{n^2}{\log n}\right)$ why not $n \leq 10^4$?I did an $O\left( \dfrac{n^4}{\log n^2}\right)$ that wouldn't passed with higher values of $n$
•  » » 3 months ago, # ^ |   0 It is actually O(n * sqrt(n)) :)
•  » » 3 months ago, # ^ |   -7 The author team deliberately set it as troll. We didn't mean to kill $O(\frac {n^4} {\log n})$ specially but implementations with high constant time will lead to a TLE.
•  » » » 3 months ago, # ^ | ← Rev. 2 →   +1 and the author somehow succeeded in killing pollard rho (I don't know if that's intended, though I think it should be)
•  » » » » 3 months ago, # ^ |   -68 I see how you cheated C. Now stop putting shit here. Shit.
•  » » » » » 3 months ago, # ^ |   +25 proof bro? my first AC is just skipped due to resubmission. You can easily see it barely fits in TL
 » 3 months ago, # | ← Rev. 4 →   0 Please fix the LaTeX in Solution F.
•  » » 3 months ago, # ^ |   0 thanks for the reminder and it's ok now.
•  » » » 3 months ago, # ^ |   0 And for the solution of C, it should be if $x\equiv 0 \pmod 2$?
•  » » » » 3 months ago, # ^ |   0 Thanks, you're right.
 » 3 months ago, # |   0 Is there any prize in this contest for individuals ranking under 2k
 » 3 months ago, # |   -8 ah yes of course chinese remainder theorem on third task sily me for not knowing fringe ideas on suposedly easier tasks
•  » » 3 months ago, # ^ |   0 CRT is not generally considered a fringe idea.
•  » » 3 months ago, # ^ | ← Rev. 3 →   0 Chinese Remainder Theorem only states that there exists a unique solutionEdit again: In coding, CRT refers to the algorithm using this fact, so I was wrong
•  » » 3 months ago, # ^ |   +22 CRT is one of the crucial ideas you should always think about when solving a number theory related problems.
 » 3 months ago, # |   0 While there are many primes up to 10^18, we only need to check for the primes up to ⌊n/2⌋. This is because min(cnt0,cnt1,…,cntp−1)≥2 is impossible for greater primes according to Pigeonhole Principle. whyy??
•  » » 3 months ago, # ^ |   +17 Take prime $p = 53$ as an example, it's impossible to use only $100$ elements to fill a bucket of size $53$ and each slot has at least $2$ elements.
•  » » » 3 months ago, # ^ |   0 elaborate for this tc plz 2 10005294,10005402
•  » » » » 3 months ago, # ^ |   +6 Surely it's YES without checking any prime. If $a_i$ are pairwise distinct, the minimum case with answer NO is $n = 4$ as mentioned above.
•  » » » » » 3 months ago, # ^ |   0 what about this 5 10005294,10005402,10005398,10005212,10004358 ???
•  » » » » » » 3 months ago, # ^ | ← Rev. 4 →   +3 For $p=2$, we get $\mathit{cnt}_0=5$ and $\mathit{cnt}_1=0$.For $p=3$, it's unnecessary to check because of Pigeonhole Principle. If we check it, we get $\mathit{cnt}_0=3$, $\mathit{cnt}_1=0$ and $\mathit{cnt}_2=2$. Ensuring $x \bmod 3 = 2$, we can calculate a proper $x$.
•  » » » » » » » 3 months ago, # ^ |   +3 so answer should be YES
•  » » » » » » » » 3 months ago, # ^ |   0 Surely for $x = 5$.
•  » » » » » » » » » 3 months ago, # ^ |   0 Thanks, got it now.
•  » » 3 months ago, # ^ |   +3 If min(count(i))>=2, then sum(count(i))>=p*2, which means 2*p<=n
 » 3 months ago, # |   +44 Problem C and D are really really amazing (and easily one of the best problems I've ever come across, the proof of C, the pigeon hole principle drives me crazy!) ! I really appreciate the authors for such amazing problems. Its a pity I wasn't able to participate :(
•  » » 3 months ago, # ^ |   0 I've been trying to figure out that pigeon hole idea could you please explain it or point me to a resource that does.
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 can you please explain Pegion hole principle proof ?,why only we are checking primes less than n/2. I am still stucked in that.
 » 3 months ago, # | ← Rev. 2 →   -18 ayo everybody
 » 3 months ago, # |   -34 CRT for 3rd task?, cannot believe..trash round
•  » » 3 months ago, # ^ | ← Rev. 2 →   +32 You don’t actually need to know it, I just observed that if there were two odd and even there would always be at least two even, so modulo 2 would be present. I later expanded this idea to other prime numbers.
•  » » » 3 months ago, # ^ |   0 I didn't get it, can you please elaborate on your intuition, I would like to know your thought process.
•  » » » » 3 months ago, # ^ |   +14 If there are two odd numbers and two even numbers, there will always be at least 2 even numbers. This is because any number you add has to be odd or even, therefore the two original even numbers will be even if an even number is added and the two odd numbers will be even if an odd number is even. This means there will be a pair divisible by 2(or gcd!=1). Now the underlying structure of this phenomenon is important. Why does this work? Well in modulo arithmetic (a+b)%m = a%m + b%m. If a is our given number, and b is what we’re adding, we can only add two distinct values (0 and 1). If the problem was simply gcd!=2, we only need to check whether there is one distinct modulo of 2. Otherwise, no matter what we add there will always be at least 2 numbers where %2==0. However, this principle itself is not only restricted to 2, it can be done for any number. For our purposes, we only need to check prime numbers although it’s not necessary to find out which prime number to check. Since n == 100, the maximum number we need to check is 50(since there needs to be at least 2 in each spot for it to fail). The main intuition came from the fact that n is reasonable small, so the solution must involve checking all the number in the array in terms of their modularity rather than gcd or other measures on the elements since the elements themselves can be quite large.
•  » » » » » 3 months ago, # ^ |   0 thanks, dude!
•  » » 3 months ago, # ^ |   +29 You don't need to implement the algorithm of CRT. It's just used to promise the existence of such x. In fact many contestants got AC by intuition.
 » 3 months ago, # |   0 Can someone explain the transitions in dp for G ?
 » 3 months ago, # | ← Rev. 2 →   0 Can anyone clear my doubt? In problem C, suppose that I have checked the remainders upto p primes , and I got such x, which satisfies the given condition( I constructed this x from first p primes where p is greater than largest element in the set). Now, how can I say that the solution I got will not contain any multiple of primes which is greater than pth prime when every element is different. I didn't get proper intuition here, so I didn't proceed afterwards :( any help will be highly appreciated.
•  » » 3 months ago, # ^ |   0 By solution, I mean final state of array, that is (a1+x,a2+x....)
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 A intuitional sketch explanation is, for a large enough prime $p$, we can always find a proper value $\mathit{offset}$ so that none of $a_i + \mathit{offset}$ will be multiples of $p$.
•  » » » 3 months ago, # ^ |   0 Is this ai ai+x or is it the initial ai, (here x is same as how I constructed x using first p primes).
•  » » » » 3 months ago, # ^ |   0 the initial.
•  » » » » » 3 months ago, # ^ |   0 But, after choosing that offset, still I may find some different x, and after addig this x to ai+ offset, I still cant say that there is no multiple of such large p.
•  » » » » » » 3 months ago, # ^ |   0 The final $x$ is derived by merging many of $\mathit{offset}$ with Chinese Remainder Theorem, instead of summing up. So primes won't affect each other.
•  » » » » » » » 3 months ago, # ^ | ← Rev. 2 →   0 Now, how can you we say that this new x is not giving two multiples of primes, which are greater than the primes from which I constructed this x. It will be very helpful if this is explained in the editorial.
•  » » » » » » » » 3 months ago, # ^ |   0 Maybe I didn't really get your point, so I hope it can be helpful to take this case as an example. When we list equations accordingly, just like: $x \equiv 1 \pmod 2 \\ x \equiv 2 \pmod 3$. We will able to calculate a proper value like $x = 5$ using CRT. When we continue to add more equations for larger primes, the calculation is still possible as long as adding valid equations is possible.
•  » » » » » » » » 3 months ago, # ^ | ← Rev. 3 →   +17 The $x$ isn't constructed by merging the congruences of primes $p \le n$, but $p \le \max |a_i - a_j|$ over all $1 \le i < j \le n$ (i.e. the largest difference between any two values in the array). We just know that for any $p > n$ there has to exist some remainder $r$ such that $a_i \equiv r\ (mod\ p)$ doesn't appear at all. That's why we don't need to calculate them.We don't need to check any primes $p > \max |a_i - a_j|$ since for two values $a_i + x,\ a_j + x$ to both be divisible by some prime $p$, we would also need their difference $|(a_i + x) - (a_j + x)| = |a_i + x - a_j - x| = |a_i - a_j|$ to be divisible by $p$ which is not possible if $p > \max |a_i - a_j|$.
•  » » » » » » » » » 3 months ago, # ^ |   0 Why x need to be constructed by only p<= maxabs(ai-aj), suppose that I have constructed such an x in this way, and I will see the array (a1+x, a2+x,.... an+x). Now, I can guarantee that no two of them hve a common factor of p for all primes <= max(ai-aj). How can I comment on p> max(abs(ai-aj)), I mean how can you say that there doesnt exists 2 multiple's of p>max(abs(ai-aj)) in the array (a1+x,a2+x...an+x). Hope you got my doubt...
•  » » » » » » » » » 3 months ago, # ^ | ← Rev. 2 →   0 I updated my original comment to show this. Message me privately if you still don't understand this.
•  » » » » » » » » » 3 months ago, # ^ |   0 Thank you very much for the solution.
•  » » » » » » » 3 months ago, # ^ |   +1 Just a little question, why is the cost mentioned in Hint 1 of problem B 2n instead of n only?
•  » » » » » » » » 3 months ago, # ^ |   +8 If $k = 1$, the cost of the section which only has the value $n$ is $max(n) + min(n) = n + n = 2n$
•  » » » » » » » » » 3 months ago, # ^ |   0 ah yeah, my brain just stopped working and just thought that it's only the max(n) only...
 » 3 months ago, # |   +41 I think in problem E, you need to elaborate on why the probabilities attached to the vertices are independent (in fact, they are not!), otherwise the probability of a value of ${\mathit{siz}}_{\mathit{son}}$ may be non-deterministic.
•  » » 3 months ago, # ^ |   +16 Aren't they independent as the two components separated by the current edge have not been in contact with one another (which means every event within each component is independent to the other, and by extension the sizes and probablilities and whatnot)?
•  » » » 3 months ago, # ^ |   0 Precisely, what he means to say is that what you've written should have been there in the editorial.
 » 3 months ago, # |   +8 Problem A was literally mind blowing
 » 3 months ago, # |   0 In C after checking for all primes <= N. After that how can we say that there will exist a number such that gcd will be 1 for every pair.
•  » » 3 months ago, # ^ |   0 If no prime was found where every possible remainder appeared at least twice, there has to be at least one remainder for every prime such that $x \equiv r\ (mod\ p)$ works. We know that such $x$ that fits all of the congruences always exists because the Chinese remainder theorem says so. (Go to the proof-section for the proof of the theorem).
•  » » » 3 months ago, # ^ |   0 Thanks a lot!
•  » » » 3 months ago, # ^ |   0 Bro can you please explain this line with an example. I can understand it
 » 3 months ago, # |   +11 Did anyone else miss A because they sorted array b?
•  » » 3 months ago, # ^ |   0 I solved A after B,C,D with four WA's because of this.
 » 3 months ago, # |   +10 Why is my Python PriorityQueue solution too slow in PyPy. 187389454In Python 3.8 it is faster: 187389600
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 The queue module is for ensuring thread safety, as such, the PriorityQueue that appears within it suffers from some extra overhead even if you aren't writing multi-threaded code. The more usual module to use is heapq.As for why pypy is slower in this case, it depends on what its maintainers are willing/able to get to. Synchronization can get gnarly, especially if optimized with per-platform specifics, so it's understandable that the maintainers might count that as a prohibitively high maintenance load vs. how relatively rarely it comes up.
 » 3 months ago, # |   +1 Can someone explain why "Then there is a way to make $p$ a permutation iff there is a way to assign a direction for every edge such that every vertex has one edge leading into it. " is true in problem D's editorial?
•  » » 3 months ago, # ^ |   +7 For choosing one element from $a_i$ and $b_i$, we can consider "choose $a_i$" as "edge $(a_i, b_i)$ is directed as $b_i \rightarrow a_i$".
 » 3 months ago, # |   0 why in problem A we just sort all elements but not the last one ?
•  » » 3 months ago, # ^ |   0 You have to perform m operations . So if you do the last operation then you can't replace last element from your board regardless if it is smaller or greater than other elements.
 » 3 months ago, # |   0 In Solution Para-5 Line 3 , Why it min(cnt,....)>=2 ? Can someone please elaborate this line.
•  » » 3 months ago, # ^ |   0 refer to the last paragraph
 » 3 months ago, # | ← Rev. 3 →   +115 ;_;
•  » » 3 months ago, # ^ |   +68 Thank you very much for the round, I enjoyed it very much and will also remember it for very long as the round I reached gm! I liked the problems very much, especially problem D. The underlying idea was very cute and unexpected, I wish to see such problems more often
•  » » 3 months ago, # ^ |   0 Why are you leaving CP?
•  » » » 3 months ago, # ^ |   0 Graduated from university and no longer have the opportunity to participate in the ICPC, so I will not keep training for a long time anymore.
 » 3 months ago, # |   0 Hi, I have two questions related to editorial for Problem C."Yes" condition: "every prime $p$ should divides at most one $b_i$" Question 1: so, do I correctly understand, that, instead of checking Yes, we are checking No?So, "No" condition is next:There is a prime number $p$ for which there are two elements $a_i$ and $a_j$ such $(a_i+x)\equiv 0\text{ } (\text{mod }p)$ and $(a_j+x) \equiv 0\text{ }(\text{mod }p)$ for any positive integer $x$.By subtraction two equations we have: $a_i \equiv a_j \text{ }(\text{mod }p)$.Question 2: do we need just to check for given $p$ if two elements have same remainder modulo $p$? I mean, that if we can find such $p$ and such two elements then answer is No?If so, then it contradicts with next statement in editorial: If $\text{min}(\text{cnt}_0,\text{cnt}_1,…,\text{cnt}_{p−1}) \ge 2$, we output NO immediately. Because it should be $\text{max}(\text{cnt}_0,\text{cnt}_1,…,\text{cnt}_{p−1}) \ge 2$ instead of $\text{min}(\text{cnt}_0,\text{cnt}_1,…,\text{cnt}_{p−1}) \ge 2$.Or I am unable to understand the logic why $\text{min}$ is used instead of $\text{max}$.
•  » » 3 months ago, # ^ | ← Rev. 3 →   0 $a_i \equiv a_j \pmod p$ means a slot in bucket $cnt$ is banned, but maybe other slots are still available.For a bucket like $\mathit{cnt} = [111, 222, 1, 333, 444]$, although $\max = 444$, we have $\min = \mathit{cnt}_2 = 1$, so we can keep $x \equiv 3 \pmod 5$ to get a proper $x$ such that "$5$ should divide at most one $b_i$" holds.
•  » » » 3 months ago, # ^ |   0 I'm sorry, but I don't understand...Consider smaller example instead of $cnt=[111,222,1,333,444]$, just $cnt=[2,2,1,2,2]$.Array $a=[5,10,6,11,7,8,13,9,14]$ gives such $cnt$ modulo $5$. You are saying that you can choose $x \equiv 3\text{ }\left(\text{mod }5\right)$. OK, but with $x = 3$ we have $b=[8,13,9,14,10,11,16,12,17]$. But $gcd(14,10)=2$, so, $x = 3$ is a wrong number.
•  » » » » 3 months ago, # ^ | ← Rev. 4 →   0 This NO is caused by prime $2$ instead of prime $5$. Only if condition $\min(\mathit{cnt}) \leq 2$ holds for each prime, we output YES. For example, $a = [6, 12, 18, 24, 30, 36, 48, 54, 60]$ and $x = 13$ (if we set $x \equiv 1 \pmod 2$, $x \equiv 1 \pmod 3$ and $x \equiv 3 \pmod 5$).
•  » » » » » 3 months ago, # ^ |   0 If we are able to find a prime number such that count of any of its remainder is 1 than ans should be yes and why do we need to check for other primes?we are considering the cases after adding the value x. so in that sense why we need to take the modulo we assumed that we have added x but the modulo we have taken is not representing itI am really confused on how the solution workedIf possible please breakdown a test case into small pieces, I tried it but got messed upAlso please link similar problems(if any)
•  » » » » » » 3 months ago, # ^ |   0 From "We are able to find a prime number such that count of any of its remainder is 1", we can only derive that it's possible to choose a proper $x$ such that $p$ won't divide two or more of $b_i$. But we don't know if it holds for other primes.
•  » » » » » » » 3 months ago, # ^ |   0 Consider the test-case, n=4 a={8,9,11,13}if p=2 we have cnt={1,3} if p=3 we have cnt={1,1,2}so usnig CRT we will find the solution for x=0 (%2) x=0 (%3) || x=1 (%3) so we can get a solution as x=6 here since we can not have solution with x=1(%3) so how can we say for other cases if we only had equations(given below)a solution will exist x=0 (%2) x=1 (%3) since in above test case if we only considered these 2 equations there will not be a possible solution
•  » » » » » » » » 3 months ago, # ^ |   0 CRT always can give you solutions as long as you input correct congruence equations. A solution for "x=0 (%2) x=1 (%3)" is $x = 4$.
•  » » » 2 months ago, # ^ |   0 How does a single slot verify we can have different values for all numbers giving different remainders.
•  » » » » 2 months ago, # ^ |   0 CRT. Different prime numbers won't affect each other.
•  » » 3 months ago, # ^ |   0 When $a_1 \bmod p = a_2 \bmod p = c$, $x$ should not be $(p - c) \bmod p$. (Because if $x\equiv (p-c){\pmod {p}}$, just like $x=p-c$, then $(a_1 + x) \bmod p = (a_2+x)\bmod p = 0$, which means $a_1+x$ and $a_2+x$ at least have one same factor $p$ and $\gcd(a_1+x,a_2+x)\not = 1$.)The constraints are $x\not = c$, where $c$ is that at least there is a pair of $a_i$ and $a_j$ that meets $a_i \bmod p = a_j \bmod p=c$. So if there is one of the counts of $a_i \bmod p$ that is less than $2$, we can get equation $x \equiv (a_i \bmod p) \pmod p$. For all $p$, we can get a group of equations. Because there is no limitation on $x$, anyway we can solve one $x$ by CRT or other ways.
 » 3 months ago, # |   +22 Good contest but why were the samples so weak ?
•  » » 3 months ago, # ^ |   +10 Too strong samples will imply correct solutions. I hope we have set it basically properly.
 » 3 months ago, # | ← Rev. 8 →   +63 Gonna post my solution to F because some people say it is easier to understand and it does not require Kummer's theorem and Vandermonde's identityInstead of dealing with the condition of or-sum being $y$ directly, we aim to find solutions to $A_1|A_2|A_3|\ldots|A_n \subseteq y'$, for all $y' \subseteq y$. And use PIE to get the actual answer.Focus on a single value of $y'$. $A_1|A_2|A_3|\ldots|A_n \subseteq y'$ can be represented as $A_i \subseteq y'$. Let $C$ be the array of toggled bits in $y'$ copied $n$ times. Then we can represent this as finding the parity of the number of solutions to $\sum B_i \cdot 2^{C_i}=x$, where $B_i$ can be chosen to be either $0$ or $1$. This is for because each bit inside $y'$, we have a choice to turn it on or off for elements of $A$. And we want to count the number of such ways to do that, which leads to us solving the above problem. This is a giant subset sum problem that is not feasible to solve, so let us instead try to make some observations about it.Suppose that $C_a=C_b$, then we will perform the operation $\text{swap}(B_a,B_b)$. This operation is an involution over all solutions to $B$. The parity of the number of solutions is equivalent to the parity of the number of fixed points of the involution. elaborationConsider the solutions of $B$ as vertices of a graph. We will add a directed edge from solution $B_1$ to $B_2$ if $B_2$ is obtained by swapping $B_{1,a}$ and $B_{1,b}$. Now, each vertex has exactly $1$ outgoing edge.Notice that if we traverse the edges twice, we will end up back at the same vertex since swapping $B_a$ and $B_b$ twice does nothing. Therefore, each connected component of the graph either looks like $a$ with a self-loop to itself or $a \leftrightarrow b$.If we delete all connected components of the form $a \leftrightarrow b$, the parity of the number of vertices does not change since we deleted an even number of vertices. The number of vertices that are self-loop components are those where swapping $B_a$ and $B_b$ changes nothing. That is, those solutions where $B_a=B_b$. update: alternate interpretationWe want to find the value of $[x^k] \prod (1+x^{2^{C_i}})$ under mod $2$. Realize that $(1+x^{2^k})=(1+x)^{2^k}$. Therefore, $\prod (1+x^{2^{C_i}}) = \prod\limits (1+x)^{2^{C_i}} = (1+x)^{\sum 2^{C_i}}$. Finding $[x^k] \ (1+x)^z$ under mod $2$ is easy.Therefore, we should only consider solutions where $B_a=B_b$. However, since $C_a=C_b$, it is equivalent to deleting $C_a$ and $C_b$ and adding $C_a+1$ instead. If we continue this process until there are no duplicate elements in $C$, $C$ would end up being the toggled bits of $ny'$.Note that it is sufficient to calculate the total xor of $A_i$ over all valid arrays for any $i$ since this value is same for all $i$.So the total xor of element $A_i$ is $\bigoplus\limits_{y' \subseteq y} \bigoplus\limits_{\substack{v \in y' \\ (x-v) \subseteq (n-1)y'}} v$.Actually, we can focus on parity that some bit is contained in $A_i$. So solutions to $\bigoplus\limits_{y' \subseteq y} \bigoplus\limits_{\substack{bit \in y' \\ (x-bit) \subseteq ny'-bit}} bit$. This achieves $O(y \log y)$ complexity.Do remember to output $0$ if $n$ is even as we only calculated the contribution of a single element of $A$.
 » 3 months ago, # |   0 Problem A is amazing. I wasn't able to solve any questions. :(
 » 3 months ago, # | ← Rev. 4 →   +15 This is how I solved F — Here goes my solution to F, few people find it easier than understanding involution etcFirstly, $C(N,R)$ odd, if and only if $R$ is a subset of $N$. This comes from lucas theorem.This is the only pre-requisite one need for solving this problem. Let's assume that $N$ is odd; otherwise answer is just zero.Let the on bits in $Y$ be $b_1,b_2,...b_k$ (powers of 2).Now we can write $a_1+..+a_n = x$ as $c_1*b_1+c_2*b_2+...+c_k*b_k=X$, where $1 \le c_j \le n$.Once we have fixed a particular set of $c_1,c_2,...c_k$, no of ways to chose such $a_i$ is $T=C(n,c_1) * C(n,c_2) * .... * C(n,c_k)$If T is odd, it adds all bits $b_j$ where $c_j$ is odd.One necessary condition for $T$ to be odd is each $C(n,c_i)$ is odd, implying $c_i$ is a subset of $n$. Let $d_1, d_2, ..., d_l$ (powers of 2) be the bits of $n$. We can also split each $c_i$ in these bits. Namely,$c_i = e_{i,1} d_1 + e_{i,2} d_2 + ..... + e_{i,l} d_l$. Now, $X$ can be written as $X= \sum e_{i,j} b_i d_j$.Let's call this multiset of powers of 2, whose subset we should pick to form $X$, $S$. Namely,$S = (b_i* d_j )$ for all $1 \le i \le k$ and $1 \le j \le l$I will leave this $S$ and come back to it later. The necessary and sufficient conditions for OR $Y$ is- At least one among each $e_{i,1}, e_{i,2}, ..., e_{i,l}$ is one, because we want $c_i \ge 1$Since $N$ is the odd, one among $d_1, d_2, ..., d_l$ is $1$, lets assume $d_1 = 1$.Note that total xor has a contribution from $b_i$ only if $e_{i,1}$ is 1.$Y_1,Y_2,...Y_m$ be the subsets of $Y$. Instead of finding total XOR when OR is $Y$. Let's find total XOR when OR is a subset of $Y_o$ for each $1 \le o \le m$.EOD, we can use PIE on these to find the total XOR when OR is exactly $Y$. Let's count the contribution of each $b_i$ when OR is subset of $y_j$.$e_{i,1}$ must be 1, $b_i$ should be present in subset of $y_j$.We can change this problem to an earlier defined problem, where we will have to find sum $X$,using a subset bit of $b$ which forms $y_j$ and $d$ namely multiset $S'$, with the only condition that $e_{i,1}$ must be $1$. To simplify things, we can remove $b_i*d_1$ from $S'$ (let's call this multiset $T$) and find the sum $X' = X-b_i$. Now, our original problem has been reduced to counting the no of subsets in multiset $T$, which sum $X'$, the only thing we are interested in is if it's odd or not. Let $T = T_1, T_2, T_3,...$ be the multiset, if it contains two values $T_i = T_j$,then no of ways with sum $X'$ when coefficient of $T_i$ as $1$ and $T_j$ as $0$ is equal to no of ways with sum $X'$ when coefficient of $T_i$ as $0$ and $T_j$ as $1$.These ways cancel each other out, and we are left with finding no of ways when both coefficients are either $0$ or $1$.For these, we can remove $T_i=T_j$ from multiset $T$ and replace it with $2*T_i$.We can keep repeating this exercise until all the elements in $T$ are unique.When this happens, $T$ will be nothing but a binary representation of the sum of all values in $T$.Then to check if $X'$ can be formed using values present in $T$ is just checking if $X'$ is a subset of $T$. Overall we will have to find the contribution for each bit in each subset of $Y$, and that can be computed in $O(1)$.Overall time complexity $O(Y*logY)$.
 » 3 months ago, # |   +13 Chinese Reminder Theorem. -> Chinese Remainder Theorem
•  » » 3 months ago, # ^ |   0 Thanks for correcting and it's fixed now.
 » 3 months ago, # | ← Rev. 2 →   +13 In $C$, I understand why for each prime $p$ there must be least one $0 \le v < p$ where $a_i \equiv v$ mod $p$ occurs at most once. I also understand that if the previous condition is satisfied, for any set of primes, for each $p$ of them we can choose $0 \le v < p$ where $a_i \equiv v$ mod $p$ occurs at most once and construct $x$ that satisfies the congruences $x\equiv -v$ mod $p$ using Chinese remainder theorem, i.e., to make every $p$ divides at most one $a_i+x$ .But what guarantees that after choosing a set of primes we will not end up with a new prime $p_{new}$ by which some $a_i+x$ and $a_j+x$ will be divisible? and if we include $p_{new}$, what guarantees that another newer prime will not appear and continue like this indefinitely? We already know a trivial case that causes this, i.e., when we have $a_i = a_j$. But what guarantees there are no other cases that can cause this?
•  » » 3 months ago, # ^ |   0 Instead of chosing $a_i \equiv v$ mod $p$. You should choose $v \equiv -a_i$ mod $p$. This will ensure that for each prime p, there exists atmax one such $a_i + x \equiv 0$ mod $p$ for each prime $p$.
•  » » » 3 months ago, # ^ | ← Rev. 3 →   +8 Yes I understand how we should choose the moduli for a set of primes to ensure every prime of them divides at most one $a_i+x$, but this is not my question.My question is why is it guaranteed that after doing this for any set of primes there will not always appear another prime that was not in the set and will divide some $a_i+x$ and $a_j+x$.A trivial example for this is an array of $2$ values with $a_1=a_2=v$. For any set $S$ of primes we can create an $x$ such that no prime of them divides $v$, but we will always end up with a prime that was not in $S$ and divides $v$ ($a_1$ and $a_2$). So the question is, apart from an arbitrary array with some $a_i=a_j$, what guarantees that there are no other cases that can cause this?
•  » » 3 months ago, # ^ |   +1 It looks like the answer of my question is here.Any prime that divides any $2$ values divides their difference as well. The difference between any $a_i$ and $a_j$ will still be the same after adding $x$ to both. This means we have an upper bound for the primes that can divide any $a_i+x$ and $a_j+x$ as long as $a_i$ and $a_j$ are different. When $a_i=a_j$, no upper bound exists as any prime divides $0$.
 » 3 months ago, # |   +5 Why BenQ uses Rust for solving H in Goodbye 2022 contest? Is there any benefits over C++?
 » 3 months ago, # |   0 so where can I find the Chinese tutorial
•  » » 3 months ago, # ^ |   0 It's available now, sorry for being late.
 » 3 months ago, # | ← Rev. 2 →   0 In Problem C you didn't use the condition "all $a_i$ are different". So why do I have to check the trivial NO? What makes the solution incorrect when some $a_i$ are the same?This is what confuses me when I come up with this solution.
•  » » 3 months ago, # ^ |   0 https://codeforces.com/blog/entry/110754?#comment-986999above argument fails when ai=aj
 » 3 months ago, # |   0 Problem A can also be done by priority queue (using Min Heap)
•  » » 3 months ago, # ^ |   0 No need actually, sorting is enough.
 » 3 months ago, # |   0 My solution for problem D is giving tle can anybody find the tc or error. My solution
 » 3 months ago, # |   +60 I have another idea for H. First we solve by hand for $p_i=q_i=n-i+1$, it is easy using idea for $n=2$. Now whenever $p_i>p_{i+1}$, the corresponding paths must intersect and so you can untangle them and swap $p_i$ and $p_{i+1}$. So we can just do bubble sort and do $O(n^2)$ such subroutines to modify into correct $p$. Same idea for fixing $q$. Thanks for the contest, very interesting problems.
•  » » 3 months ago, # ^ |   0 Can you elaborate your idea in more detail?
 » 3 months ago, # |   0 how to prove that [n,1,n-1,2,n-2,3,n-3,4,....] is the optimal solution for B ??
•  » » 3 months ago, # ^ |   +9 the lower bound of the cost is $n+1$ (we cannot do better than that) $[n,1,n-1,\dots]$ has cost $n+1$ (we hit the limit)
•  » » » 3 months ago, # ^ |   0 got it , thank you :)
 » 3 months ago, # |   0 Problem G has such a simple statement. It seems so unexpectedly hard to me. Seems a really nice problem, gonna try it when I reach red.
 » 3 months ago, # |   +8 Why is the greedy strategy for question A correct? Is there any proof of the correctness of the first solution or the second?
•  » » 3 months ago, # ^ |   +8 I added a short explanation about the sorting approach — hope that helps!
 » 3 months ago, # |   +10 Really a nice contest for last of 2022.
 » 3 months ago, # |   0 Felt really pumped after solving the first 2 but I had no clue about the third. Feels like I need to solve more prime number problems.
 » 3 months ago, # |   -10 I think the Problem A was harder than B. Don't know but the attempts apart from using Priority Queue failed (much similar approaches were tried in the contest).
 » 3 months ago, # |   +5 For E, is the expression for updating the probabilities very intuitive? I mean, mathematically, I got the expression but not sure if there is some obvious way to state that both probabilities will become (Pu + Pv)/2
•  » » 3 months ago, # ^ |   0 Actually, we can consider the move operation as "swap or don't swap with both $\frac 1 2$ probability", no matter whether $u$ and $v$ are occupied or not. Therefore, $p_{\mathit{new}} = \frac {p_u+p_v} {2}$.
•  » » » 3 months ago, # ^ |   0 How do you prove that probability of swapping is equal to $1 \over 2$?
•  » » » » 3 months ago, # ^ |   0 just simple case-analysis for all $4$ cases. (node $u$ / $v$ occupied or not)
 » 3 months ago, # | ← Rev. 2 →   +1 In E, why isn't (or I just didn't see in code) $sum_u$ updated while calculating the contribution each edge gives to the final answer, when $p_u$ was changing?
•  » » 3 months ago, # ^ |   0 Because it's not changing.Each edge split the tree into two components, and you can see that a butterfly cannot fly from one component to the other before the operation on this edge.
•  » » » 3 months ago, # ^ |   0 Got it. Very thanks :)
•  » » 3 months ago, # ^ |   0 Please ensure that you have gotten why we claim $|\mathit{siz}_{\mathit{son}} - \mathit{siz}^0_{\mathit{son}}| \leq 1$ before think about later parts.
•  » » » 3 months ago, # ^ |   0 Thanks >_- I was thinking too complicatedly.
•  » » 3 months ago, # ^ |   0 I think the butterflies don't cross that edge.
•  » » » 3 months ago, # ^ |   0 That's the very point.
 » 3 months ago, # |   0 In Problem-C,In the min case, cnt[i]=2 for every 0 <= i < p where p is a prime number. So, 2*P=n tends to P = floor of n/2. That is also proved by Pigeonhole principle.
 » 3 months ago, # |   0 in problem C can you find such x for yes
•  » » 3 months ago, # ^ |   0 It is theoretically possible by using CRT as the editorial mentioned, but the result may be very large.
•  » » » 3 months ago, # ^ |   0 Could you please explain how theoretically it is possible to use CRT? For some Prime P1, we need x1 to be added in the array to make at most 1 element divisible by P1, but how to find x so that at most 1 element is divisible by all primes smaller than n/2?
•  » » » » 3 months ago, # ^ |   0 solve congruence equations like: $x \equiv x_1 \pmod {p_1} \\ x \equiv x_2 \pmod {p_2} \\ \dots$
•  » » » » » 3 months ago, # ^ |   -10 Got it. Thank you!
 » 3 months ago, # |   0 In question C If min(cnt)<2 holds for all primes, then we can list certain congruence equations and use Chinese Reminder Theorem to calculate a proper x I don't want to go to too many details on how to find x but can someone explain why the Chinese Remainder Theorm can be used here?
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 CRT is used to solve congruence equations, for example, CRT tell us "$x = 13$ is a solution" if we set $x \equiv 1 \pmod 2$, $x \equiv 1 \pmod 3$ and $x \equiv 3 \pmod 5$.
»
3 months ago, # |
-29

what's wrong with my code for problem A: Koxia and Whiteboards

# include

using namespace std;

# define ll long long int

const unsigned int mod = 1e9+7;

int main(){

ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//this is fast I/O (inputput output) use header file <cstdio>
ll t;cin>>t;
while(t--){
ll n,m; cin>>n>>m;
vector<ll>a(n),b(m);
for(int i=0; i<n; i++) cin>>a[i];
for(int i=0; i<m; i++) cin>>b[i];
sort(a.begin(),a.end());
sort(b.begin(),b.end(),greater<int>());
if(m==1){
ll sum = b[0];
for(int i=1; i<n; i++) sum+=a[i];
cout<<sum<<endl;
continue;
}
if(n>m){
// no problem
int flag = 0;
for(int i=0; i<m; i++){
if(a[i]<b[i]) {
flag = 1;           // there is atleast 1 swap
a[i]=b[i];
}
}
if(flag == 0)       // if there is no swap (i.e all elements of b are smaller than a)
a[0]=b[0];
ll sum = 0;
for(auto it:a) sum+=it;
cout<<sum<<endl;
}
else{
// here m>n
int flag = 0;
for(int i=0; i<n; i++){
if(a[i]<b[i]) {
flag = 1;           //there is atleast 1 swap
a[i]=b[i];
}
}
if(flag == 0)             //if there is no swap(i.e all element of b are smaller than a)
a[0]=b[0];
ll sum = 0;
for(auto it:a) sum+=it;
cout<<sum<<endl;
}
//ll sum = 0;
//for(int i=0; i<n; i++) sum+=a[i];
//cout<<sum<<endl;
}
return 0;

}

 » 3 months ago, # | ← Rev. 3 →   0 1770A KOXIA AND WHITEBOARDS - Koxia and Whiteboards can someone point out my mistake in the given code. Thanks in advance. 187386373t = int(input()) for _ in range(t): n, m = map(int, input().split()) a = [int(x) for x in input().split()] b = [int(x) for x in input().split()] a.sort() b.sort() ans = b[-1] k = a[1:] + b[:m-1] k.sort() ans += sum(k[m-1:]) print(ans)
 » 3 months ago, # |   +8 In problem D I have considered bipartite graph from number to position, the solution is very similar actually. To verify feasibility of assignment, we check that each connected component contains the same amount of numbers and places.
 » 3 months ago, # |   0 For D, what was the intuition to set up the graph like so? I've gotten the 2 lemmas but I couldn't figure out how to set up the graph like that. If anyone can provide some insight, that would be great.
•  » » 3 months ago, # ^ |   0 Refer to https://codeforces.com/blog/entry/110754?#comment-987007. Honestly it needs some inspiration or experience.
•  » » » 3 months ago, # ^ |   0 Thanks! I understood that after looking at the editorial, just couldn't figure out how to model it as a graph before reading the editorial. Might just need to practice more I think.
 » 3 months ago, # |   0 can anybody please explain what hints towards using graph in problem D? Is there so observable pattern?
 » 3 months ago, # |   0 Can someone please explain how D problem is converted to a graph problem? Like what exactly are the edges and the vertices in the said graph? Thanks in advance :)Following is my approach, please correct me if I am wrong (I think it would TLE anyway tbh)I could figure out lemma 1 and lemma 2 by myself and thought that I can make a directed graph by taking the elements in array a and b as vertices and every a[i] and b[i] connected to a[i+1] and b[i+1] except the last node. Then I traverse through this graph twice and check if I can create a path with unique vertices and reach the terminal node (i.e. check if P is a permutation) one path starting from a1 and the other from b1. Every node is marked 1 if a path through the node exists or 0 other wise. Now we can check for every (a[i], b[i]): if a[i] and b[i] are both marked 1 and if they are equal that means a path through both the vertices exists and any of them can be chosen during that round (i.e. c[i] can be anything so multiplying answer with n) if they both are marked 1 but are not equal then c[i] can only take 2 values in that round (so multiplying answer with 2) if only one of them is marked 1 then c[i] can only take that one value so multiplying answer with 1 else no path exists so the answer is multiplied with 0
•  » » 3 months ago, # ^ |   0 Refer to https://codeforces.com/blog/entry/110754?#comment-987007. They're not really for some clear meanings, but we can claim 2 problems are equivalent and this is enough.
 » 3 months ago, # |   0 2 2 109 111 119 110for this solution Answer is 229 by editorial solution But the answer is 230
•  » » 3 months ago, # ^ |   0 You have to apply all $m$ operations sequentially.
•  » » » 3 months ago, # ^ |   0 thanks I understand
 » 3 months ago, # |   0 Can anyone explain the logic behind only taking prime numbers upon n/2 in problem C?
•  » » 3 months ago, # ^ |   0 pegion hole ! for primes over n / 2 there exists an r < p where cnt[r] < 2 (cnt[x] = number of array elements that have reminder x when devided by p)
 » 3 months ago, # | ← Rev. 3 →   0 In E, what is inv2? And why do we multiply delta by it?UPD: Ok, inv2 means division by 2, but why do we divide delta by 2?
•  » » 3 months ago, # ^ |   0 If we use delta, it means we apply the move operation always, no matter the direction of edges. But actually, it's randomly chosen from two directions.
 » 3 months ago, # |   0 In D, what does "if (edge != 2 * vertex) ans = 0;" this implies?
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 Refer to the editorial (Paragraph "We can transform this into a graph problem..."). We need to check whether $|V| = |E|$ or not.
 » 3 months ago, # |   0 in problem cgiven the input a = [5, 7], then [5 mod 2, 7 mod 2] = [1, 1]. 1 appears twice so the minimum multiplicity is equal to 2. Above in paragraph 3 you say print NO. if x=2,then the gcd(5+2, 7+2) = gcd(7, 9) = 1. Isn't it wrong to print no while there is an x for which gcd(a_{1}+x, a_{2}+x) = 1.I'm probably wrong I just want someone to explain how.
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 1 appears twice but 0 doesn't appear, so the minimum multiplicity is $0$ instead of $2$.
•  » » » 3 months ago, # ^ |   0 thank you.
 » 3 months ago, # |   0 I had not attended the contest but found problem A quite hard
 » 3 months ago, # |   0 can anyone please post link of the classical problem mentioned in hint 1 of problem E
 » 3 months ago, # |   0 Can someone provide a easir explanation for problem C
 » 3 months ago, # | ← Rev. 3 →   0 Do you feel this contest funny?
 » 3 months ago, # |   0 in problem D why edge!=2*vertex
•  » » 3 months ago, # ^ |   0 Scroll up the mouse wheel a few times to see.
 » 3 months ago, # |   0 Can somebody explain how the sigma pi formula came in F’s editorial and how did this helped in solving the problem. As we are not interested in number of sequences but xor of such ones. Moreover $\binom{ny}{x}$ is the solution of equation $t_1 + t_2 + … + t_n = x$ where each $t_i$ can take any value between 0 and y by Vandermode identity, then how are we ensuring that each $t_i$ is also subset of y?
•  » » 3 months ago, # ^ |   0 We can't ensure that each $t_i$ is a subset of $y$ so we need inclusion-exclusion principle (Hint 4).
 » 3 months ago, # |   0 Can someone explains why in problem C, we only consider prime number ?
•  » » 3 months ago, # ^ |   0 nvm i got it
 » 3 months ago, # |   0 In problem C, we only need to iterate through all prime numbers, then why are we checking for each number from 2 to n/2 ??
•  » » 3 months ago, # ^ |   -8 checking prime numbers in $[2, \lfloor \frac{n}{2} \rfloor]$ is enough, I just got lazy to sieve prime numbers when implementing it.
 » 3 months ago, # |   0 Hi!I am wondering, for problem C, is it equivalent to check all integers up to $\lfloor n/2 \rfloor$ instead of primes? The criterion for NO is exactly the same. And for the existence of $x$, we could also create the equations in the same way, (in which the modulo may not be pairwisely coprime, but we can always convert it to one that is), and use CRT to solve it.Actually, I think checking integers is more essential, right?
•  » » 3 months ago, # ^ |   0 checking prime numbers in $[2, \lfloor \frac{n}{2} \rfloor]$ is enough, I just got lazy to sieve prime numbers when implementing it.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 So instead of using primes upto u/2 -> how traversing all numbers upto n/2 won't change our answer ?I mean can you prove ?
•  » » » » 2 months ago, # ^ |   0 like if you run out slots when checking $6$, then you must run out slot when checking $2$ or $3$, so it's redundant to check composite numbers.
•  » » » » » 2 months ago, # ^ |   0 ok ok i got that like if 2 and 3 are dividing at most one numbers then obviously 6 will divide at most one number.
 » 3 months ago, # |   0 Can anyone explain the problem D why we build the graph like this and why we can find the answer by assigning directions for each edge? I can't imagine how it works
 » 3 months ago, # |   0 Can anybody explain how Chinese Remainder Theorem is used in Problem C? and in Chinese remainder theorem,if x%p1=k1, x%p2=k2, x%p3=k3, x%p4=k4 according to theorem p1, p2, p3, p4 are pairwise co prime then what is the use of p1, p2, p3, p4 to be relatively co prime?
 » 2 months ago, # | ← Rev. 2 →   0 gr8
 » 2 months ago, # |   0 How to get the x if it exist for Problem B by using CRT? what's the mod function?
•  » » 2 months ago, # ^ |   0 mod is % in C++; CRT is https://oi-wiki.org/math/number-theory/crt/
•  » » » 2 months ago, # ^ |   0 In the problem C , why we are checking prime numbers only
•  » » » » 2 months ago, # ^ |   0
•  » » » » » 2 months ago, # ^ |   0 Got it , thanks
 » 2 months ago, # |   0 My greedy solution to problem A: 190982238