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.
thanks man, it works.
Yeah, you're right.
The total number of operations to get all the possible values from the array by performing the given operation in the problem is of the order of $$$O(n\times2\times\operatorname{log}C)$$$, where $$$C=10^9$$$, which approximately sums up to $$$6\times10^6$$$ operations.
In the worst case, the total number of values stored in the map would be of the order of $$$O(n\times2\times\operatorname{log}C)$$$, which is the same as the number of operations to simulate all the possible values.
After storing all the values in the map, you would fetch all the values from the map and take the value which has been visited by $$$n$$$ elements and also has the least number of operations performed to reach this value.
So, for fetching all the values from the map (and also when you were storing these values) it would take Time Complexity of the order of $$$O(M\operatorname{log}M)$$$, where $$$M=$$$ number of elements in the map. So, this becomes of the order of $$$O(n\times2\times\operatorname{log}C\times\operatorname{log}(n\times2\times\operatorname{log}C))$$$, which approximately sums up to $$$1.35\times10^8$$$ operations, which easily fits in the Time Limit: 2 seconds.
Also, it at max requires $$$6\times10^6\times12$$$ bytes $$$=$$$ $$$72$$$ Megabytes of memory in the map, which fits the Memory Limit: 512 Megabytes as well.
But, I think the maps have a significant hidden constant factor which adds up as we increase the number of elements in the map and perform operations on it. This added constant factor usually adds to the overall Time Complexity and hence maybe results in TLE.
The Editorial shows a clever trick to avoid inserting irrelevant elements in the map by checking if it has already been inserted or not. If the element hasn't been inserted in the map for index $$$i \gt 1$$$, then that means the number of elements that visit that value is $$$ \lt n$$$, which means that, that particular element would never be the last equal element.
My Submission: 375893847
The only thing I don't know is, how would this method result in $$$O(n)$$$ Memory Complexity.
Twist: If you use an Unordered Map instead of using Ordered Map, it runs in the Time Limit that too without using the optimization described in the Editorial.
Submission using Unordered Map: 375902927
I dis the almost same thing and my test is passing , probably you would have not used the lines for fast input-output, below is my code : ~~~~~ #include<bits/stdc++.h> using namespace std; #define ll long long #define mod 1000000007LL int main() { // Add these two lines for Fast I/O: //but note it will take all the input at once and then the output(it will untie cin and cout) //that is it will print everthing together and not one by one, so don't use it to have something //sort of interaction... ios_base::sync_with_stdio(false); cin.tie(NULL);
#ifndef ONLINE_JUDGE freopen("C:/Users/Nilesh Presswala/Desktop/c files/input.txt", "r", stdin); freopen("C:/Users/Nilesh Presswala/Desktop/c files/output.txt", "w", stdout); #endif ll n,k; cin>>n>>k; vector<ll> p(n+1),pp(n+1); //precompute factors of each; vector<vector<ll>> factors(n+1); for(int i=1;i<=n;i++){ for(int j=1;j*j<=i;j++){ if(i%j==0){factors[i].push_back(j); if(i!=j*j){factors[i].push_back(i/j);}} } } for(int i=1;i<=n;i++){pp[i]=1;} for(int i=2;i<=k;i++){ for(int j=1;j<=n;j++){ ll sum=0; for(auto f : factors[j]){ sum=(sum+(pp[f]))%mod; } p[j]=sum; } for(int j=1;j<=n;j++){pp[j]=p[j];} } ll ans=0; for(int j=1;j<=n;j++){ ans=(ans+pp[j])%mod; } cout<<ans; return 0; }~~~~~
I also encountered TLE initially. Instead of using 2 independent maps or complex nested maps, I managed to get AC in ~0.2s using a strict pruning method that avoids inserting useless elements into unordered_map.
Pre-compute the Valid Set: I ran the simulation for a[0] first, and stored every generated number in a std::set valid.
Pruning during processing: For every subsequent sequence, while simulating a[i] -> 1, I simply check if (valid.count(current_number)) before inserting into the unordered_map. If it's not in the a[0] path, it will never satisfy c1[x] == n, so we just skip it.
Hash Maps: I used 2 basic unordered_map<ll, ll> (one for c1, one for c2) and only inserted the filtered numbers.
This pruning step drastically reduces the map insert operations (roughly by 80%). It passes the limit easily.
Here’s the core logic I used:
wonderful anwser.i've never seen sooooooo gental code.u r the first man.u r a great gentleman,the only
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!
Amazing Solution!
how?
Lets say we fix the final answer to be even,
We will try to make 2 elements x and y equal instead of the whole array,
if any of x or y is odd, we need to first make them even....
once they are even, the only operation of dividing by 2 decreases the value, hence optimally we decrease the larger element.
something similar when we fix the answer to be odd, we make x and y both odd, and lets say x>y, then best we can do is x = (x+1)/2 to decrease the x
ye thats the main idea
I think that it was a worst contest. Choosing problems for every position(specially for B) was really inappropriate , isn't it?
i agree
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
whoa, cool
nice approach.
Can someone explain D? please.
how much would F be rated approximately
Maybe 2400-2700？
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.
But we have to store the values for every possible ai. And ai is in the range of 10^9
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
yup the same exact approach i have followed and its very intutive but why mutli source bfs just write a function that computes number of moves required for the target node . i guess we are doing the same thing but i didnt get why you used the term multi source bfs
Yeah actually i didn't execute the BFS when I was solving I thought about the problem like we have multiple sources so I just said it.
ohk get it
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.
Thanks
Problem F seems easier than usual.
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 :(.
Problem B's code has
&mdash, pls fixEDIT: D also has
&mdashtooNote that, those
&mdashmust be replaced by-(minus) sign.Can anyone tell why the following solution for problem A, when n=6, is not correct?
8 1 11 2 3 4
The following set is formed:- (8, 1, 11, 2, 3, 4, 9, 12, 13, 5, 7), which has all unique elements!
you supposed to have all unique elements (no two elements are equal)
But in the solution, all the elements are unique. [8, 1, 11, 2, 3, 4, 9, 12, 13, 5, 7] all the elements are unique and array [8, 1, 11, 2, 3, 4] has all the elements less than equal to 2.n (12).
That solution is correct. There are two ways to go about this as far as I know. Trivially output 2*i-1 for all i from 1 to n, or start from 1 and 2 and keep building and recording sums from there and make sure the repeated sum isn't printed.
Implementation 1: 375484565
Implementation 2: 375477956
But this solution is showing wrong answer in testcase 1 for n=6.
Elements must be <= 2*n
But in the solution, array [8, 1, 11, 2, 3, 4] has all the elements less than equal to 2.n (12).
8 1 11 2 3 4 is correct, I think you are misreading the judge/problem statement.
A problem that utilizes the bound on answers and considering multiple cases (like F): https://csp.vnoi.info/problem/csphn_30_4_hocmay.
TLDR: find a partition of n to powers such that sums of exponents is minimized. The intended solution is seemingly $$$O(N^{5/6})$$$. The four-square theorem is already provided in the problem statement, though.
For problem C:
Build a vector of vectors, each of which contains the sequence of values from $$$a_i$$$, ending at $$$1$$$. Keep removing the last elements of all vectors while those values are equal. Then, the sum of the size of vectors can be the answer to the problem, assuming that the optimal answer doesn't contain any $$$1 \rightarrow 2$$$ transformation.
If the optimal answer involves any $$$1 \rightarrow 2$$$ transformation, then the final value must be $$$2$$$. So you can additionally count the number of operations required to transform all values to $$$2$$$, and take the smaller one for the final answer. Time and space complexity is $$$O(n \log C)$$$ ($$$C = 10^9$$$ as in the editorial).
For problem D:
You need to be careful in picking the value of $$$-\text{inf}$$$ mentioned in the editorial, because if you pick something too small (close to $$$-10^{18}$$$), you'll have to use a value larger than $$$10^{18}$$$ to cancel the negative offset, violating the rules of output.
Was able to solve F via brute-force precomputation over all possible triples in $$$[1,2e5]$$$, with just a little bit of pruning to avoid MLE.
There's a problem in F's editorial. It should be "g(b-a)<=max(b-1,n-a)"
In D, the solution in editorial has an inner loop j:i->0, in the worst case if all s[i] = '1', we get quadratic time complexity?
In Problem A you can also just print n numbers backwards starting from 2*n till n+1
eg. if n=3 you can print 6 5 4 as 6 5 4 11 9 all are distinct
lol E can be solved in O(n^3) with pragmas
Submission
Yes, the worst-case time complexity of my code is also O(N^3), yet it still gets accepted.
377380034
Guys, i think there is an issue in problem D code, will it run at time complexity of O(N^2)? I suggest we should apply one more condition: if (d[i] == true) break
for example test 1 200000 11111111111111111(200000) 1 1 1 1 1 1 1 1 1(200000) 1 2 3 4 ... 200000
Editorial program cost "Total time: 212005 ms" on my PC.
But i do not know whether my example legal?
For Problem E, I have an approach: iterate every node in the tree and set it as the root in turn. Let the current root be u, which has cnt subtrees. We store the node count corresponding to all possible path lengths obtainable from each subtree into a two-dimensional array with the syntax: g[cnt].push_back(length_node).
We then split the problem of selecting three nodes into two scenarios: ① Node u must be chosen. The remaining two nodes are selected from two different subtrees of u. ② Node u is excluded entirely; all three nodes are picked from three distinct subtrees of u.
For Case ①: the problem reduces to: given cnt arrays whose total element count sums to n, count the number of valid ways to pick two distinct arrays, then pick one value from each such that the sum of the two values equals d−1.
For Case ②: the problem becomes: given cnt arrays whose total element count sums to n, count the number of valid ways to pick three distinct arrays, then pick one value from each such that the sum of the three values equals d−1.
The total count of valid configurations rooted at u is the sum of results from the two cases above.
I can solve Case ① in O(N) time, but Case ② runs in O(N^2). Since we need to process all N nodes as roots, the worst-case overall complexity should theoretically be O(N^3).
Yet the code still passes all test cases, and I am confused why this happens.
simpler solution for A, instead of thinking odd sequence or even sequence , printing the numbers from 2n till 1 or 1 to 2n always works, since they always satisfy the conditions. My submission in contest 375476815
C is wrong
My approach for C:-
It is sure that the whatever the number at the end in the array , that won't exceed min element of the array or +1 the same if it is odd, so i just stored all the possible numbers that can be formed after applying the given operations on the min element and then iterate over each of them and take the minimum of the operations over the numbers which are possible ending candidate of the array.
Here is the code
I have an interesting solution for problem E using Centroid Decomposition.
Let's root the tree at the centroid and say that at least two of the three vertices, which are the ends of the cut tree, are located in different subtrees relative to the current centroid.
Now we have 3 cases:
All three vertices lie in different subtrees relative to the current centroid. How to count: For each vertex in the subtrees of the current centroid, we store three values: the subtree index, the depth of the vertex, and the vertex itself. Then in $$$O(M^2)$$$ we can iterate over two vertices that will be the ends of the cut tree. Knowing their depths, we can determine at what depth the third vertex should lie. We add to the answer the number of vertices at the required depth that do not lie in the subtrees of the first or second vertex. This can be implemented, for example, by storing the total count of all depths and the count of depths in each subtree. Obviously, this result will then need to be divided by 3 so that each triplet of vertices is counted exactly once.
The distance between two vertices lying in different subtrees is exactly $$$d-1$$$. In this case, the third vertex will be the centroid itself.
Two of the iterated vertices lie in the same subtree. In this case, the third vertex must lie in another subtree. Let's find the size of the minimal tree that contains these two vertices and the centroid. It can be found using the formula $$$(h[v] + h[u] + dist(v, u)) / 2$$$, where $$$h[i]$$$ is the depth of vertex $$$i$$$ relative to the current centroid, and $$$dist(v, u)$$$ is the distance between vertices $$$v$$$ and $$$u$$$ (which can be found, for example, using LCA). Then we again know at what depth the third vertex should lie in another subtree.
The solution works in $$$O(N^2 \log N)$$$ or $$$O(N^2 \log^2 N)$$$ depending on the implementation.