### MateoCV's blog

By MateoCV, history, 19 months ago,

Thanks for participating in the round! I hope you enjoyed the problems!

1646A - Square Counting

Solution
Code

1646B - Quality vs Quantity

Solution
Code

1646C - Factorials and Powers of Two

Solution
Code

1646D - Weight the Tree

Solution
Code

1646E - Power Board

Solution
Code

1646F - Playing Around the Table

Solution
Code

Additionally, ak2006 has made video editorials for problems B, C and D.

• +136

| Write comment?
 » 19 months ago, # |   +12 For Problem B, in Java, Arrays.sort(a) method got TLE for int[], and it worked for Integer[]. Wasted more than an hour, without realising this :( , due to different algorithms used in the sorting methods.
•  » » 19 months ago, # ^ | ← Rev. 3 →   +3 a
•  » » » 19 months ago, # ^ |   -8 i used the sort() function and it didn't give me any TLE in C++
•  » » » » 19 months ago, # ^ |   +6 C++ sort() always works in $O(NlogN)$, while Java's Arrays.sort() has a worst case time complexity of $O(N^2)$.
•  » » 3 months ago, # ^ |   0 Why is there such a difference, do you know the reason, can you Sue me, I am troubled by this problem
•  » » » 3 months ago, # ^ |   0 Check this — https://codeforces.com/blog/entry/7108
•  » » » » 3 months ago, # ^ |   0 Thank you very much
 » 19 months ago, # |   +36 If you are/were getting a WA/RE verdict on any of the problems from this contest, you can get a small counter example for your submission on cfstress.comProblems added: "A, B, C, D, E, F".If you are not able to find a counter example even after changing the parameters, reply to this thread, mentioning the contest_id, problem_index and submission_id.
•  » » 18 months ago, # ^ |   0 Wow that's amazing.
 » 19 months ago, # |   +2 Editorial to D and E feel more complecated than the problems, no great help. I think not solving D and E is caused mostly by lack of math skills. Unfortunatly same lack of math skills makes it hard to understand the editorials.
•  » » 19 months ago, # ^ |   +53 I was able to solve E, and I think it's not that difficult. Here's how I solved it 1. Two rows can produce same number if and only if we have a number d such that the two rows are d^a, d^b. 2. Let's look at rows 2,4,8, .. In row 2, we have elements 2^1, 2^2,2^3,.., 2^m In row 4, we have elements 4^1, 4^2, 4^3,..., 4^m In row 8, we have elements 8^1, 8^2, 8^3,...., 8^m Now let's rewrite these rows in base 2 2^1, 2^2, 2^3,..., 2^m 2^2, 2^4, 2^6, ..., 2^2m 2^3, 2^6, 2^9, ..... 2^3m Now let's ignore 2 and only look at powers 1,2,3,..,m 2,4,6,..,2*m 3,6,9,...,3*m 3. Let's try to write a method, which can tell us the unique values in this r*m multiplication table. 1,2,3,..,m 2,4,6,..,2*m 3,6,9,...,3*m . r,r*2,r*3,..,r*m Well even if we do a bruteforce, it is okay, because the number of rows at max will be Logn. Submission should be easy to understand 148377896
•  » » » 19 months ago, # ^ |   0 Thanks.
•  » » 19 months ago, # ^ |   +7 D's editorial seems fine , If someone has at least tried the problem He/She will be completely able to connect here ..
•  » » 19 months ago, # ^ |   +14 where do you need math in D editorial?
 » 19 months ago, # |   0 Failed C system tests with the correct solution using pypy :(
 » 19 months ago, # |   +11 This solution for problem E works for much larger values of $m$ (like $m\leq 10^{18}$). We just need to take modulo at some places.
 » 19 months ago, # | ← Rev. 2 →   +25 E can also be solved with the inclusion-exclusion principle and also works with large $m$. 148397426
•  » » 19 months ago, # ^ |   +2 can you share some resources on Inclusion-Exclusion Principle please :)
•  » » » 19 months ago, # ^ |   +8 I'm not an expert on that and this is the only English resource that I've read so far: https://cp-algorithms.com/combinatorics/inclusion-exclusion.html#the-verbal-formula.
•  » » 19 months ago, # ^ |   +60 For problem E, the same solution can be extended to work with large $n$ as well. Observe that in the part where you do the inclusion-exclusion, the only thing that matters is the $lcm$ of all the numbers. Therefore if you store only the lcm, you can get an $O(polylog(n))$ algorithm. This solution can solve the problem for $n \leq 10^{15}, m \leq 10^{18}$.Code: 148407574
 » 19 months ago, # |   0 Can someone please explain why I am getting TLE in C? My solution is: https://codeforces.com/contest/1646/submission/148397036
 » 19 months ago, # |   0 Don't know why my solution Math.floor(s/(n*n)) in JavaScript didn't work for Problem A, anybody know y?
•  » » 19 months ago, # ^ |   0 Try n = 1, s = 10^18 — 1 on your solution (it ouputs 10^18). I don't know js but obviously it's due to typing and precision errors.
 » 19 months ago, # |   0 Actually, there is no problem in repeating 1, 2, or any other power of two. This is because it can be proven that (try to prove it!) those sums are not optimal.I spent about 30 minutes in C just to add additional things to my implementation to avoid the cases where i have both 1's or 2's. If I noticed this I would probably finish this problem within 20 minutes. Thanks for the Editorial!
•  » » 19 months ago, # ^ |   0 You can consider that you are supposed to represent the number as a sum of powers of two or factorials of numbers greater than 2. In other words, don't consider 1 and 2 as factorials. This way you won't have to worry about repetition.
 » 19 months ago, # |   +6 Additional for problem E :- I used inclusion-exclusion and it will work for m<=1e18 https://codeforces.com/contest/1646/submission/148374136
 » 19 months ago, # |   0 yay, editorial!!!
 » 19 months ago, # | ← Rev. 2 →   +5 Hi I wanted to write this yesterday, but I went to sleep so I am writing it now in the hope that no one else discovered it (which should have pretty low chances)So F is from the All Russian MO. See this and if you want this as well.
 » 19 months ago, # |   +10 I had alternate solution to F during testing.First given the input, let's rearrange it in such a way that each column is a permutation of $[1,n]$, we can do this using $n$ bipartite matchings in $O(n^4)$ or $O(n^3 \sqrt n)$. This way we can already assign which card goes to which player. This reduces the problem to solving $n$ permutations of cards but doing so in parrallel, where on the $i$-th operation, player $(i+j) \% n$ will pass one of the cards in the $j$-th permutation to the next player.It is not to hard to figure how to solve a each permutation in $n(n-1)$ moves using a simple dfs.code: 148411890
 » 19 months ago, # |   0 Why doesn't greedy work in C? We always try to take the closest powerful number and compute answer. Where does it fail? Something like this 148381259
•  » » 19 months ago, # ^ |   0 Try this case 1 768Answer should be 2 :) Tried greedy for complete two hours.
 » 19 months ago, # |   +8 For D, I discovered that there was this https://courses.grainger.illinois.edu/cs473/sp2011/lectures/09_lec.pdf — but this lecture does not completely solve the problem — you still need to figure out which nodes was chosen from the tree dp. (Also, another reason I should stop using Python)
 » 19 months ago, # | ← Rev. 3 →   0 For 1646E - Power Board if we even use unordered_set in place of visited (used in editorial's code), it is giving a TLE for m=1e6. Unordered set operations are said to be O(1), right? then why that's happening or am i calculating the complexity wrong ?code
•  » » 19 months ago, # ^ |   0 https://codeforces.com/blog/entry/62393Also unordered_map gave me MLE during contest so I had to switch to vector or bitset for marking the numbers
 » 19 months ago, # |   0 my code of problem D is working fine on the local machine but giving the wrong output on OJ. Can anyone please point out my mistake? My Submission
•  » » 19 months ago, # ^ | ← Rev. 2 →   0 Mulitply with -1LL wherever u want to negate.
•  » » » 19 months ago, # ^ | ← Rev. 2 →   0 Thanks a lot, buddy. But can you please tell me why it was giving such a output? I have just changed (-graph[vertice].size()) to this (-1ll*graph[vertice].size()) and it passed ^_^
•  » » » » 19 months ago, # ^ |   0 Method size() returns an unsigned int, which is casted to signed by the second expression, but not the first.
•  » » » » » 19 months ago, # ^ |   0 thanks
 » 19 months ago, # |   +2 I made video Solutions for A-D in case someone is interested.
•  » » 19 months ago, # ^ |   +1 you are wonderful ！
 » 19 months ago, # |   0 How to solve the Additional comment of Problem E? I need help.
•  » » 19 months ago, # ^ | ← Rev. 2 →   +16 I was having a hard time understanding PIE solutions but I think I figured it out, heres my explanationFollowing the editorial the problem boils down to solving how many distinct integers are in the set $S = \{ab | 1\leq a\leq k,1\leq b\leq m \}$for an integer $x$ in $S$, let $mask(x)$ be a k bit number where the i-th bit is on iff $x = (i+1)y$ for some integer $y\leq m$. let $f(i)$ be the number of integers $x$ such that $mask(x) = i$.the final answer is $f(1) + f(2) + f(3) + \cdots + f(2^{k}-1)$ .but f is hard to compute instead we will do PIE on f using another value that we can compute easily, let $g(i)$ be the sum of $f(j)$ such that $i$ is a submask of $j$ then $f(1) + f(2) + f(3) + \cdots + f(2^{k}-1) = \sum_{n=1}^{2^{k}-1}{(-1)^{popcount(n)}g(n)}$. To compute $g(i)$, let $a_{0},a_{1},a_{2} \cdots$ be the index of the bits are on in $i$ (sorted in increasing order) then if $x$ is counted by $g(i)$, $x$ has to be divisble by $lcm(a_{0},a_{1},a_{2} \cdots)$ since $x = a_{0}b_{0} = a_{1}b_{1} = a_{2}b_{2}\cdots$. Thus $g(i)$ counts how many distinct $x$ in $S$ can be written as $lcm*y$. we can notice that $y\leq \frac{m}{lcm/a_{0}}$ thus $g(i) = \frac{m}{lcm/a_{0}}$ which can be computed in $O(k)$. Back to the original problem we can precompute and solve the above subproblem for all possible $k$ in $O(k2^{k})$ yielding a total complexity of $O(k2^{k} + n)$. $k$ is atmost $\log n$ so this runs fast enough
•  » » » 19 months ago, # ^ |   +8 Thank you very much!I have understood your explanation! PIE refers to inclusion-exclusion principle,right? (I didn't heard of this statement,but I guess it from your formula ahahahaha). Besides, On the basic of your explanation, I find an important detail during implementation: we can't do PIE simply on range[1,k*m]. it must be done in blocks:[1,m],[m+1,2*m],……,[(k-1)*m+1,k*m]. That's because divisor 1 isn't illegal in range [m+1,2*m], divisor 2 isn't legal in range[2*m+1,3*m] and so on. But the complexity din't change.
•  » » » 18 months ago, # ^ | ← Rev. 2 →   0 I'd be grateful iff you can briefly explain why $y\le m/(\frac {lcm}{a_0})$. upd: I realized soon after. first the biggest $b_i$ must belong to $a_0$,since x is the same, and for $a_0b_0$, $b_0\le m$,so $x\le a_0m$,which means $y*lcm\le a_0m$,and so on.
 » 19 months ago, # |   +1 Why does greedy fail in problem C?
 » 19 months ago, # |   0 " In case both options (making it good or not) work, you have to choose to not make it good, as you do not know if its father was good or not."How does this not affect making maximum number of good nodes?
•  » » 19 months ago, # ^ |   0 If you are constructing the answer in the subtree of x, it has to have value v and f(x,0)=f(x,1)=v (both options work), then if you choose not to make vertex x good, the maximum is not affected because f(x,0)=f(x,1), so there is a way to have the same number of good vertices.
 » 19 months ago, # |   0 Please any one explain in question 1646A Square counting When I firstly submit the code lli n,m; cin>>n>>m; lli ans=m/pow(n,2); cout<>n>>m; lli ans=m/(n*n); cout<
•  » » 19 months ago, # ^ |   0 This is because the pow function returns a floating-point number type. Using floating-point numbers in this problem could produce a wrong answer due to precision issues or because you are printing a non-integer number as the answer.
 » 19 months ago, # |   0 Can someone explain how the solution for problem A works for cases where sum/(n*n) is greater than n+1? for e.g if sum is 100 and n=4 then aforementioned solution will yield ans=6 but the size of array is just n+1(i.e 5),here's my code for this particular problem>>148312599
•  » » 19 months ago, # ^ |   0 That is because the statement says: It is guaranteed that the value of s is a valid sum for some sequence satisfying the above constraints.So, n = 4 and s = 100 is not a valid input.
 » 19 months ago, # |   0 In problems C, what does __builtin_clzll() and __builtin_popcountll() do? Help O:
•  » » 19 months ago, # ^ |   +1 __builtin_clz() returns how many leading 0s are there when writing a number in binary, and __builtin_popcount() returns how many 1s are there.For example, 5 is 101 in binary, and a int has 32 bits, so __builtin_clz(5) is 29, and __builtin_popcount(5) is 2.__builtin_clzll() is the long long version of __builtin_clz(), __builtin_clzll(5) is 61, because a long long has 64 bits. So is __builtin_popcountll().
•  » » » 19 months ago, # ^ |   0 Oh o: Thanks a lot!
 » 19 months ago, # |   0 Could anybody explain the logic behind problem C? thanks in advance!!
•  » » 19 months ago, # ^ | ← Rev. 2 →   0 Did you checked out the video of ak2006? That may be useful to you.
 » 19 months ago, # | ← Rev. 4 →   +10 Hi there! Sorry for writing in English.. Our friends from all around the world here will understand that I am tired.I am pretty sure that you can do 1646F in O(n^2) time, so better than the tutorial solution. Here's the thinking.Afiu (as far as I understand).. 1646F.. can also be done with Max-Flow right?.. So just have an 1 capacity edge between piece[player: i, card: c]--> piece[player: i+1, card: next_expected_card_after_[c]]. So there are at most O(n^2) nodes and thus with lift-to-front, you can pull O(n^6) complexity. But with simplification above — that matching "cards of player i" to "cards of player i+1" is in fact independent of matchings for [i+1, i+2] and [i-1, i], then you can do bipartite matching and get just n * O(n^3) = O(n^4).In fact, taking advantage of the fact that — for there to be a solution, you need to have all cards next[c] for all cards c for player i, as part of the cards of player i+1, then you can simplify the bipartite matching step to a simple HashMapping: next[c] --> what is the position where next[c] is found for player i+1. This way, the bipartite matching step goes down to O(n), and total running time to O(n^2) right?.. So better than the tutorial solution.What do you think about this problem-->generalization-->optimization(particularization)-->solution "simplification" of this problem to get to a better solution? Am I missing something in my argument?MirceaPs_unique. The original line of thinking was around: "Now, For 1646F — can't you get O(n^3) by simply doing an heuristic matching all the way up until you are left with just say maximum "non-solidity depth" 2 or 3 (so the maximum of the number of cards some player required to become solid)? And then just do bipartite matching — with FF flow?.. which works in O(n^3) since maximum flow is O(n) and E=O(n^2)? And in average case maybe perform as good as (n^2) since there should be around O(1) outgoing edges/card / player, no?"Ps2. So the bipartite matching in this problem, 1646F is actually a sort of bipartite "multimatching" over a set of just {1,2,..,n} semantically distinct values (elements).