MateoCV's blog

By MateoCV, history, 7 months 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

»
7 months 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.

  • »
    »
    7 months ago, # ^ |
    Rev. 3   Vote: I like it +3 Vote: I do not like it

    a

    • »
      »
      »
      7 months 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++

      • »
        »
        »
        »
        7 months 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)$$$.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeah that happened to me a couple of months ago ... sad story :(

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    same bro ,this is so unfair for someone like me(noob). I submitted it when solved count is(3k), I thought today I will get my best rank.

»
7 months 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.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hey can you tell me a small counter example where my code gives WA? contest id -> 1646 problem C submission 149901368

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Failing testcase: Ticket 2206

      Note: In case you are not aware, you can actually edit the table before clicking on "Stress Test". So, once you know that your solution works for $$$n$$$ in $$$[1, 1000]$$$ from the previous ticket, you can choose $$$n$$$ to be in range $$$[1000, 3000]$$$ in your next ticket.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Wow that's amazing.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ah, thanks. Glad to know you found it useful enough to drop a positive feedback.

»
7 months 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.

  • »
    »
    7 months 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

  • »
    »
    7 months 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 ..

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    where do you need math in D editorial?

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 months 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.

»
7 months 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

»
7 months 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.com/contest/1646/submission/148397036

  • »
    »
    4 weeks 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.

»
7 months 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?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No idea lol, I tried the same in JavaScript(Node 12), and it failed as well. I was so certain that it was the solution (well obviously it is lol), that I just rewrote it in python and submitted (completely passing). Bad luck thankfully it only cost me -50.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks, don't understand, I think now I have to start learning other languages too

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      And it made me lose so much time during d contest

  • »
    »
    7 months 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.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yh just tried it and it's try, don't even know why js works dat way

»
7 months 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!

  • »
    »
    7 months 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.

»
7 months 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.com/contest/1646/submission/148374136

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

yay, editorial!!!

»
7 months 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.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I just struggled with the if statement for 2 hours on problem A, and i couldn't solve the problem because of that, otherwise that was one shot though.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think don't try to dry-run the sample test cases. It make more confusion in sometimes

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Check this solution with binary search(148307774). I think, it's more intuitive (:

»
7 months 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

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Can you please explain this approach in more detail? How will passing the card in the j-th permutation ensure that they all will be eventually sorted?

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone plss explain problem c in detail? thanks in advance!

»
7 months 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

»
7 months 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)
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In Problem B according to Additional comment, what's wrong with this code?

#include<bits/stdc++.h>
using namespace std;
bool solve(){
  int n;
  cin>>n;
  long long int a[n];
  for(int i=0;i<n;i++){
   cin>>a[i];
  }
  sort(a,a+n);
  if(a[0]==a[n-1])
    return false;
  long long int r = 0,b=0;
  int y = (n-1)/2;
  int x = n-y;
  for(int i=0;i<x;i++){
   r+=a[i];
  }
  for(int i=x;i<n;i++){
   b+=a[i];
  }
  if(r<b)
    return true;
  return false;
}
int main(){
 int t;
 cin>>t;
 while(t--){
   if(solve())
     cout<<"Yes"<<endl;
    else
     cout<<"No"<<endl;
 }
}

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Check for the array [ 1, 1, 0, 0]

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah, I got the test cases where it will fail, but according to additional comments the code should work, but it's not... anything I misunderstood?

»
7 months 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

»
7 months 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

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Mulitply with -1LL wherever u want to negate.

    • »
      »
      »
      7 months 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 ^_^

      • »
        »
        »
        »
        7 months 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.

»
7 months ago, # |
  Vote: I like it +2 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 months 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

    • »
      »
      »
      7 months 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.

    • »
      »
      »
      7 months 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.

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can someone tell me what's the problem with writing the condition in the for loop in B as I've written in this submission https://codeforces.com/contest/1646/submission/148329479 Output was correct in my compiler but it was giving wrong answer for the first input in the example when I submitted

»
7 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Why does greedy fail in problem C?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think Greedy guarantee correct answer if a number in set can't be made by summing up all smaller numbers . not so sure though

»
7 months 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?

  • »
    »
    7 months 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.

»
7 months 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;

  • »
    »
    7 months 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.

»
7 months 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

  • »
    »
    7 months 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.

»
7 months 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:

  • »
    »
    7 months 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().

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 months 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).

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

![ ](problem C 是个好题目)

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem C, i have calculated all factorial and power of 2 less than or equal n, if equal n then ans is 1. if not then is there any way to find minimum k for these arrays as their size is not that big.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For Problem E, my algorithm went through each row and figured out, using lcm, which elements were common. I used brute force to test my code up 143*144, at which point the brute force was having too many infinities to work. I submitted it and it is not working for case 4. https://codeforces.com/contest/1646/submission/151007482

»
6 months 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?

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

[problem:b]

please help what's wrong with this solution?

for(int i = 0; i < n; i ++){
        cin >> arr[i];
    }
    vector<long long> pref(n + 1);

    for (int i = 0; i <=n ; i ++){
        pref[i] = 0;
    }
    sort(arr, arr + n, greater<int>());
    for (int i = 1; i <=n ; i ++){
        pref[i] = pref[i-1]+arr[i-1];
    }


    int l;
    if (n&1) l = n / 2;
    else l = n/2-1;

    if (pref[l] > (pref[n] - pref[l]) ) cout << "YES";
    else cout << "NO";
»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

loved C , learnt a lot thank you so much :D