Codeforces Round 1006 (Div. 3) Editorial

№	Пользователь	Рейтинг
1	jiangly	3810
2	Benq	3676
3	Kevin114514	3655
4	maroonrk	3463
5	strapple	3447
6	Um_nik	3387
7	heuristica	3322
8	turmax	3317
9	tourist	3307
10	jiangbowen	3291

№	Пользователь	Вклад
1	Qingyu	156
2	nik_exists	150
2	maspy	150
4	Um_nik	141
5	Errichto	139
6	adamant	137
7	AmShZ	135
8	BledDest	132
9	maroonrk	131
10	qwexd	129

Спасибо за участие в самом исекайнутом контесте на NyaForces!

Мы честно-честно старались над задачами.

2072A - Новый мир, новый я, новый массив

Разбор

Решение

#include <bits/stdc++.h>

using namespace std;

void solve() {
  int n, k, p;
  cin >> n >> k >> p;
  if (-n * p <= k && k <= n * p) {
    cout << (abs(k) + p - 1) / p << '\n';
  } else {
    cout << "-1\n";
  }
}

int main() {
  int tt;
  cin >> tt;
  while (tt --> 0) {
    solve();
  }
  return 0;
}

Оценка задачи

2072B - Будучи казначеем в прошлом, я помогаю гоблинам обманывать людей

Идея: ne_justlm

Разбор

Решение

#include <bits/stdc++.h>

using namespace std;

void solve() {
  int n;
  string s;
  cin >> n >> s;
  int64_t dash = count(s.begin(), s.end(), '-');
  int64_t under = n - dash;
  int64_t ans = (dash / 2) * (dash - dash / 2) * under;
  cout << ans << '\n';
}

int main() {
  int tt;
  cin >> tt;
  while (tt --> 0) {
    solve();
  }
  return 0;
}

Оценка задачи

2072C - Создание ключей от хранИЛИщ стало моим основным навыком

Идея: ne_justlm, IceHydra

Разбор

Решение

#include <iostream>
#include <vector>

using namespace std;

void Solve() {
  int len, val;
  cin >> len >> val;
  vector<int> ans(len, val);
  int or_val = 0;
  bool flag = true;
  for (int i = 0; i < len - 1; ++i) {
    if (((or_val | i) & val) == (or_val | i)) {
      or_val |= i;
      ans[i] = i;
    } else {
      flag = false;
      break;
    }
  }
  if (flag && (or_val | (len - 1)) == val) {
    ans[len - 1] = len - 1;
  }
  for (auto it : ans) cout << it << ' ';
  cout << '\n';
}

signed main() {
  cin.tie(0)->sync_with_stdio(0);
  int test_count = 1;
  cin >> test_count;
  while (test_count --> 0) Solve();
}

Оценка задачи

2072D - Для магов нет ничего сложного в экзамене, но я его не осилил

Идея: ne_justlm

Разбор

Решение

#include <bits/stdc++.h>

using namespace std;

void solve() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }

  int best_diff = 0, L = 0, R = 0;
  for (int i = 0; i < n; ++i) {
    int cnt_greater = 0, cnt_less = 0;
    for (int j = i + 1; j < n; ++j) {
      cnt_greater += a[j] > a[i];
      cnt_less += a[j] < a[i];

      if (best_diff > cnt_greater - cnt_less) {
        best_diff = cnt_greater - cnt_less;
        L = i, R = j;
      }
    }
  }

  cout << L + 1 << ' ' << R + 1 << '\n';
}

int main() {
  int tt = 1;
  cin >> tt;
  while (tt --> 0) {
    solve();
  }
  return 0;
}

Оценка задачи

2072E - Тебе же нравится герой, который бьёт по площади двойным уроном?

Идея: ne_justlm

Разбор

Решение

#include <bits/stdc++.h>

using namespace std;

vector<pair<int64_t, int64_t>> rec(int64_t k, int64_t x0 = 0, int64_t y0 = 0) {
  if (!k) {
    return {};
  }
  int64_t delta = 0;
  while (delta * (delta - 1) / 2 <= k) {
    delta++;
  }
  delta--;
  auto remaining = rec(k - delta * (delta - 1) / 2, x0 + delta + 1, y0 + 1);
  vector<pair<int64_t, int64_t>> ans;
  for (int x = x0; x < x0 + delta; ++x) {
    ans.push_back({x, y0});
  }
  ans.insert(ans.end(), remaining.begin(), remaining.end());
  return ans;
}

void solve() {
  int64_t k;
  cin >> k;
  if (!k) {
    cout << "1\n69 52\n";
    return;
  }
  auto ans = rec(k, 0, 0);
  cout << ans.size() << '\n';
  for (auto [x, y] : ans) {
    cout << x << ' ' << y << '\n';
  }
}

int main() {
  int tt = 1;
  cin >> tt;
  while (tt --> 0) {
    solve();
  }
  return 0;
}

Оценка задачи

2072F - Прощай, жизнь банкира, здравствуй, жизнь мага

Идея: itz_pabloo

Разбор

Решение

#include <bits/stdc++.h>

using namespace std;

constexpr int64_t kMaxN = 1e6 + 69;
vector<int64_t> c(kMaxN);

void precalc() {
  c[0] = c[1] = 0;
  for (int i = 2; i < kMaxN; ++i) {
    c[i] = c[i - 1];
    int x = i;
    while (x % 2 == 0) {
      x /= 2, c[i]++;
    }
  }
}

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

  --n;
  for (int i = 0; i <= n; ++i) {
    cout << k * (c[n] == c[i] + c[n - i]) << " \n"[i == n];
  }
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  precalc();

  int tt = 1;
  cin >> tt;
  while (tt --> 0) {
    solve();
  }
  return 0;
}

Оценка задачи

2072G - Переворачивая числа 300 лет, сам того не заметив, посчитал сумму

Идея: ne_justlm, IceHydra

Разбор

Решение

#include <bits/stdc++.h>

using namespace std;

constexpr int64_t mod = 1e9 + 7;
constexpr int64_t twoInv = 500'000'004;
constexpr int64_t sixInv = 166'666'668;

int64_t add(int64_t a, int64_t b) {
  return (a % mod + b % mod) % mod;
}

int64_t mns(int64_t a, int64_t b) {
  return (a % mod - b % mod + mod) % mod;
}

int64_t mul(int64_t a, int64_t b) {
  return (a % mod) * (b % mod) % mod;
}

int64_t rev(int64_t n, int64_t p) {
  int64_t res = 0;
  while (n) {
    res = add(mul(res, p), n % p);
    n /= p;
  }
  return res;
}

int64_t stupid(int64_t n, int64_t k) {
  int64_t res = 0;
  for (int64_t p = 2; p <= k; ++p) {
    res = add(res, rev(n, p));
  }
  return res;
}

int64_t sum1(int64_t r) {
  return mul(mul(r, r + 1), twoInv);
}

int64_t sum1(int64_t l, int64_t r) {
  return mns(sum1(r), sum1(l - 1));
}

int64_t sum2(int64_t r) {
  return mul(mul(mul(r, r + 1), 2 * r + 1), sixInv);
}

int64_t sum2(int64_t l, int64_t r) {
  return mns(sum2(r), sum2(l - 1));
}

int64_t get(int64_t n, int64_t l, int64_t r) {
  if (l > r) {
    return 0;
  }

  int64_t res = mul(sum1(l, r), n);
  int64_t minus = 0, plus = 0;

  int64_t L = l;
  while (L <= r) {
    int64_t value = n / L;
    int64_t R = min(r, n / value);

    minus = add(minus, mul(sum2(L, R), value));
    plus = add(plus, mul(R - L + 1, value));

    L = R + 1;
  }

  return add(mns(res, minus), plus);
}

void solve() {
  int64_t n, k;
  cin >> n >> k;

  int64_t sq = (int64_t)sqrtl((long double)n);
  int64_t ans = mul(max<int64_t>(0, k - n), n);
  ans = add(ans, stupid(n, min(sq, k)));
  ans = add(ans, get(n, sq + 1, min(n, k)));

  cout << ans << '\n';
}

int main() {
  int tt = 1;
  cin >> tt;
  while (tt --> 0) {
    solve();
  }
  return 0;
}

Оценка задачи

Комментарии (40)

Показать архивные | Написать комментарий?

jagan028

19 месяцев назад, скрыть # |

+11

F was so good!

Apart from the Pascal's triangle solution, You can do it by recursion and I learned that the self-similar repeating fractal pattern formed by F is called a Sierpinski's triangle!

→ Ответить

Dinarchak

19 месяцев назад, скрыть # ^ |

It also corresponds exactly to Pascal's triangle, taken modulo 2, a beautiful problem.

Rushdi

nice

Vladimir001

← Rev. 2 →

Thanks to the authors for a good round

Top12

constructive contest

liangjeremy

lol,I feel like I did a combinatorical maths competiton instead of a codeforces round

dssfsuper2

+13

For the F, if we use Lucas' Theorem, we can actually deduce that $$$\binom{n}{k}\mod 2$$$ is 1 only if $$$k$$$ in binary is a submask of $$$n$$$, in other words if $$$k$$$&$$$n$$$ equals $$$k$$$

With this there's an elegant two-line solution in $$$O(n)$$$:

int a,b;cin>>a>>b;a--;
for(int i = 0;i<=a;i++) cout << (int)((a&i)==i)*b << ' ';

ne_justlm

that is our model solution, but we thought that power of 2 solution is easier to understand.

Makaty

hello there, can you please explain what submask means

If k is a submask of n, then every bit that is 1 in k is also 1 in n. for example 0010001 is a submask of 1010011, because the only bits that are 1 in the first number (3rd and 7th), are also 1 in the second number.

imzero34802

18 месяцев назад, скрыть # ^ |

amazing solution man, had a small doubt, in lucas theorem when we convert the numbers to different bases, do the bases have to be the same prime number we are taking % with at the end ?

Greyitis

17 месяцев назад, скрыть # ^ |

Yes

eugenechka.boyko.2_0-0

иначе говоря, лишь посмотрев все исекаи мира мы обретаем силу писать раунды на кф

устами eugenechka.boyko.2_0-0 глаголет истина

melodiasssf

some how deepseek solved G on first try

jiazhiba44

+28

ne_justlm In fact, the first part of the problem G is not $$$O(\sqrt{n} \log n)$$$. The reason is that the total time is equal to $$$\sum\limits_{i=2}^{\sqrt{n}} \frac{\ln n}{\ln i}$$$, and since the logarithmic integration yields a complexity of $$$\int\limits_{2}^\sqrt{n} \frac{1}{\ln x} dx=O(\frac{\sqrt n}{\ln n})$$$ for the latter part, the total complexity is $$$O(\sqrt{n})$$$

thanks! will change later

lvisbl_

In the problem F, you said that we will build each the numbers in the n-th rows bit by bit, but why in the solution you just multiply it with the odd condition. I understand that when we have odd condition of power of 2 then the bit i-th at which Ki is set also must be set for the number, but do multiplication hold this property? Or how can I relate multiplication with xor property, thank.

multiplication works because condition will be either $$$0$$$ or $$$1$$$, so multiplying by it is just the same as set all set bits from $$$k$$$ to $$$1$$$.

za11

For the F , I tried to print out the triangle to find the pattern, and finally I found that they meet this pattern, can someone help prove it?

        for(int i =0;i < n;i++)
        {
            if((i|(n-1))==n-1)
                cout<<k<<' ';
            else
                cout<<0<<' ';
            cout<<endl;
        }

look up Lucas' theorem. after you know it, it's kinda easy to prove

_Kee

Problem F: Not too different from the official solution, but I calculated the parity of binomials using the following formula:

$$$\begin{align*} \binom{n}{0} &= 1 \\ \binom{n}{r} &= \binom{n}{r-1} \cdot \frac{n - r + 1}{r} \end{align*}$$$

Then you can sequentially count the numbers of factor $$$2$$$ in the denominator and the numerator for each $$$r$$$.

TuringCPU

"count the numbers of factor 2 in the denominator and the numerator"

what do you mean by this ?

Let's say you can denote $$$\displaystyle \binom{n}{r}$$$ as a fraction $$$\displaystyle \frac{p}{q}$$$ (note this value is always an integer). Let's extract the factors of $$$2$$$ from $$$p$$$ and $$$q$$$:

$$$\begin{align*} p &= 2^s \cdot p^\prime, \\ q &= 2^t \cdot q^\prime. \end{align*}$$$

Where $$$s \ge t$$$ since $$$q$$$ divides $$$p$$$. Then the following holds:

$$$\begin{align*} \frac{p}{q} \ \text{is even} \iff s \gt t. \end{align*}$$$

Therefore, to find the parity of $$$\displaystyle \binom{n}{0}, \binom{n}{1}, \ldots, \binom{n}{n}$$$, you only need to count the number of factor $$$2$$$ s that appear in the denominators and the numerators in those values, instead of calculating those values in full. And this can be done sequentially, from $$$\displaystyle \binom{n}{0}$$$ to $$$\displaystyle \binom{n}{n}$$$, using the formula I wrote in the post above.

Nguyendinhbach_69

How tf did newbies and pupils know lucas theorem for F ???? Anyways F is a beautiful problem.

Seems like proof for E is not complete as "For k <= 446, the algorithm places no more than 43 sticks", how do we get this 43 sticks, do you proceed the same proof with upper bound is 446 instead of 10^5 and repeat for the next upper bound until reach 0? Do we have any formal proof, thank you!

H.Shiva

← Rev. 4 →

Can anyone explain me why (n^2) solution worked in problem D? Because timeComplexity is (testcases*n*n) => (10^4 * 10^3 * 10^3) => 10^10 which is greater than 10^8, then why it not giving tle

Wevton

There is a condition on the input saying that sum of $$$n^2$$$ over all n in the testcase is bounded to $$$4*10^6$$$, so it is only $$$2*10^3 * 10^4 = 2*10^7$$$ operations, which fits the time limit.

total complexity is $$$\mathcal{O}(\sum\limits_{i = 1}^{t} n_i^2)$$$ which is already bounded to $$$4 \cdot 10^6$$$. that would be the total number of operations

RGB_ICPC_7

Nice problem statements

esh_war2

← Rev. 3 →

https://cses.fi/problemset/task/1082

Helpful problem for G

https://www.geeksforgeeks.org/sum-divisors-1-n/

Gordon__Freeman

In the third case where $$$\log_p{n} \le \log_{\sqrt{n}}{n}$$$ , in the case where they are equal wouldn't the number of digits be $$$\log_p{n} + 1 = 3?$$$

no.

_whimsical_

kinda surprised this submission for E didnt TLE. i guess recursion is not so bad

Mortelman

Желаю здоровья, счастья и хороших контестов идейному вдохновителю названий для этих задач.

(Ну и другим составителям раунда тоже всего хорошего)

DarkDevilVaqif

17 месяцев назад, скрыть # |

I wasn't expecting D to be brute force of the nested loop type

B1ossoms

14 месяцев назад, скрыть # |

I think F can be solved by Lucas theory.Here my solution. ~~~~~ int n, k; cin >> n >> k; n -- ; for (int i = 0; i <= n; i ++ ) { cout << ((i & (n — i)) == 0 ? k : 0) << " \n"[i == n]; } ~~~~~

hangz

12 месяцев назад, скрыть # |

[submission:341537826]why my code tle case3,i cant understand,sos!

Haostar

8 месяцев назад, скрыть # |

sooooo many math :(

Блог пользователя ne_justlm

Спасибо за участие в самом исекайнутом контесте на NyaForces!