### feecIe6418's blog

By feecIe6418, 12 months ago,

Thanks for participation!

If your solution to D involves any data structures and is not $O(n)$ -- please read the "solution 1". I believe it is very interesting, but to make the difficulty suitable for D we allowed not $O(n)$ solutions.

1696A - NIT orz!

Hint 1
Solution

1696B - NIT Destroys the Universe

Hint 1
Hint 2
Solution

1696C - Fishingprince Plays With Array

Hint 1
Hint 2
Solution

1696D - Permutation Graph

This problem has two different solutions. The first one is more beautiful, but less straight-forward.

Hint 1 for solution 1
Hint 2 for solution 1
Hint 3 for solution 1
Solution 1
Hint 1 for solution 2
Hint 2 for solution 2
Solution 2

1696E - Placing Jinas

Hint 1
Hint 2
Hint 3
Solution

1696F - Tree Recovery

Hint 1
Hint 2
Solution

1696G - Fishingprince Plays With Array Again

Hint 1
Hint 2
Hint 3
Solution

1696H - Maximum Product?

Hint 1
Hint 2
Solution
• +332

 » 11 months ago, # |   +12 Thank you for fast editorial!
 » 11 months ago, # |   +18 fast editorial, good problemsgreat round!
 » 11 months ago, # |   +10 What a speed!
 » 11 months ago, # |   +7 Editorials with hints. Appreciable efforts..Thanks!
 » 11 months ago, # |   +30 I hope I'm not the only one who got WA on question B for not realizing that the answer is at most 2... XD
•  » » 11 months ago, # ^ | ← Rev. 2 →   0 .
•  » » 11 months ago, # ^ |   +2 got 4 times wa then realised .
•  » » 11 months ago, # ^ |   0 Lol Same...
•  » » 11 months ago, # ^ |   -11 LOL ! I also did not realize it.
•  » » 11 months ago, # ^ |   -8 got WA 3 times not realizing answer will be at most 2, one more WA for a mental typo using max(ans,2) instead of min(ans,2).
 » 11 months ago, # |   0 Thanks for so much early tutorial
 » 11 months ago, # |   +12 Best way to present editorial is with hints Thanks for fast and crisp editorial
•  » » 11 months ago, # ^ |   0 Yeah, totally agreed! I love it when editorials have Hints as it allows many of us to solve problems (sometimes we just need that train of thought and a little nudge). Honestly, it's better than looking at the solution and then doing it, as there's still that feeling of 'doing it ourselves'
 » 11 months ago, # |   0 Tq for fast Editorial
 » 11 months ago, # |   +2 Thank you for the fast editorial feecIe6418 Congrats on your first Global Round. It's hard to imagine that you single-handedly created all except for one problems for this round, that's amazing! Great work! FeedbackI really liked the problems. Personally I felt that the problem statements were not very lengthy (which is good) and not too hard to understand for low-rated players. Honestly, I only checked out the first three problems, but I found them really interesting. I was able to work out the solutions for the first two, sample test cases were also good in my opinion, no problems with that.Unfortunately due to a power cut in my locality, I didn't have internet access for the first hour of the contest and this decided not to participate. Looking forward to upsolving in virtual participation.Also, many congratulations once again on your first Global Round. It's hard to imagine the amount of work that goes into making these problem statements and testing them. Kudos to the team and to all testers and problem setters on the platform!!
 » 11 months ago, # |   +3 Thanks for the fast editorial. By the way,E
 » 11 months ago, # |   0 Thank you for Editrorial!
 » 11 months ago, # | ← Rev. 2 →   -6 Feeling sorry for Tourist. Dude is facing a lot of negative deltas in recent times. I remember reading a blog few days back, when someone predicted Tourist's fall. It's becoming real now :(
•  » » 11 months ago, # ^ |   +24 Just out of curiosity, could you link that blogpost? I'd like to read it too
•  » » 11 months ago, # ^ |   0 Brother Legends never dies Tourist is Legendary No one takes his place
•  » » » 11 months ago, # ^ |   -21 There is nothing called legendary. If you consistently put in the effort for over a decade(He has been into mathematics and programming since age 10), you could become like him(may be better than him).
•  » » » » 11 months ago, # ^ |   +23 And you're still newbie after 3 years.
•  » » » » » 11 months ago, # ^ |   -13 Because I am not consistent :( I am trying to be consistent.
•  » » » » » 11 months ago, # ^ |   -7 And you are still unrated after 2 years
•  » » » » » 11 months ago, # ^ |   0 I am saving the link to this comment because i want to comment here when i get a decent level of rating in CF.
•  » » » » » » 11 months ago, # ^ |   0 and what's your definition of "decent"?
•  » » » » » » » 11 months ago, # ^ |   0 RED
•  » » » » » » » » 11 months ago, # ^ |   0 lol, okay.
•  » » » » » » » » » 11 months ago, # ^ |   0 I want to give the same reply to u one day
•  » » 11 months ago, # ^ |   0 A Lion takes its one step back before making its bigger attack
•  » » 11 months ago, # ^ |   0 Normal competition when everyone is too good.
•  » » 11 months ago, # ^ |   0 Share the blog . I want to see what happen to our king !!.
•  » » 11 months ago, # ^ |   +3 i Dont think its a downfall if you get -56 for global rank 7.
 » 11 months ago, # |   +3 Thank you for Editrorial!
 » 11 months ago, # |   +48 Solution for E without using the identity given in the editorial: Let $D_i$ be the $i$'th diagonal, the set of $(x, y)$ such that $x+y=i$. Calculate the answer by summing each diagonal. When moving from $D_i$ to $D_{i+1}$, the current number of moves is simply multiplied by $2$, except in the case where some cell in $D_i$ is a "boundary" (the cell down or to the right is black). But there are only $O(n)$ such boundary cells, so we can simply subtract their contribution as we go along.
 » 11 months ago, # |   -38 Thank you for such a fast editorial , But I would like to say , talk is cheap , show me the code
 » 11 months ago, # |   0 Plz show codes for the questions
 » 11 months ago, # |   0 Are you sure memory limit will not exceed if we expand them? If not why did it happen to me?
•  » » 11 months ago, # ^ |   0 because you do not need to store entire expanded array. you can simply store counts of repeating factors.
•  » » 11 months ago, # ^ |   0 You shouldn't make the whole array just you can store the occurences
•  » » » 11 months ago, # ^ |   0 can you pls explain how to store the occurrences such that they appear in the correct order as well?
•  » » » » 11 months ago, # ^ |   0 I did it just storing a pair of values: the factors and its number of ocurrences. For example, for M = 3 and A = {6 3 4} -> {[2,3] [1,3] [4,1]} Did it for both vectors and compare them
•  » » » » 11 months ago, # ^ |   0 161770389 You can check here. I've just stored it as pair like if A={4,2,6} and M=2 then it will be {{2,3},{3,2}}.
•  » » » 11 months ago, # ^ |   0 This is how I rewrote my solution after hitting the memory limit.https://codeforces.com/contest/1696/submission/161775684
 » 11 months ago, # |   0 Thanks for the fast Editorial!
 » 11 months ago, # |   0 Can someone explain why the following code for Problem C is getting RTE on Pretest 3? Codevector breakdown(ll t, ll m) { ll recur = 1; while(t%m==0) {t/=m; recur*=m;} return vector(recur, t); } int main() { setIO(); TestCase() { int n, m; cin >> n >> m; vector a; for(int i = 0; i < n; i++) { ll x; cin >> x; vector bx = breakdown(x, m); for(auto& z: bx) a.push_back(z); } int o; cin >> o; vector b; for(int i = 0; i < o; i++) { ll x; cin >> x; vector bx = breakdown(x, m); for(auto& z: bx) b.push_back(z); } cout << (a==b ? "Yes" : "No") << endl; } } 
•  » » 11 months ago, # ^ |   0 The maximum size of the array that can be created is of order 1e5, you are pushing more values than the max size, thus giving RTE. Instead of pushing all values, just store it in pair of vectors {value, frequency}.
•  » » » 11 months ago, # ^ |   0 Makes sense, thank you so much!
•  » » » 11 months ago, # ^ |   0 Excuse me, why is it giving RTE and not memory error?
•  » » » » 11 months ago, # ^ |   0 As far as I know, segmentation fault = RTE in online judges
•  » » » » » 11 months ago, # ^ |   0 I meant how it's a segmentation fault? Like the code doesn't set any array size constraints as such
•  » » » » » » 11 months ago, # ^ |   0 Because, after the array is completely filled, he is trying to insert more elements in it...
 » 11 months ago, # |   0 Flash like Editorial!!!
 » 11 months ago, # |   0 "Find the maximum possible value of the maximum value in a after any number (possibly zero) of operations."In Problem A this line mislead me into thinking that we have to maximize the maximum value of the original array, so I took the maximum value say "V" in the array and expected V|Z to be the answer, but after spending like an hour and half I realized that the answer would be the maximum attainable value of any value in the array, I would like to request the authors to write clearer statements to avoid such confusion, like the line mentioned above could be replaced by, "Find the maximum possible value in a after any number (possibly zero) of operations." Those who faced the same difficulty can upvote the post so that it reaches the authors. Peace.
•  » » 11 months ago, # ^ |   0 Exact same thing happened with me!!! wasted 24 mins on a simple problem.
 » 11 months ago, # |   +3 The problem F is great !
 » 11 months ago, # |   +119 Easier solution for F:Firstly, notice that if you know a single edge of the tree, you can figure out all the edges. (If you know an edge u,v first all w such that dist[u][v] = dist[u][w] and add edge u,w. Then continue this process). In the end, you can verify the existence in O(n^3). Now, realize that out of (1,2), (1,3) ... (1,n), one of the edges must be present. So, try all of these n-1 possible edges and check if you get a valid tree.
 » 11 months ago, # |   0 fast editorial, good problemsgreat round!
 » 11 months ago, # |   +15 D was really great, I have solved it with stack, segment tree, and bfs :).
 » 11 months ago, # |   +12 Was it really a good idea to give n+1 number in array for task E ? I didn't solve it only because of this. The tasks mustn't be with such a potential trap I think.
•  » » 11 months ago, # ^ |   0 lmao came here to comment this
 » 11 months ago, # |   +3 D is really cool, I solved it with mono stack and binary search
•  » » 11 months ago, # ^ |   0 I cant understand the second approach given in editorial . Need help
 » 11 months ago, # |   0 could someone please find the mistake in my submission for C?
•  » » 11 months ago, # ^ |   0 seems integer overflow problem.
•  » » 11 months ago, # ^ |   0 Int overflow
 » 11 months ago, # |   0 For Question 2 it says that it will give you the smallest non-negative integer (**zero or positive number**) which does not appear in S. For test case 0 2 3 0 1 2 0 . if i take the entire array and put it in the mex function . how will it return any non-negative number that does not appear in the array ?
•  » » 11 months ago, # ^ |   0 if you take entire array, it will return 4. return value of mex doesn't have to appear in array.
•  » » 11 months ago, # ^ |   0 it will give 4. so the array will be 4 4 4 4 4 4 4. then do mex again for the entire array, it will give 0 this time. hence all 0.
 » 11 months ago, # |   +3 thanks for the editrorial!
 » 11 months ago, # |   0 pls give some proofs for math formulas you are using in E solution otherwise it doesnt tutorial, because your solution based only on this math fact so you have to prove it
•  » » 11 months ago, # ^ |   +72 It's just hockey stick identity. Nothing more, nothing less. I don't think one has to prove a well-known, simple identity in combinatorics in their editorial
•  » » 11 months ago, # ^ |   0 I'll leave a link to the solution of last problem from last Starters since it also uses this identity and gives a 'proof' based on another (maybe more well-known) identity.
•  » » 11 months ago, # ^ | ← Rev. 2 →   +12 For row i : the summation is iCi + (i+1)Ci + (i+2)Ci ... + (i+v[i]-1)Ci.Now if we know iCi = 1 = (i+1)C(i+1)Replacing this in the above formula we get the summation for row i as : (i+1)C(i+1) + (i+1)Ci + (i+2)Ci ... + (i+v[i]-1)Ci. Combine the first 2 terms : (i+1)C(i+1) + (i+1)Ci = (i+2)C(i+1) [ Using the simple property nCr = (n-1)C(r-1) + (n-1)Cr ]Replacing this in the equation we get : (i+2)C(i+1) + (i+2)Ci ... + (i+v[i]-1)CiAgain now, we can combine the next 2 terms and so on. So finally we get (i+v[i])C(i+1)
•  » » » 11 months ago, # ^ | ← Rev. 4 →   +22 Thinking on how to come up with a visual approach, I have found the following one. It does nothing different than what 123thunderbuddie did, but supports the idea visually.We want to find the sum of the number of ways to reach every cell in the $i^{th}$ row. Assuming there are $c$ cells, the sum is equal to the following (just what 123thunderbuddie wrote): $\displaystyle \binom{i}{i} + \binom{i+1}{i} + \cdots + \binom{i+c-1}{i}$Suppose there is a row below that has the same number of cells $c$ (not the $(i+1)^{th}$ row but a temporary one). This sum is actually equal to number of ways to reach the last cell in that row, which is $\binom{i+c}{i+1}$ (number of ways to reach cell $(i+1, c-1)$ from $(0, 0)$). Here is a visualization:
 » 11 months ago, # |   0 Why is this submission with long long giving WA, but this isnt.
•  » » 11 months ago, # ^ |   +1 The variable is z_cnt is not initialized in both of them resulting in UB. You got lucky with the second solution.
•  » » » 11 months ago, # ^ |   0 Thanks :) me rn
 » 11 months ago, # |   0 Kudos to the authors for an amazing round. Finally reached Purple!
 » 11 months ago, # |   +87 I've noticed that in G there are no small tests before the first big one, maybe that's the case in other problems too, keep in mind that it's bad.
 » 11 months ago, # |   0 I am not sure of the time complexity of this solution for D can someone help out https://codeforces.com/contest/1696/submission/161799451I feel it should be $O(n)$ because any next greater or next smaller chain is travelled once.
 » 11 months ago, # | ← Rev. 2 →   +20 We can do D in O(N). By maintaining premax,premin,sufmax,sufmin. Spoilerll n; cin>>n; vector a(n); cin>>a; vector loc(n+1); for(ll i=0;i> adj(n+1); vector sufmax(n+2),sufmin(n+2); sufmax[n-1] = a[n-1]; sufmin[n-1] = a[n-1]; for(ll i=n-2;i>=0;i--){ sufmax[i] = max(sufmax[i+1],a[i]); sufmin[i] = min(sufmin[i+1],a[i]); } vector premin(n+1),premax(n+1); premin[0] = a[0]; premax[0] = a[0]; for(ll i=1;i a[i] and a[i] == premin[i]){ adj[i+1].push_back(loc[premax[i]]); adj[loc[premax[i]]].push_back(i+1); } if(sufmax[i] > a[i] and a[i] == sufmin[i]){ adj[i+1].push_back(loc[sufmax[i]]); adj[loc[sufmax[i]]].push_back(i+1); } if(sufmin[i] < a[i] and a[i] == sufmax[i]){ adj[i+1].push_back(loc[sufmin[i]]); adj[loc[sufmin[i]]].push_back(i+1); } } debug(adj); auto bfs = [&](ll x){ vector vis(n+1),dist(n+1); vis[x] = 1; dist[x] = 0; queue q; q.push(x); while(q.size()){ auto node = q.front(); q.pop(); for(auto child: adj[node]){ if(vis[child] == 0){ vis[child] = 1; dist[child] = 1 + dist[node]; q.push(child); } } } return dist[n]; }; cout << bfs(1) << endl; 
•  » » 11 months ago, # ^ |   -13 thanks for the code
•  » » » 11 months ago, # ^ | ← Rev. 2 →   0 you're welcome. Some lines are redundant you can remove them.
•  » » 11 months ago, # ^ |   0 Doesn't this code will add multiple edges between two nodes? Though it won't affect our result.
•  » » » 11 months ago, # ^ |   0 Yup it will i thought of making vector but i ran out of time. see my submission during contest. I clutched this question after being brutally harrassed by Problem C(nice problem) in last 3 min.
 » 11 months ago, # |   0 Thank you very much for the fast editorial! I learned a lot from the problems I didn't solve.
 » 11 months ago, # | ← Rev. 2 →   0 I solved problem D using greedy approach :) 161785869 here it is
 » 11 months ago, # |   0 Can someone explain C please
•  » » 11 months ago, # ^ | ← Rev. 2 →   +2 Just maintain vector of pairs where pairs.first = actual value and pair.second = frequency . Make vector of both a and b . And check at last a == b or not. Since we can divide every no m times even in the worst case it's log(n), which means atmost 30times for each element. which is still O(N). Code-- Spoiler#include #include #include using namespace std; #define mem(a, b) memset(a, (b), sizeof(a)) #define all(x) begin(x), end(x) #define rall(x) rbegin(x), rend(x) #define mp make_pair #define print2d(mat,n,m){for(int i=0;i void __print(const pair &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';} template void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";} void _print() {cerr << "]\n";} template void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);} #ifndef ONLINE_JUDGE #define debug(x...) cerr << "[" << #x << "] = ["; _print(x) #else #define debug(x...) #endif template istream& operator>>(istream& is, vector& v){for (auto& i : v) is >> i;return is;} template ostream& operator<<(ostream& os, vector& v){for (auto& i : v) os << i << ' ';return os;} const int N = 2e5 + 100; const ll inf = 2e18; ll mod1 = 998244353; ll mod = 1e9 + 7; const int imax = 1 << 30; // C:\mingw64\include\c++\12.1.0\bits g++ -std=c++20 stdc++.h void loop(){ ll n,m; cin>>n>>m; vector a(n); cin>>a; ll k; cin>>k; vector b(k); cin>>b; auto get = [&](vector &a) -> vector> { vector> res; ll sz = a.size(); for(ll i=0;i T; ll cnt = 1; ll cur = a[i]; while(cur % m == 0 and cur){ cnt *= m; cur /= m; } if(res.empty() or res.back().first != cur){ res.push_back({cur,cnt}); } else{ res.back().second += cnt; } } return res; }; vector> A = get(a); vector> B = get(b); cout << (A == B ? "YES" : "NO") << "\n"; } int main(){ ios_base::sync_with_stdio(false);cin.tie(nullptr); cout.tie(nullptr); ll t = 1; cin>>t; for(ll i=0;i
•  » » » 11 months ago, # ^ |   0 Nice username name, totally relatable ;)
 » 11 months ago, # |   +30 Another solution for F: Let $S(u)$ be a set of pairs $(x, y)$ such that $d(x, u) = d(y, u)$. Notice that $u$ with minimal number of elements in $S(u)$ is a leaf and the vertex connected to it is a vertex $v$ such that $S(v)$ contains $S(u)$ and for every pair $(x, y)$ such that $(x, y)$ belongs to $S(v)$ and doesn't belong to $S(u)$ either $x = u$ or $y = u$. We can remove that leaf and continue the process.
•  » » 11 months ago, # ^ |   0 Notice that u with minimal number of elements in S(u) is a leaf. Do you know how to prove this? It does make sense intuitively.
 » 11 months ago, # | ← Rev. 2 →   +8 Is it just me or are the codes not attached?
 » 11 months ago, # |   0 https://codeforces.com/contest/1696/submission/161805451 Can someone help me figure out why my problem C code is giving WA on test 9?
 » 11 months ago, # |   0 Hope I'm not the only one who overcomplicated D with sparse tables, sets and binary searches.
 » 11 months ago, # | ← Rev. 3 →   0 I was dazzled when I found the "more beautiful but less straightforward" solution to problem D. It was perfectly splendid! orz
 » 11 months ago, # |   0 Can any one tell why in Problem C Why my Map based solution does not work but it work by using vector>
•  » » 11 months ago, # ^ |   0 order matters, in map is ordered by key in increasing order so.
•  » » » 11 months ago, # ^ |   0 Okk Thanks for this
 » 11 months ago, # |   +1 Any other guy who got wrong answer on problem B untill realising answer can be atmost 2 !!
 » 11 months ago, # |   +8 "EDITRORIAL" of Codeforces Global Round 21. Lol :D
 » 11 months ago, # | ← Rev. 3 →   +32 I have another solution for F. It was very painful to implement, though, so I couldn't finish it during the contest. Maybe some of you had a similar thought.First of all, if x and y are even distance apart, then there must be a valid z that's equidistant from them (center of their path). Also, if x and y are an odd distance apart, then no valid z will occur, clearly. Therefore we can create a graph where there is an edge between x and y if there is a valid such z. This graph must be bipartite, so we will be able to split vertices into 2 categories.Now we will solve for the adjacent vertices of every vertex. After this, it will be pretty easy to construct a solution (and check if it is false) as we can just add in all the apparent edges. Consider the vertex v. Now, for all other vertices, we can form equivalence groups by their distance to v. Then, for each of these groups, we can check if every 2 vertices of that group are equidistant. If so, then clearly every one of these vertices is in a different component of the "graph without v". Now the size of the largest of those groups must be the degree of v, as each outgoing edge of v signifies one connected component on the "graph without v". Of course, we still are not able to pinpoint which one of these groups contains the vertices distance 1 around v. Let's say there are m such groups (groups where every 2 vertices are equidistant from each other and every vertex is equidistant from v with the largest possible size). Then they must be "circles" around v from distance 1 to m. We are trying to find the group of distance 1. This is where the bipartite property comes in: consider any point p from a group k distance away from v. If p and v are in different bipartite categories, then they are at an odd distance away from each other. Otherwise, they are even distanced away, and there will be exactly one single vertex z that is equidistant from them both, which will be in the middle of the path between p and v. This z will clearly be in the equivalence group with distance k/2 away from v. let's call this operation (obtaining a new vertex with k/2 distance) splitting. Now consider the equivalence group that splits the most. It is clear that if $k=2^ba$( a odd), then b will be the times it splits. Then, it is obvious that the largest power of 2 less than or equal to k will satisfy this property. The important part is that a vertex with a power-of-2 distance will eventually split into a vertex of distance 1 from v, and so we can obtain all the other vertices of distance 1 around v, and we are done.I believe this method as described takes $O(n^3\log{n})$ time, and it could be simplified to $O(n^3)$
 » 11 months ago, # |   0 In Q2) Won't a case like this 0 2 3 0 4 0 5 0 return 3 as answer since there are three subarrays which need to be turned into zero?
•  » » 11 months ago, # ^ |   0 In this Optimal Move would be to take whole subarray and calculate its MEX and replace it with all elements in the array then second move would be converting all array value zeroIn your Example 0 2 3 0 4 0 5 0 We first find out the mex of whole array which is 1 so array will be 1 1 1 1 1 1 1 1 then in second operation we will convert the above array to 0 0 0 0 0 0 0 0 so no more than two ways are possible
•  » » » 11 months ago, # ^ |   0 Thanks now I get it
•  » » » 11 months ago, # ^ |   0 For 0 2 3 0 4 0 5 0 ans is 1 how ?
•  » » » » 11 months ago, # ^ |   0 No ans is not one in this case beacause we will take min(2,count of total continuous non zero element) we need maximum two operation only min(2,3) will be 2
 » 11 months ago, # |   +15 Here is my solution to problem D:I have a recursive function that takes two-parameter $(l, r)$ positions of the starting and ending index in an array and calculates the optimal answer for this range.For the optimal answer, I first find the index of the minimum element and maximum element in the range $(l, r)$ and store them in $s$, $e$. $(s < e)$. I am using a segment tree and a map to find the index of the minimum and maximum in the range $(l, r)$. It is optimal to have an edge between $(s, e)$, so we add one edge.So, The answer for the range $(l, r)$ is $1$ + the answer for $(l, s)$ + the answer for $(e, r)$, and the base case is that if $l$ == $r$, there is no need to add an edge, so return $0$.
 » 11 months ago, # |   +31 Here is another solution for F:Assume that for some two nodes $u$ and $v$, we know there exist an edge between them in the solution.From this, we can find all vertices $w$ such that $dist(u, v) = dist(v, w)$, then the solution must also contain the edge $(v, w)$.Repeating that process, we can find the solution (if exists) in a bfs-like way.Therefore, for each $x$ from $2$ to $n$ we can suppose that the edge $(1, x)$ exists in the solution, try to find that solution, and see if it is valid.
 » 11 months ago, # |   +5 Great round. I especially liked that nothing between A and E is too implementation-heavy.
 » 11 months ago, # |   +8 Damn my $O(n \log^2n)$ solution for D managed to pass. :)
 » 11 months ago, # | ← Rev. 2 →   +21 Minor issue: blog title has a typo (Editorial not editrorial)feecIe6418
•  » » 11 months ago, # ^ |   0 There r quite a lot of typos .
 » 11 months ago, # |   +54 Here is $O(n^3)$ solution to F. First we can find the farthest distance from any vertex $x$ to other. So we know the diameter of the tree. If we root the tree at the center, we can know the depth of every vertex. So we can determine at least one edge in the tree (node with depth 1 and the root), then use the method in the editorial. It also shows there is at most one valid answer.
 » 11 months ago, # |   0 That's quick.
 » 11 months ago, # |   -15 I think the contest has too much observation.
•  » » 11 months ago, # ^ |   +1 As is literally every codeforces round including div 3, div.2, educational, div1+div2 combined, div1, olympiad-based rounds?(yes I know that div.4 exists but I don't have a very fond experience in div.4)
 » 11 months ago, # |   +3 a bit of pity for Dpass pretest make me think it works anywaybut didn't come up with cases like 1 100000 2 99999 3 99998 4 99997 ...then got fsttry to consider more next time. or maybe always need to try to achieve as low complexity as i canit's actually a great problem though, and solution 1 is awesome.
•  » » 11 months ago, # ^ |   -7 why so many downvotes
 » 11 months ago, # |   0 For D, what if the maximum element is 1 or n?
 » 11 months ago, # |   0 This time i screwed up my time on Div2C using Map to store the counts and matching them (which is not possible) because it leads to a very bigger value which cannot be stored. Using two pointers is a saviour
 » 11 months ago, # |   0 Could someone please help me to find me the error in my code of problem D I am using approach 2 https://codeforces.com/contest/1696/submission/161834104
•  » » 11 months ago, # ^ |   0 Take a look at Ticket 14387 from CF Stress for a counter example.
•  » » » 11 months ago, # ^ |   0 Ohh yes Got it Thanks!!
 » 11 months ago, # | ← Rev. 2 →   +16 In problem G, when I set const double INF = 1.0 / 0.0; It got TLE on test 76 (or Pretest Passed 5880ms, and TLE on test 7 if I unroll the loops in matrix multiplication myself) with GNU C++14 (32bit), but ~850ms with GNU C++20 (64bit, winlib).However, when I set const double INF = 1e18; Its speed remains unchanged with GNU C++20 (64bit, winlib), but when compiled by GNU C++14 (32bit), it works in <500ms and becomes the fastest submission.Is there any logic behind this (about inf in double)?
•  » » 11 months ago, # ^ | ← Rev. 3 →   0 An explanation for the first (but not very informative) is that diving by zero (even with floating numbers) is undefined behavior, (according to [expr.mul.4], or discussions in StackOverflow), and anything can happen with undefined behavior.
•  » » 11 months ago, # ^ | ← Rev. 2 →   0 a better suggestion might be using std::numeric_limits::infinity() as the value for inf. this is not undefined behaviour and still compares bigger than the maximum value representable with double.
 » 11 months ago, # |   +1 If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints. If you are not able to find a counter example even after changing the parameters, reply to this thread (only till the next 7 days), with links to your submission and ticket(s).
 » 11 months ago, # |   0 great tutorial
 » 11 months ago, # |   0 Can you please brief me, if the test case would 5 2 0 3 0 5 how the answer would be 2 or less explaining the l and r for each operation?I didn't understand...sorry :(
•  » » 11 months ago, # ^ |   0 in first operation,you can take l=1 and r=6(basically the entire array),so the new array will be 1,1,1,1,1,1. In second operation,again select l=1 and r=6,the array will now be 0,0,0,0,0,0.
•  » » » 11 months ago, # ^ |   0 For a collection of integers S, define mex(S) as the smallest non-negative integer that does not appear in S....Then it means I can take any smallest non negative integer? it's not necessary that it should be less than all the elements of the array right?
•  » » » » 11 months ago, # ^ |   0 No it's not necessary.But you cannot just take "any" smallest non negative integer. for example-Mex(5,2,0,3,0,5) will be 1 because 1 is the smallest non negative integer which does not appear in this array.
•  » » » » » 11 months ago, # ^ |   0 thank you so much... <3
•  » » » » » 11 months ago, # ^ |   0 But how number of operation for (5,2,0,3,0,5) is 1.
 » 11 months ago, # |   0 can anyone please explain the proof for problem c with intution by taking an example? i couldnt understand editorial
•  » » 11 months ago, # ^ |   0 Try expanding $a$ and $b$ into $a^\prime$ and $b^\prime$ in the example test cases.
•  » » » 11 months ago, # ^ |   0 i have expanded both the arrays upto maximum extent as possible but im not getting proof/intution.
•  » » » » 11 months ago, # ^ |   +3 Now notice that it is possible to obtain $a^\prime$ from $a$ after some operations, and it is possible to obtain $b$ from $b^\prime$ after some operations, so if $a^\prime = b^\prime$, we can obtain $b$ from $a$.We still need to prove that if $a^\prime \ne b^\prime$, it is impossible to obtain $b$ from $a$ after any number of operations.To do so, note that the fully expanded form of $a$ does not change when you perform one of the operations on it.
 » 11 months ago, # |   -24 shit contest. downvoted
 » 11 months ago, # |   0 What does it mean by "z will always become a submask of itself after any number of operations, so ai will always be a submask of (ai or z) after any number of operations"? Please explain.
•  » » 11 months ago, # ^ |   0 Basically, $z$ will only lose bits.So $(a_i\mathrm{\ or\ } z^\prime) \le (a_i\mathrm{\ or\ } z)$, where $z^\prime$ is $z$ after some operations.
•  » » » 11 months ago, # ^ |   0 Okay, but what is the meaning of submask here specifically. Is it like changing the set bits of z after any number of operations so the resulting bit representation i.e. bit mask obtained is called submask?
•  » » » » 11 months ago, # ^ |   0 $z^\prime$ is a submask of the bitmask $z$, since every bit that is set in $z^\prime$ is also set in $z$, but not necessarily vice versa.
•  » » » » » 11 months ago, # ^ |   0 It means new bitmask obtained after changing only the set bits of a bitmask is known as submask of that bitmask. Am I right?
•  » » » » » » 11 months ago, # ^ | ← Rev. 2 →   0 Sounds right
 » 11 months ago, # |   0 the explanation for problem c is very good.
 » 11 months ago, # |   0 Find Solve problems for C ,orz,%%%，thans
 » 11 months ago, # | ← Rev. 3 →   0 Why this code is working fine for question A? for(int i = 0; i < a.size(); i++){ cin >> a[i]; a[i] = a[i] | z; z = a[i] & z; ans = max(ans, a[i]); } Here I am performing both the operations — bitwise or and bitwise and. Also why it is not needed to perform second operation i.e bitwise as given in tutorial, any proof?
•  » » 11 months ago, # ^ |   0 You are doing:  x = (a[i] | z) y = x & z z = y Every bit in z that is 1 is also 1 in x, so (x & z) equals z. In other words, you aren't changing the value of z and the second operation is doing nothing.
 » 11 months ago, # | ← Rev. 2 →   0 Have a solution different from the tutorial for problem D which does not use segment tree or stacks, very difficult for me to explain how it works but the following ideas might help-$1.$ $Its$ $always$ $optimal$ $to$ $jump$ $to$ $the$ $farthest$ $index$ $from$ $current$ $index.$$2.$ $We$ $always$ $jump$ $from$ $a$ $local$ $maxima$ $to$ $a$ $local$ $minima,$ $and$ $then$ $to$ $a$ $local$ $maxima$ $and$ $so$ $on.$161975222
 » 11 months ago, # | ← Rev. 2 →   +18 For F, for each $i$, one can assume that edge $(1, i)$ is in the tree, and then try to construct the rest of the tree, as per hint 2. We can then check if the tree is valid.At the start, for each node $v$, we can do a $O(n^2 \alpha(n))$ precomputation of the equivalence classes of nodes equidistant from $v$. Then, we can do each tree reconstruction and check in $O(n^2)$, for a total complexity of $O(n^3 \alpha(n))$.
 » 11 months ago, # | ← Rev. 2 →   0 -
 » 11 months ago, # |   0 Can someone explain the equation given in Problem E?
 » 10 months ago, # |   0 Hi, could someone take a look at why I'm getting WA on test case 3 of F? My submission is here.Specifically, I create equivalence classes for each node; each equivalence class represents equal distance from said node. This is done using DSU's, which should make the whole thing have complexity $O(n^3)$. Thanks!
 » 10 months ago, # |   0 I got a solution for F which solves it in $O(n^3)$Well-known Theorem: there is atmost two centres in a tree (a center is a vertex with minimum value of maximum distance of a vertex from the given vertex: this value is called eccentricity).Note that using the given information, we can find the eccentricity of a vertex: this is just the number of equivalence classes of vertices wrt any given vertex (two vertices belong to the same equivalence class wrt a given vertex if they have the same distance from that given vertex).So we can easily find the centre(s) of the tree. If there are two centers, there is a theorem that they must be connected, so we find an edge immediately and proceed to construct the tree.If there is one center, then we can prove that all adjacent vertices have eccentricity of exactly one greater than the center, and all other non-adjacent vertices have eccentricity $\geq e+2$, where $e$ is eccentricity of the center. So in this case, we can find any node with $e^\prime = e+1$ and hence, these two must be connected, and we have found an edge.
 » 9 months ago, # |   0 you should have explained the reason for 2 being the maximum ans.
 » 8 months ago, # | ← Rev. 2 →   0 Can someone explain me why I am getting TLE on problem C in test 11 because according to me my program is running in O((n+k)logmV) (as given in the editorial) . Instead of storing frequency I am just using a count variable to check whether expansion of both array will be same. thanks https://codeforces.com/contest/1696/submission/173329854
 » 6 months ago, # |   0 In problem E, if you don't know the equation : $\sum_{i = 0}^kC_{n+i}^n = C_{n+k+1}^{n+1}$, here's the proof:first, you have to know $C_{a}^b = C_{a - 1}^b + C_{a - 1}^{b - 1}$then, $\sum_{i = 0}^kC_{n+i}^n = C_n^n+C_{n+1}^n+C_{n + 2}^n + ...+C_{n+k}^n\\ =C_{n+1}^{n+1} + C_{n+1}^n + C_{n + 2}^n ... + C_{n + k}^n\\ =C_{n + 2}^{n + 1} + C_{n + 2}^n + ... + C_{n + k}^n\\ =C_{n + 3}^{n + 1} + ... + C_{n + k}^n\\ =...\\ =C_{n + k}^{n + 1} + C_{n + k}^n\\ =C_{n + k + 1}^{n + 1}$