Problem A:
Editorial
Tutorial is loading...
Code
t = int(input())
for tt in range(t):
n = int(input())
ans = [2 * i + 1 for i in range(n)]
print(*ans)
Problem B (Author: TheScrasse):
Editorial
Tutorial is loading...
Code
#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define len(a) (int)(a.size())
#ifdef LOCAL
#define __lg(n) log2(n)
#endif
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
template<typename T>
using PQ = priority_queue<T, vector<T>, greater<>>;
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
int mx = 0;
for (int i = 0; i < n — 1; ++i) {
mx = max(mx, a[i] — a[i + 1]);
}
for (int i = 1; i < n; ++i) {
if (a[i] < a[i — 1]) {
a[i] += mx;
}
}
if (is_sorted(all(a))) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
}
Задача C:
Editorial
Tutorial is loading...
Code
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
cnt1 = dict()
cnt2 = dict()
x = a[0]
a = a[1:]
s = set()
c = 0
while x not in s:
if x not in cnt1:
cnt1[x] = 0
cnt2[x] = 0
cnt1[x] += 1
cnt2[x] += c
s.add(x)
if x & 1:
x += 1
else:
x >>= 1
c += 1
for x in a:
s = set()
c = 0
while x not in s:
if x in cnt1:
cnt1[x] += 1
cnt2[x] += c
s.add(x)
if x & 1:
x += 1
else:
x >>= 1
c += 1
ans = 10 ** 18
for k, v in cnt1.items():
if v == n:
ans = min(ans, cnt2[k])
print(ans)
Problem D (Author: sunkuangzheng):
Editorial
Tutorial is loading...
Code
#include<bits/stdc++.h>
#ifdef DEBUG_LOCAL
#include <mydebug/debug.h>
#endif
using ll = long long;
const int N = 5e5+5;
using namespace std;
int T,n; string s; ll a[N],c[N],b[N],d[N];
void los(){
cin >> n >> s,s = " " + s; d[0] = 1;
for(int i = 1;i <= n;i ++) cin >> a[i],d[i] = 0;
for(int i = 1;i <= n;i ++) cin >> c[i];
c[0] = -1e18,b[0] = 0;
for(int i = 1;i <= n;i ++){
if(c[i] != c[i — 1]){
if(c[i] < c[i-1]) return cout << "No\n",void();
b[i] = c[i],d[i] = 1;
for(int j = i;j >= 0;j --){
if(s[j] == '1'){
if(d[j — 1] && b[j — 1] + a[j] != b[j]) return cout << "No\n",void();
d[j — 1] = 1,b[j — 1] = b[j] — a[j];
}else break;
}
}
}for(int i = 1;i <= n;i ++){
if(s[i] == '1') b[i] = b[i-1] + a[i],d[i] = 1;
if(!d[i]) b[i] = -1e16;
a[i] = b[i] — b[i-1];
if(max(c[i-1],b[i]) != c[i]) return cout << "No\n",void();
}
cout << "Yes\n";
for(int i = 1;i <= n;i ++){
cout << a[i] << " \n"[i == n];
}
}int main(){
ios::sync_with_stdio(0),cin.tie(0);
for(cin >> T;T --;) los();
}
Problem E:
Editorial
Tutorial is loading...
Code
#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define len(a) (int)(a.size())
using namespace std;
using ll = long long;
using ld = long double;
const int N = 2228;
vector<int> G[N];
int tin[N], tout[N];
int timer = 0;
int cntup[N][N];
int cntdown[N][N];
ll ans1 = 0, ans2 = 0, ans3 = 0;
void solve_path(int n, int v, int d) {
vector<int> dist(n);
auto dfs = [&](auto &self, int v, int p, int h = 0) -> void {
dist[v] = h;
for (int i : G[v]) {
if (i != p) self(self, i, v, h + 1);
}
};
dfs(dfs, v, -1, 0);
for (int i = v + 1; i < n; ++i) {
if (dist[i] == d) {
ans1 += d - 1;
}
}
}
void dfs_tin(int v, int p) {
tin[v] = timer++;
for (int i : G[v]) {
if (i != p) dfs_tin(i, v);
}
tout[v] = timer;
}
void solve() {
int n, d;
cin >> n >> d;
--d;
for (int i = 0; i < n; ++i) G[i].clear();
ans1 = 0, ans2 = 0, ans3 = 0, timer = 0;
for (int i = 0; i < n - 1; ++i) {
int a, b;
cin >> a >> b;
G[a - 1].push_back(b - 1);
G[b - 1].push_back(a - 1);
}
for (int i = 0; i < n; ++i) solve_path(n, i, d);
for (int i = 0; i < n; ++i) {
fill(cntup[i], cntup[i] + N, 0);
fill(cntdown[i], cntdown[i] + N, 0);
}
dfs_tin(0, -1);
for (int i = 0; i < n; ++i) {
auto dfs = [&](auto &self, int v, int p, int h) -> void {
if (tin[i] <= tin[v] && tin[v] < tout[i]) ++cntdown[i][h];
else ++cntup[i][h];
for (int j : G[v]) {
if (j != p) self(self, j, v, h + 1);
}
};
dfs(dfs, i, -1, 0);
}
vector<int> h(n);
auto dfs = [&](auto &self, int v, int p, int hh = 0) -> vector<int> {
int m = len(G[v]);
vector<vector<int>> who(m);
vector<int> all;
all.push_back(v);
h[v] = hh;
for (int i = 0; i < len(G[v]); ++i) {
if (G[v][i] == p) continue;
who[i] = self(self, G[v][i], v, hh + 1);
for (int j : who[i]) all.push_back(j);
for (int j = 0; j < i; ++j) {
for (int v1 : who[i]) {
for (int v2 : who[j]) {
int D = h[v1] + h[v2] - 2 * hh;
if (D >= d) continue;
int need = d - D;
ans2 += cntup[v][need];
int cnt3 = cntdown[v][need];
cnt3 -= cntdown[G[v][i]][need - 1];
cnt3 -= cntdown[G[v][j]][need - 1];
ans3 += cnt3;
}
}
}
}
return all;
};
dfs(dfs, 0, -1, 0);
cout << ans1 + ans2 + ans3 / 3 << '\n';
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
}
Problem F (Author: Vladithur):
Editorial
Tutorial is loading...
Code
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define gsize(x) (int)((x).size())
const char nl = '\n';
typedef long long ll;
typedef long double ld;
using namespace std;
const int K = 450;
void solve() {
int n, q;
cin >> n >> q;
vector<int> f(n, -1); // f[i] = -1 if impossible, 1 if i = a^2, 2 if i = a^2 + b^2
for (int a = 1; a * a < n; a++) {
for (int b = a; a * a + b * b < n; b++) {
f[a * a + b * b] = 2;
}
f[a * a] = 1;
}
vector<int> g(n, -1); // g[i] = -1 if impossible, else min `b` over i = a^2 - b^2
for (int b = 1; b * b < n; b++) {
for (int a = b; a * a - b * b < n; a++) {
int v = a * a - b * b;
if (g[v] < 0) g[v] = b * b;
}
}
while (q--) {
int a, b;
cin >> a >> b;
int ans = 4;
for (int d = -K; d <= K; d++) {
int x = a + abs(d) * d;
if (x <= 0 || x > n) continue;
int ta = x, tb = b;
if (ta > tb) swap(ta, tb);
int tans = 4;
{
int v = tb - ta;
if (g[v] > 0 && g[v] <= max(n - tb, ta - 1)) {
tans = 2;
}
if (f[v] > 0) {
tans = f[v];
}
if (d != 0) tans++;
}
ans = min(ans, tans);
}
cout << ans << nl;
}
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int t;
cin >> t;
while (t--) solve();
}
For problem C it says the Time Limit is 2 sec for every test, however in my solution I iterate over $$$N(\le10^5)$$$ and for each iteration I simulate the crunching procedure, $$$a_i$$$ which can go upto $$$10^9$$$ in worst case, and will take only $$$2log(H)\times(log(N\times(log(H)))$$$ ops, $$$2log(H)$$$ out of it are simulation steps and $$$(log(N\times(log(H))$$$ is the number of ops needed for updates in std::map, where $$$H(\le10^9)$$$, and the map size will be $$$N\times2log(H)$$$, so the time complexity should be $$$O(N\times2log(H)\times(log(N\times(log(H))))$$$, which translates to roughly $$$1.3\times10^8$$$ ops $$$\le$$$ $$$2\times10^8$$$ ops since Time Limit was 2 sec this shouldn't TLE.
Also Explanation for C in Edi isn't showing up.
xoxo and FairyWinx please look into the issues for 2231C - Chipmunk Theo and Equality
I created video editorial for C. Chipmunk Theo and Equality.
With the help of ChatGPT, I realized that using two separate maps is twice as slow. Chat told me to use a map<ll, pair<ll, ll>>. Of course it's actually unordered_map<ll, pair<ll, ll>, custom_hash> mp;
The point is, using 1 map is going to save you twice the time. The editorial uses 2 which is bad, but it is better for intuitively teaching the solution.
I have an interesting solution for C.
If we fix the parity of the final answer to be odd or even, then there is a greedy way to achieve it in minimum operations.
Takes 250 ms only in Python
beautiful!
I think that it was a worst contest. Choosing problems for every position(specially for B) was really inappropriate , isn't it?
Problem C has quite an interesting TL Limit 375594227 had to optimise it to the bone with unordered_map (even multiple unordered_maps TLed) but somehow passed , preety much kept all possible elements and the cost required for each element to reduce to all elements they can reach and then found best answer among all values which all elements can be reduced to.
A more elegant solution i did during the contest 375535979 where i simulated from the largest value mentioning this as i have no clue what the tutorial has written. Hope it helps!!
Could someone recommend problems that use the same idea as F ? (Specifically the theorem mentioned)
https://cses.fi/problemset/task/3355
https://cses.fi/problemset/task/3406
I have an interesting solution for C. Construct a graph that represents the procedure mentioned in the problem. Like 9 -> 10 -> 5 -> 6 -> 3 -> 4 -> 2 -> 1. Imagine doing this for all natural numbers. The graph formed is almost a tree but it has an issue that there is an edge from 1 to 2 and also an edge from 2 to 1. So basically we can find the LCA(lowest common ancestor) of all the elements of the input array in this tree(assuming it's rooted at 1). And then we can calculate number of moves needed to reach this number(the LCA). Since there can be some trouble with 1 or 2. We check for 1 and 2 separately. Implementation
Can someone explain D? please.
how much would F be rated approximately
C makes us realize that we should not use map blindly. For instance, one could have used an array nd for each index store possible values instead of using map.
I find it strange that the intended solution for C was not to just simulate the process (or that no one else mentioned a similar solution). My solution 375495693 did just that in O(nlog(n)log(C)). It simulates in a greedy way using a priority queue while keeping track of the smallest and biggest element and exiting the simulation once the smallest value was one less than the biggest (a special case for 1, 2 was needed tho).
I guess this goes to show how bad the maps are.
I upsolved C and I just simulated the problem (now I'm thinking why everyone is talking abt map here) without any map or other data structure. My approach is just take the min element and generate all possible nums till 1. Now these numbers are our target nodes and now we can just solve the problem like Multi source BFS. 375678399
Hey I am able to see this "Rating changes for last rounds are temporarily rolled back. They will be returned soon" Is it only for me or everyone is seeing it?
It will be fixed, happens sometimes.
Problem F seems easier than usual, felt bad.
1) Every number can be represented as atmost sum of 4 squares — This is just theory
2) Then finding answers for 1,2 are very easy, case 3) is the trick part which could also be solved after some thinking.
Usually F problems are very hard in div 2 contests, but this one is not the case :(.