Thanks for participating in the most isekai NyaForces contest!
We honestly strived to make good tasks.
2072A - New World, New Me, New Array
Idea: ne_justlm
Tutorial
Tutorial is loading...
Solution
#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 - Having Been a Treasurer in the Past, I Help Goblins Deceive
Idea: ne_justlm
Tutorial
Tutorial is loading...
Solution
#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 - Creating Keys for StORages Has Become My Main Skill
Tutorial
Tutorial is loading...
Solution
#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 - For Wizards, the Exam Is Easy, but I Couldn't Handle It
Idea: ne_justlm
Tutorial
Tutorial is loading...
Solution
#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 - Do You Love Your Hero and His Two-Hit Multi-Target Attacks?
Idea: ne_justlm
Tutorial
Tutorial is loading...
Solution
#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;
}
Idea: itz_pabloo
Tutorial
Tutorial is loading...
Solution
#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 - I've Been Flipping Numbers for 300 Years and Calculated the Sum
Tutorial
Tutorial is loading...
Solution
#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;
}
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!
It also corresponds exactly to Pascal's triangle, taken modulo 2, a beautiful problem.
Thanks to the authors for a good round
constructive contest
lol,I feel like I did a combinatorical maths competiton instead of a codeforces round
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)$$$:
that is our model solution, but we thought that power of 2 solution is easier to understand.
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.
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 ?
Yes
thanks :)
some how deepseek solved G on first try
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
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$$$.
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?
look up Lucas' theorem. after you know it, it's kinda easy to prove
Problem F: Not too different from the official solution, but I calculated the parity of binomials using the following formula:
Then you can sequentially count the numbers of factor $$$2$$$ in the denominator and the numerator for each $$$r$$$.
"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$$$:
Where $$$s \ge t$$$ since $$$q$$$ divides $$$p$$$. Then the following holds:
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.
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!
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
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
https://cses.fi/problemset/task/1082
Helpful problem for G
https://www.geeksforgeeks.org/sum-divisors-1-n/
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.
kinda surprised this submission for E didnt TLE. i guess recursion is not so bad
I wasn't expecting D to be brute force of the nested loop type
Hi, I’ve implemented the following solution, and it fails on 2 test cases. I believe the logic is mostly fine, but I might be missing a specific edge case.
Could someone please help me understand what kind of edge case might be going wrong?
Especially this part seems suspicious:
if((or_value | (n — 1)) == x)
Here is my full code:
include <bits/stdc++.h>
using namespace std;
define ll long long
void solve(int d){ ll n , x , i = 0 , c = 0; cin >> n >> x; ll temp = x; vector binary(31 , -1); // complexity of this code is log₂(N) while(temp > 0){ binary[i] = temp % 2; temp /= 2; i++; } for(ll j = 0; j < i; j++){ if(binary[j] == 0 || binary[j] == -1) break; c++; } ll max_mex = (ll)pow(2 , c) — 1;
if(n == 1){ cout << x << endl; } else if(n > max_mex){ for(ll i = 0; i < max_mex + 1; i++){ cout << i << " "; } for(ll i = 0; i < n - max_mex - 1; i++){ cout << x << " "; } cout << endl; } else if(n <= max_mex){ ll or_value = 0; for(ll i = 0; i < n; i++){ or_value = or_value | i; if(i == n - 1){ if((or_value | (n - 1)) == x){ cout << i << endl; } else { cout << x << endl; } } else { cout << i << " "; } } }}
int main() { ios::sync_with_stdio(false); cin.tie(NULL); int t; cin >> t; while (t--) { solve(1); } return 0; }
If anyone could help point out a counterexample or what I might be missing, that would be very helpful. Thanks in advance!
wow!!! , i came up with a new solution for question C, 323122376, can someone check out this and tell me if its worse or better than solution in tutorial
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]; } ~~~~~
sooooo many math :(