change

if(n*n<m){
        cout<<"-1\n";
        return;
}

to

if(n < ceil_div(m, n)){
        cout<<"-1\n";
        return;
}

This was the edge case, thanks!

Forgot to handle self cycle.

Can't seem to get D to AC, failed 6 test cases. My idea is to label $$$2*i$$$ as blue and $$$2*i + 1$$$ as red for $$$i \in [1, n]$$$ and treat it as a graph dfs problem

vt<vt<int>> G;
vt<int> vis;

void dfs(int u, int p = -1) {
  if(vis[u])
    return;
  vis[u] = 1;
  for(auto v: G[u]) {
    if(v == p)
      continue;
    dfs(v, u);
  }
}

void solve() {
  int n, m;
  cin >> n >> m;

  G = vt<vt<int>>(2 * n);
  vis = vt<int>(2 * n);

  for(int i=0; i<n; i++) {
    int b = 2 * i, r = 2 * i + 1;
    G[b].pb(r);
    G[r].pb(b);
  }

  for(int i=0; i<m; i++) {
    int a, c;
    char b, d;
    cin >> a >> b >> c >> d, a--, c--;
    a = a * 2 + (b == 'R');
    c = c * 2 + (d == 'R');

    G[a].pb(c);
    G[c].pb(a);
  }

  int ans1 = 0, ans2 = 0;

  for(int i=0; i<n; i++) {
    int b = 2 * i, r = 2 * i + 1;
    if(vis[b] || vis[r])
      continue;

    if(!vis[r])
      swap(r, b);

    dfs(b, r);
    if(vis[r])
      ans1++;
    else {
      dfs(r, b);
      ans2++;
    }

  }
  cout << ans1 << " " << ans2 << en;
}

don't post your code, instead use spoiler tags

or just give a link to your submission

First find the maximum amount of digits, $$$nDigits = N / mn$$$ where $$$mn$$$ is the minimum over all $$$C_i$$$.

After that, loop from the most significant to the least significant digit while greedily assigning the digit's number by taking the maximum $$$j, j \in [1, 9]$$$, where $$$n - C_j \geq rest * mn$$$. $$$rest$$$ is the number of remaining unassigned digits. After a valid $$$j$$$ is found, reduce $$$n$$$ by $$$C_j$$$.

Submission

Got it, so basically we need to minimize the difference between the two subsets and add to the smaller subset powers of two that add up to that difference. Thanks a bunch.

Can you share your thought process on how you came up with the first 30 numbers being powers of two?

Super helpful blog!

Google Kickstart 2020 Round D — Beauty of Tree is also a cool problem that can be solved with the "contribution" technique.

I completely agree. Combined with the short statements, i always learn something new from ABC, especially D/E/F

I didn't think it was impl-heavy. Notice you can determine the coefficient of $$$B_i, 0 \leq i \leq m$$$ from C[i] / A[0];

int main() {
  fast;
  cin >> n >> m;

  vi A(n+1);
  FOR(n+1) cin >> A[i];
  reverse(all(A));

  vi C(n+m+1);
  FOR(n+m+1) cin >> C[i];
  reverse(all(C));

  vi B(m+1);
  FOR(m+1) {
    int times = C[i] / A[0];
    B[i] = times;
    FOR(j, n+1)
      C[i+j] -= A[j] * times;
    debug() << im(C);
  }
  reverse(all(B));
  EACH(x, B) cout << x << " ";
}

Notice you only need to do [0, 1] operation either vertically or horizontally (chessboard of size 1x2 or 2x1). Do this backwards for every row and column where there is a black cell. Edge case is when top left column is black.

You can also do $$$dp[index]$$$, where $$$dp[i]$$$ denotes the number of lexicographically smaller strings for index $$$i, 1 \leq i \leq \frac{(n+1)}{2}$$$. Finally, define $$$t$$$ as follow:

    string t = s;
    for(int i=1; i<=(n+1)/2; i++)
      t[n-i] = s[i-1];

If the string $$$t$$$ is lexicographically smaller than $$$s$$$, or with c++ you can just check if $$$t \lt = s$$$, add 1 to the answer. submission

Here is a similar, but simpler problem to better help understand converting to other bases. C — One Quadrillion and One Dalmatians

It's the prefix sum of the cost, which is:

1. cost of emptying the empty part of the portal, or the purple part of the portal if you've played Minecraft

2. cost of adding the outer obsidian

Use long long for x, as $$$x \leq{10^{18}}$$$

I haven't implemented a BIT solution, but found one that got accepted. Hopefully, it helps. submission

Thank you, will keep that in mind

Edge case when $$$n \lt = 2$$$, output should be 0

Really liked the problems!

Can anyone point out my mistake on B? Submission

I used bitmasks to simulate the removed numbers, implementation was buggy as it keeps getting WA on test 2

Neat trick! Will keep this in mind for similar problems. Thanks!

Output is the $$$id's$$$ sorted by their rankings decreasingly (bigger ranking -> more wins, or if same number of wins the smaller id gets the better rank).

What you need to do is make a custom comparator for your rankings array and sort them for every match.

I agree statement was bloated and implementation was not fun :(

Submission

Thank you, how do you know when to do heavy-light splitting? I'm having trouble identifying this type of problem

oh what a silly mistake. Thanks!

Any idea how to solve E? I used set for the sorted items and queue for the unsorted. Implementation was full of bugs I suppose as I got 8 WA.

Oh yeah that was an edge case. Glad I could help

I don't know about your implementation, but I used

and reduce with n-curK using the same formula. Submission

You should use adjacency list instead of adjacency matrix for checking the banned ways, improving from $$$n^2$$$ to $$$n + 2*m$$$ for the inner loop when reducing the banned ways

D was nice, even though I couldn't pass all test cases

I'm also curious why my submission outputs empty while locally it works fine. (Josephus Problem I btw) (disclaimer: code is ugly) submission

Would be a huge help if anyone can figure out why :)

Great explanation, helped me understand DP a bit better. Thanks.

Can anyone help explain how we get the number of banned ways here? I'm still confused while reading the editorial. Will update if I can think of a beginner friendly explanation.

Okay so I finally understood the method. Basically after computing the co-rime pairs, we loop for i in range [max(2, l), r], and for every i, we substract 2 * n_coprime - 1 from answer.

Why 2 * n_coprime - 1? Let's look at some example.

ex: [3, 7]
i = 2.
n_coprime(2) = 2, which is 4 and 6. I'll put these in a set, S = (4, 6).
To get the number of coprime pairs, we do S x S, the self product of this set which produces (4, 4) (4, 6) (6, 4) (6, 6)

let's represent this better in a n_coprime(2) by n_coprime(2) matrix, 2 x 2 matrix

(4,4) (6,4)
(4,6) (6,6)

we have a convincing pattern, the top and left borders are the g, where g = gcd(x,y) and either x/g = 1 or y/g = 1 that we need to remove.

let's see another example

ex: [3, 8]
i = 2
n_coprime = 3, S = (4, 6, 8)

co-prime pair 3x3 matrix:
(4,4) (6,4) (8,4) <
(4,6) (6,6) (8,6)
(4,8) (6,8) (8,8)
^

it looks like the pattern persists, and this is the reason of doing ans -= 2 * n_coprime(i) - 1, as 2 * n - 1 computes the number of elements in the top and left border of a matrix.

    gcd(x,y) = g and one of x/g != 1 or y/g != 1 is not satisfied
    is equivalent to
    gcd(x,y) = g and x = g or y = g

    ex: 3 8

    step 1:
    compute n_coprime pairs

    i = 2, mu[2] = 1
    (6, 4), (4, 6), (6, 6), (4, 4), (4, 8), (8, 8), (8, 6), (8, 4), (6, 8)
    3, mu = 1
    (3, 3) (3, 6) (6, 3) (6, 6)
    4, mu = 0
    (4, 4)
    5, mu = 1
    (5, 5)
    6, mu = -1 -> already computed twice
    (6, 6)
    7, mu = 1
    (7, 7)
    8, mu = 0
    (8, 8) -> already computed once

    ans = (4, 4) (4, 6) (4, 8) (6, 4) (6, 6) (6, 8) (8, 4) (8, 6) (3, 3) (3, 6)
    (6, 3) (5, 5) (7, 7) (8, 8)

    step 2:
    remove every g, where g = gcd(x,y) and either x/g = 1 or y/g = 1

    [i: 3]  [n_coprime(i): 2] (3, 6)  -> 2 * 2 - 1 = 3
    (4, 4) (4, 6) (4, 8) (6, 4) (6, 6) (6, 8) (8, 4) (8, 6) ~(3, 3) ~(3, 6) ~(6,
    3) (5, 5) (7, 7) (8, 8)

    [i: 4]  [n_coprime(i): 2] (4, 8)  -> 2 * 2 - 1 = 3
    ~(4, 4) (4, 6) ~(4, 8) (6, 4) (6, 6) (6, 8) ~(8, 4) (8, 6) ~(3, 3) ~(3, 6)
    ~(6, 3) (5, 5) (7, 7) (8, 8)

    [i: 5]  [n_coprime(i): 1] 5       -> 1 * 2 - 1 = 1
    ~(4, 4) (4, 6) ~(4, 8) (6, 4) (6, 6) (6, 8) ~(8, 4) (8, 6) ~(3, 3) ~(3, 6)
    ~(6, 3) ~(5, 5) (7, 7) (8, 8)

    [i: 6]  [n_coprime(i): 1] 6       -> 1 * 2 - 1 = 1
    ~(4, 4) (4, 6) ~(4, 8) (6, 4) ~(6, 6) (6, 8) ~(8, 4) (8, 6) ~(3, 3) ~(3, 6)
    ~(6, 3) ~(5, 5) (7, 7) (8, 8)

    [i: 7]  [n_coprime(i): 1] 7       -> 1 * 2 - 1 = 1
    ~(4, 4) (4, 6) ~(4, 8) (6, 4) ~(6, 6) (6, 8) ~(8, 4) (8, 6) ~(3, 3) ~(3, 6)
    ~(6, 3) ~(5, 5) ~(7, 7) (8, 8)

    [i: 8]  [n_coprime(i): 1] 8       -> 1 * 2 - 1 = 1
    ~(4, 4) (4, 6) ~(4, 8) (6, 4) ~(6, 6) (6, 8) ~(8, 4) (8, 6) ~(3, 3) ~(3, 6)
    ~(6, 3) ~(5, 5) ~(7, 7) ~(8, 8)

    tot = 10
    14 - 10 = 4

    final ans = (4, 6) (6, 4) (6, 8) (8, 6)

Hope this helps, highly suggesting reading this as well if you want to understand what mobius functions does!

I walked through the example test case, which might be helpful to whoever is still confused

  gcd(x,y) = g and one of x/g != 1 or y/g != 1 is not satisfied
  is equivalent to
  gcd(x,y) = g and x = g or y = g

  ex: 3 7

  step 1:
  compute n_coprime pairs, here mu[i] denotes the mobius function of i

  i = 2, mu[2] = 1
  (4, 4) (4, 6) (6, 4) (6, 6)
  3, mu = 1
  (3, 3) (3, 6) (6, 3) (6, 6)
  4, mu = 0
  (4, 4)
  5, mu = 1
  (5, 5)
  6, mu = -1
  (6, 6)
  7, mu = 1
  (7, 7)

  ans = (4, 4) (4, 6) (6, 4) (6, 6) (3, 3) (3, 6) (6, 3) (5, 5) (7, 7)

  step 2:
  remove every g, where g = gcd(x,y) and either x/g = 1 or y/g = 1

  [i: 3]  [n_coprime(i): 2] (3, 6)  -> 2 * 2 - 1 = 3
  ans = (4, 4) (4, 6) (6, 4) (6, 6) ~(3, 3) ~(3, 6) ~(6, 3) (5, 5) (7, 7)

  [i: 4]  [n_coprime(i): 1] 4       -> 1 * 2 - 1 = 1
  ans = ~(4, 4) (4, 6) (6, 4) (6, 6) ~(3, 3) ~(3, 6) ~(6, 3) (5, 5) (7, 7)

  [i: 5]  [n_coprime(i): 1] 5       -> 1 * 2 - 1 = 1
  ans = ~(4, 4) (4, 6) (6, 4) (6, 6) ~(3, 3) ~(3, 6) ~(6, 3) ~(5, 5) (7, 7)

  [i: 6]  [n_coprime(i): 1] 6       -> 1 * 2 - 1 = 1
  ans = ~(4, 4) (4, 6) (6, 4) ~(6, 6) ~(3, 3) ~(3, 6) ~(6, 3) ~(5, 5) (7, 7)

  [i: 7]  [n_coprime(i): 1] 7       -> 1 * 2 - 1 = 1
  ans = ~(4, 4) (4, 6) (6, 4) ~(6, 6) ~(3, 3) ~(3, 6) ~(6, 3) ~(5, 5) ~(7, 7) 

  tot = 7
  9 - 7 = 2

  final ans = (4, 6) (6, 4)

i saw submissions from the leaderboard do this after computing the number of coprimes [L, R]

  for (int i = max(2, l); i <= r; i++) {
    ans -= 2 * n_coprime(i);
    ans++;
  }

I know it has something to do with removing g, where g = gcd(x,y) and either x/g = 1 or y/g = 1 but can't wrap my head around it.

example submissions: AnandOza SSRS

I think the key observation is that for every possible subset sum i inside the range [0, sum/2], there is always a corresponding subset sum sum - i. The answer is sum - i where i is the biggest i in the range [0, sum/2] where dp[i] = true. Hope this helps.

Thank you, very clean and understandable solution

Thanks, really nice problem

Sorry for the vague question, I was referring to your submission. Thank you nonetheless. Love your streams btw, hope you do more in the future.

Can you explain why we do k-- at the start? Thank you in advance!

1-indexed solution

For those who are weak in combinatorics and don't know how to solve E with it (like me), here is my submission with detailed comments. Main idea was from thescrasse's submission

See also this comment to understand more about inclusion-exclusion principle.

Hope this helps

Thank you, very detailed and understandable explanation.

Thanks, this helped a lot

Thanks you, this is very helpful

Nice explanation, a bit of typo, should be $$$a[i] = (1,3),(1,4),(3,4)$$$

Yeah, I learned to understand when to return lo and hi, rather than just memoziring it. Thanks!

Thank you for sharing, I hope this will help me get to pupil :)

Another way to think about it is the property of odd numbers which is n & 1.

If there is an odd element, then the minimum number of trailing zeros is 0, the odd number.

If there is no odd number, that means every element has a bit sequence of where there are trailing zeros.

From your example, [6 6 4 4 4] in bit form is [110 110 100 100 100], where the minimum trailing zero is 1, which is from 6.

Dividing all the elements by two is the same as removing the trailing zero (which all elements have) until there is an odd number (the least significant bit is 1)

After this operation is done, you're guaranteed to not be able to split the elements,

Awesome explanation, thanks!

partitionForces

Thank you for the detailed explanation, I finally understood E.

Really nice problems, no idea how to solve them though lol

Really interesting problems, have no idea how to solve them though lol

Thanks for the info! I've only used Atcoder Library on atcoder contests but I think I'll start using it on codeforces as well.

What does NTT stand for?

thanks, changed from long long to __int128 and got AC

Leaving this here hope it helps https://labuladong.gitbook.io/algo-en/iii.-algorithmic-thinking/detailedbinarysearch

Ok got it, thank you for the very fast response

In C2 solution and find_left binary search why do we return hi instead of lo?

I see, thanks for pointing it out

C was a great question, I'm still confused though on my find_left function.

at first, my mid calculations were the standard (lo + hi) / 2, but this causes infinity loop:

ll mid = lo + (hi - lo) / 2;

then I changed it to (lo + hi + 1) / 2, then got AC:

ll mid = lo + (hi - lo + 1) / 2;

full code:

ll find_left(ll secondMaxIdx)
{
	ll lo = 1, hi = secondMaxIdx - 1;
	while (lo < hi)
	{
		ll mid = lo + (hi - lo) / 2;
		if (ask(mid, secondMaxIdx) == secondMaxIdx)
		{
			lo = mid;
		}
		else
		{
			hi = mid - 1;
		}
	}
	return lo;
}

Can anyone with a better understanding of binary search explain why this works?

I like how menacing your comment is because of that duck

I did nth_element(N/2) and got 1 wa. Any ideas? submission

i cry

i cry

same here bud, keep going

Oh wow that's such a cool way, thanks so much!

Oh wow I'm dumb. Really appreciate the explanation!

Can you explain why 2^k -1? I only know a(r^n -1)/r-1 to be the summation of geometric progression.

input = n and k. max value (we dont need to consider the 10^100 as it will be canceled out) = 1+2+...+n = n(n+1)/2

for i = k; i<=n+1; i++, you have to count the number of different values.

curmax = n(n+1)/2 — (n-i)(n-i+1)/2

// explanation: 1+2+...+n — (1+2+..+n-i) = n-i+1 + n-i+2 +...+ n-i+i

curmin = i(i+1)/2

then we increment answer with curmax-curmin + 1 (zero based)

my submission

i see. Thanks, your comment is very helpful. I'll keep this in mind for future competitions.

yeah didn't realize that. Thanks!

https://mirror.codeforces.com/contest/1337/submission/76887917

Can anyone help me find out why the last testcase wasn't printed? (locally it does)

Thanks!. i would like to confirm some this line on your problem C solution.

if(a[i] > b[p]){ ans += a[i] — b[p]; a[i] = b[p]; }

What I'm getting is that this is to find the blasts that doesn't instantly kill the i+1 monster so add a[i] — b[p] to ans as in the number of bullets it will take to kill after explosion. And after that we find the minimum of all a[i]..a[n] and add it to the ans as the starting point and we don't have to do anything anymore because the blasts will insta kill everything. Correct me if I'm wrong, and thanks for the video!

bruh