MateoCV's blog

Codeforces Round #774 (Div. 2) Editorial
By MateoCV, history, 3 years ago, In English

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

1646A - Square Counting

Solution
Code

1646B - Quality vs Quantity

Solution
Additional comment
Code

1646C - Factorials and Powers of Two

Solution
Additional comment
Code

1646D - Weight the Tree

Solution
Code

1646E - Power Board

Solution
Additional comment
Code

1646F - Playing Around the Table

Solution
Code

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

  • Vote: I like it
  • +136
  • Vote: I do not like it

Comments Comments (58)
| Write comment?
»
3 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it +3 Vote: I do not like it

    a

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      i used the sort() function and it didn't give me any TLE in C++

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        C++ sort() always works in $$$O(NlogN)$$$, while Java's Arrays.sort() has a worst case time complexity of $$$O(N^2)$$$.

        → Reply
»
3 years ago, # |
  Vote: I like it +36 Vote: I do not like it

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

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

→ Reply
»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +53 Vote: I do not like it

    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

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    D's editorial seems fine , If someone has at least tried the problem He/She will be completely able to connect here ..

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    where do you need math in D editorial?

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Failed C system tests with the correct solution using pypy :(

→ Reply
»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +25 Vote: I do not like it

E can also be solved with the inclusion-exclusion principle and also works with large $$$m$$$. 148397426

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain why I am getting TLE in C?

My solution is: https://codeforces.me/contest/1646/submission/148397036

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Most likely quite late already,

    But it fails because you are using int for 'i1' and looping until it reaches 1e12, while INT_MAX is 2^31 = ~2.147B = ~2*1e9.

    There might be some other conditions to make it fail, but I checked only until this, since this should fail it already.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Don't know why my solution Math.floor(s/(n*n)) in JavaScript didn't work for Problem A, anybody know y?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Additional for problem E :- I used inclusion-exclusion and it will work for m<=1e18 https://codeforces.me/contest/1646/submission/148374136

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

yay, editorial!!!

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Try this case 1 768

    Answer should be 2 :) Tried greedy for complete two hours.

    → Reply
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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)
→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Mulitply with -1LL wherever u want to negate.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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 ^_^

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Method size() returns an unsigned int, which is casted to signed by the second expression, but not the first.

        → Reply
»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

I made video Solutions for A-D in case someone is interested.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve the Additional comment of Problem E? I need help.

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +16 Vote: I do not like it

    I was having a hard time understanding PIE solutions but I think I figured it out, heres my explanation

    Following 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

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Why does greedy fail in problem C?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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<<ans<<nl; This is giving me wrong answer

But when I submit below code It is working fine lli n,m; cin>>n>>m; lli ans=m/(n*n); cout<<ans<<nl;

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problems C, what does __builtin_clzll() and __builtin_popcountll() do? Help O:

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    __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().

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could anybody explain the logic behind problem C? thanks in advance!!

→ Reply
»
3 years ago, # |
← Rev. 4   Vote: I like it +10 Vote: I do not like it

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?

Mircea

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

hey in problem b suppose we have two 10s does that mean count of 10s is 1?

→ Reply