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

Решение за NlogC описанное в разборе не заходит даже на C++(почему то работает за 4169 мс) Причем я использовал unordered_set с самописными хешами, что log проевращало в O(1). Если что номер посылки 375550527

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 203 ms only in Python

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

I think it was a worst contest. The problem B (at least) is not a suitable one at all for the contest. Again perhaps the problem setting was not okey , isn't it?_

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)

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.

approx how much would F be rated?

btw How much would approx F be rated??

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.

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?

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 fix

EDIT: D also has &mdash too

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!

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.

In the problem A, we can do this easer

CODE:

#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define BIT(a,b) (((a) >> (b)) & 1)
#define MASK(i) (1LL << (i))
#define pii pair<int,int>
#define pll pair<long long,long long>
#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORD(i,a,b) for(int i=(a); i>=(b); --i)
#define REP(i,n) for(int i=0; i<(n); ++i)
#define EACH(x,a) for(auto &x : a)
#define VAL(x) cout << #x << " = " << x;

using ll = long long;
using namespace std;

// const int nmax = 510;

// bitset<nmax * 2> cnt;

void solve()
{
    int n; cin >> n;
    FORD(i, 2 * n, n + 1) cout << i << " "; 
    cout << "\n";
}

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

    #define name "_"
    // freopen(name ".inp","r",stdin);
    // freopen(name ".out","w",stdout);

    int t; cin >> t;
    while(t--) {
        solve();
    }
}

C was brute force lmao . I had coded it fully just the submit tab was not opening in last minute due to poor internet.

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

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 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:

1. 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.

2. The distance between two vertices lying in different subtrees is exactly $$$d-1$$$. In this case, the third vertex will be the centroid itself.

3. 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.

D sucks