By hu_tao, 7 weeks ago,

Hi all!

This weekend, at Oct/17/2021 14:05 (Moscow time) we will hold Codeforces Round #749 (Div. 1 + Div. 2, based on Technocup 2022 Elimination Round 1). It is based on the problems of Technocup 2022 Elimination Round 1 that will be held at the same time.

Note the unusual start time of the contest.

Technocup is a major olympiad for Russian-speaking high-school students, so if you fall into this category, please register at Technocup website and take part in the Elimination Round.

The Div. 1 + Div.2 edition is open and rated for everyone. Register and enjoy the contests!

The problems were written and prepared by Tlatoani, golions, rabaiBomkarBittalBang, qlf9, and me. We would like to express our thanks for antontrygubO_o, isaf27, and KAN for reviewing our problems and being great coordinators!

Huge thanks to the following users for testing our round: kefaa2, AmShZ, dorijanlendvaj, Keshi, czhang2718, 2020akadaver, Magikarp1, Richw818, quantum8, RayLee234, I_Love_YrNameCouldBeHere, Qualified, 1-gon, smax, m371, kassutta, namanbansal013, HackerMonk, Ari, PurpleCrayon, FieryPhoenix, Jellyman102, bWayne, Omkar, Aleks5d, Makcum888

And as usual, thanks to MikeMirzayanov for the great Codeforces and Polygon platforms.

You will have 2 hours and 15 minutes to solve 9 problems. The score distribution will be announced very shortly before the contest starts. Good luck to all!

UPD1:

Score distribution: $500$ — $1000$ — $1500$ — $1750$ — $2250$ — $2750$ — $3000$ — $3500$ — $4000$.

UPD2:

Thanks to everyone who participated in the contest! We hope you enjoyed the problems. We apologize for the issues at the beginning of the contest; we hope that you were still able to have a great experience.

Editorial

UPD3:

Congratulations to the winners of Codeforces Round #749 (Div. 1 + Div. 2, based on Technocup 2022 Elimination Round 1)!

And a special congratulations to peti1234 for being the only contestant to solve problem I!

Congratulations also to the winners of Technocup 2022 - Elimination Round 1!

• +460

 » 7 weeks ago, # |   +30 see you next banner
 » 7 weeks ago, # |   +73 Note the unusual timings :)
•  » » 7 weeks ago, # ^ |   +33 Added to the announcement :)
 » 7 weeks ago, # |   +73 challenging problems.
•  » » 7 weeks ago, # ^ |   +14 9 challenging problems in just 2:15 hour? isn't that quite less?
•  » » » 7 weeks ago, # ^ |   0 Maybe it is...
 » 7 weeks ago, # |   0 hoping for a good contest :)
 » 7 weeks ago, # | ← Rev. 2 →   +6 Hoping to be back to cyan. working hard to become expert.
 » 7 weeks ago, # |   +54 Clash with Atcoder Beginner Contest :(
 » 7 weeks ago, # |   +10 Damn 9 problems in 2:15 hrs
 » 7 weeks ago, # |   +4 Can we participate without being from a Russian speaking country?
•  » » 7 weeks ago, # ^ |   +8 You can register for the contest based on this (#749)
 » 7 weeks ago, # |   +7 May the force be with you. Good luck to you all :))
 » 7 weeks ago, # |   +30 As a tester, good luck!
 » 7 weeks ago, # |   -35 Can I see pretest examples in my solution?
 » 7 weeks ago, # | ← Rev. 2 →   +3 MAy the OOds be ever in ur favor
 » 7 weeks ago, # |   0 Looking forward to solve problems and see a hike in my rating.
 » 7 weeks ago, # |   +12 The only bad thing is the time of the contest. There is another contest in atcoder at the same time.
 » 7 weeks ago, # |   +12 9 problems，so much!!!!
•  » » 7 weeks ago, # ^ |   -18 May be there will be some subtask problems.
 » 7 weeks ago, # |   -25 Solve 9 problems within 2 hours and 15 minutes... The time limit is too tight!!!
•  » » 7 weeks ago, # ^ |   0 Probably first few problems would be ez :) . Otherwise the time is very tight.
•  » » » 7 weeks ago, # ^ |   +25 ...
•  » » 7 weeks ago, # ^ |   +2 for LGMSs it's not so tight, for Div2 it's not big difference to solve first 3-4 problems in 2:15 or in 2:45 for example
•  » » 7 weeks ago, # ^ |   0 I had only 10 minutes for the last three problems,so I just left and took a look at Atcoder Beginner Contest :(
 » 7 weeks ago, # | ← Rev. 2 →   -142 great
•  » » 7 weeks ago, # ^ |   +28 Woah cheater has the guts to comment!How are you cheater?
•  » » » 7 weeks ago, # ^ | ← Rev. 2 →   +1 how he is cheater. I also need the third eye ;)PS: Lol! he changed his comment from "Hope again we will solve at least 3,4 problems . best of luck everyone !" to "great" XD.
•  » » » » 7 weeks ago, # ^ |   0 he/she adds random comments for avoiding plagiarism check.
•  » » » » » 7 weeks ago, # ^ |   0 Sad thing is, they have actually figured out how to circumvent plagiarism checks.
•  » » » » 7 weeks ago, # ^ |   +10 look at his solution for problems during the contest... there are more comments in code than the code itself
•  » » » » » 7 weeks ago, # ^ |   +32 oh! got it. An expert cheater XD
•  » » » 7 weeks ago, # ^ |   +7 His way of writing code is so terrible, he got rank 47 by cheating, another terrible news!
•  » » 7 weeks ago, # ^ |   +37 solve copy paste
•  » » » 7 weeks ago, # ^ |   0 I have solved the problems like f, too.
•  » » 7 weeks ago, # ^ |   +37 Kitni cheating karega be?
•  » » 7 weeks ago, # ^ |   +5 I think I now know why "we" was used :|
 » 7 weeks ago, # |   +6 May Mike be with us.
 » 7 weeks ago, # |   +40 lighthearted meme
•  » » 7 weeks ago, # ^ |   +8 memeMe: How many coordinators reviewed your problems?Authors: Yes
•  » » » 7 weeks ago, # ^ |   -10 memeCodeforces: What is the difficulty of the problems?.Authors: Yes
 » 7 weeks ago, # |   +1 This contest clashes with AtCoder Beginner Contest 223 at 17:30 (UTC+5.5)
•  » » 7 weeks ago, # ^ |   0 Yeah that's sad!.Gonna have to leave atcoder this time :(
 » 7 weeks ago, # | ← Rev. 3 →   +5 have you noticed these days less number of people participating compared to two months earlier.
•  » » 7 weeks ago, # ^ |   0 maybe the college/school is starting... idk
•  » » » 7 weeks ago, # ^ |   0 ya i agree with you
 » 7 weeks ago, # |   +16 daytime in China,finally dont't need to stay up late
 » 7 weeks ago, # |   0 hoping for positive delta and also:1 манул)
 » 7 weeks ago, # | ← Rev. 2 →   +1 Looks like companies wanted to see each other clashes
 » 7 weeks ago, # |   0 everyone can register to the Technocup 2022 — Elimination Round.isn't it supposed to be private register?
 » 7 weeks ago, # |   0 :( Clashes with The International final
 » 7 weeks ago, # |   -12 Accroding to tradition,This Contest might be delayed:(
 » 7 weeks ago, # |   +3 Contest begin, my province: shut down the electricity.
 » 7 weeks ago, # | ← Rev. 2 →   0 todays contest be like "you all lie under my shoes"
 » 7 weeks ago, # |   0 Very very difficult questions !!
 » 7 weeks ago, # |   0 the problems are very hard, should be div. 1 only imo.
 » 7 weeks ago, # |   0 Tree problem in B? why...
•  » » 7 weeks ago, # ^ | ← Rev. 4 →   0 note that m
 » 7 weeks ago, # |   -25 Div.1 + Div.2 = Div.1.5
•  » » 7 weeks ago, # ^ |   +13 floor((1+2)/2)
 » 7 weeks ago, # |   +17 Div2 rounds based on some Russian contest for school kids are always harder than usual Div2 rounds.
•  » » 7 weeks ago, # ^ |   +3 Le the russian kid:
 » 7 weeks ago, # |   +34 Imagine wasting 30+ mins on D because you forget to assert the values of $a_i$ in a query and print $a_i = n + 1$ in a certain case T_T.But my mistakes aside, absolutely brilliant contest, one of the best I have seen in a while — Not a single boring problem from A-E! (can't talk about the rest since I haven't solved them, though F does look interesting as well)E is a really really really cool problem — it looks insanely complex at first but decomposes to pretty easy ideas through some cool observations.
 » 7 weeks ago, # |   0 Nice C I got it but too late
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   0 Sameeee :(, there was just one simple observation and i over complicated that problem, got the idea only after a min of the contest end
 » 7 weeks ago, # |   +1 What could be the testcase 3 for C?
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   0 Likely some mistake with not checking if cells which are $X$ could hypothetically escape if they weren't $X$. If that isn't the case you can't determine if it was initially $X$ or not. Forgetting to check that caused WA3 for me.
•  » » » 7 weeks ago, # ^ | ← Rev. 3 →   0 I looked for patterns like: _X \n X. where _ is any character, Here [2,2] can be both X or . , so this subgrid is indeterminable. Did I miss something?
•  » » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 You were supposed to look for the pattern  X X _ UPD: Oops, finding both patterns is the same thing, you are right
•  » » 7 weeks ago, # ^ | ← Rev. 7 →   0 I removed my WA on 3 by accounting for the fact that the leftmost column in the subgrid need not be considered for finding an ambiguous cell since the leftmost column will always be unambiguous. so we only look to need to look for ambiguous cells in (x+1,y).
 » 7 weeks ago, # |   0 In problem C XX XXquery : can 1 2 is determinable ?
•  » » 7 weeks ago, # ^ |   0 Do you mean XX \n XX? Then it's not determinable.
•  » » » 7 weeks ago, # ^ |   0 Y ?
•  » » » » 7 weeks ago, # ^ | ← Rev. 2 →   +5 Because, we can't determine the state of (2,2) cell exactly without looking at the grid. Suppose, instead of XX XX We're given, XX X. Then, still none are exitable, but one cell in the latter is empty. So, undeterminable!
•  » » » » » 7 weeks ago, # ^ |   0 Ok
•  » » » » » 7 weeks ago, # ^ |   +8 Thanks for putting me out of my misery. I spent around 2 hrs struggling with this problem. Now that I know, no one deserves that -100 more than me, I am at peace. Thanks again.
•  » » » » 7 weeks ago, # ^ |   0 because XX \n XX and XX \n X. will both result in NN \n NN , hence not determinable
 » 7 weeks ago, # |   -9 A was much harder than B. Really disapointed about not reading problem B first
•  » » 7 weeks ago, # ^ |   +1 wtf, i insta-solved A and only managed to solve B with 2 minutes remaining
•  » » » 7 weeks ago, # ^ |   +3 Same. Lool. I feel a little better now for struggling at B. Thank you.
•  » » » 7 weeks ago, # ^ |   -9 B isn't that much tougher than A. I mean the statement literally highlights $m \lt n$ in bold which is the key idea to an easy enough pigeonhole idea.
•  » » » » 7 weeks ago, # ^ |   0 oh wow! clearly i didn't notice the bolding
•  » » » » 7 weeks ago, # ^ |   0 But it did not state, as is customary, that it can be proven that under the given constraints the solution always exists.
•  » » 7 weeks ago, # ^ |   0 This guy is on drugs
•  » » 7 weeks ago, # ^ |   0 Another math hater.
 » 7 weeks ago, # |   +15 is this contest is for High-school ??
•  » » 7 weeks ago, # ^ |   +122 It's Russian highschool level which is roughly the same difficulty as a U.S. post-doctorate program or a Chinese gradeschool contest.
•  » » » 7 weeks ago, # ^ |   0 This isn't a joke, is it? :)
•  » » » » 7 weeks ago, # ^ |   +13 Yes, but also "It's funny because it's true"
•  » » » 7 weeks ago, # ^ |   +4 Most probably not even a gradeschool contest Chinese contest because all the problems were well known tricks.
•  » » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 Why did your graph nosedive then?:)
 » 7 weeks ago, # |   +36 Problem E is such a problem, where you know that the first thing that comes to your mind has to be correct [path does not matter], otherwise it will be NP-hard or something.
 » 7 weeks ago, # |   +8 What is wrong in this approach for Problem CI check the minimum answer for each column with BFS and for each query I get the maximum for each column $C_l$ $C_(l+1)$ ... $C_r$, If it's less than L, print "YES", otherwise print "NO"
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   +6 had the same idea, WA pretest 3 :(
•  » » 7 weeks ago, # ^ |   +3 I did something similar but got WA on test 3.
•  » » 7 weeks ago, # ^ |   +3 Maybe you did not handle if a blocked cell itself cannot exit the sub-graph if it was not blocked. In this case we will not be able to know if its N represents a blocked or an empty cell.
•  » » » 7 weeks ago, # ^ |   0 Can u explain why do I need to check that?
•  » » 7 weeks ago, # ^ |   +16 Are you checking if cells which are $X$ would be theoretically exitable if they weren't $X$ as well? Suppose one of those cells is not exitable even if it wasn't $X$, then you wouldn't be able to differentiate between it being initially marked $X$ or not, so the grid isn't determinable.I forgot about this and got WA3 because of that.
•  » » » 7 weeks ago, # ^ |   0 aah so you are saying that for n=2 m=2 XXXX query (1,2) should be NO instead of YES?
•  » » » » 7 weeks ago, # ^ | ← Rev. 2 →   +11 That's correct, because it could also beXXX.Both situations are identical in the view of exitability, since all 4 cells are not exitable.
•  » » » » » 7 weeks ago, # ^ |   0 Well I understand now
•  » » » 7 weeks ago, # ^ |   0 I can't understand why I need to check If $X$ would be theoretically exitable if they weren't $X$.I am checking if there is empty cell is not exitable, if there is atleast one then I can't differentiate.
 » 7 weeks ago, # |   0 Nice problems. Though it would be better (at least for me) to extend the duration of the contest... I just gave up when I finished reading problem G and found out that there was only 20 minutes left.
 » 7 weeks ago, # |   0 hint for B please
•  » » 7 weeks ago, # ^ |   +5 $m •  » » » 7 weeks ago, # ^ | 0 I made edges a -- c for the given m restrictions. Then, to get the remaining edges I connected all separate components (checked using DSU) by an edge. Whats wrong with this? I kept getting WA2. •  » » » » 7 weeks ago, # ^ | +5 Connecting all edges a-c may result in a cycle even when m •  » » » » » 7 weeks ago, # ^ | ← Rev. 2 → 0 EDIT: This will fail thsi test case  1 4 3 1 2 3 3 1 2 2 3 1Thanks. I did realize this towards the end, so added the check for cycles even while adding the initial$m$edges from the restrictions. This is what I did:add edge$a$—$c$if they arent in the same componentif$a$and$c$are already part of the same component, add edge$b$—$j$instead.$j$is any node apart from$a$,$c$and$b$. Will this work? It didnt work during the contest because I was printing$0$-indexed$j$node. •  » » » » 7 weeks ago, # ^ | +5 Consider this case, 4 3 1 2 3 3 1 2 2 3 1In your final answer, the third constraint will not be satisfied. •  » » » » » 7 weeks ago, # ^ | 0 Thanks. Got it. •  » » 7 weeks ago, # ^ | 0 Make b[i] leaves •  » » 7 weeks ago, # ^ | +5 It's given 1 < m < n .So there will be at least one node that can be between any two nodes, make it root. Now just connect all the other nodes to it. Spoiler  » 7 weeks ago, # | 0 My approach for B: I basically checked which node is not present as bi in the restrictions, then i used this node to create edge to every other node. but this gives WA on pretest 2 Can anyone explain where i am going wrong?? •  » » 7 weeks ago, # ^ | +3 its correct its my solution too u probably implemented it wrong •  » » » 7 weeks ago, # ^ | 0 oh thanks! let me find my mistake. •  » » 7 weeks ago, # ^ | +5 Check if your bi is 0-indexed or 1-indexed. I had the same problem where I accidentally read in all bi's 1-indexed, and changing it to 0-indexed fixed it. •  » » 7 weeks ago, # ^ | 0 I also did same.. May be you have done some mistake in implementation  » 7 weeks ago, # | ← Rev. 2 → +3 Nice problem set.  » 7 weeks ago, # | ← Rev. 2 → 0 Anyone else getting RTE on pretest 25 on Problem E?Update: Figured it out. Dumb mistake, I was trying to pick a starting point for the spanning tree by finding a vertex with a nonzero number of queries, but accidentally set the starting point to be the number of queries itself instead of the vertex id. In hindsight, could have just rooted the spanning tree at vertex 1.  » 7 weeks ago, # | ← Rev. 2 → 0 https://codeforces.com/contest/1586/submission/132264873can anyone help with finding bug in this solution for C? •  » » 7 weeks ago, # ^ | 0 found a bug, there was incorrect handling of invalid columnshere is the fixed submission if someone would struggle with similar bug https://codeforces.com/contest/1586/submission/132293465  » 7 weeks ago, # | 0 Did someone see F before? ko_osaga? •  » » 7 weeks ago, # ^ | ← Rev. 2 → +6 F has very similar solution to COCI 2020-2021 Contest -4 Hop .Unfortunately I recalled that I had done this problem before just after the contest ended. •  » » 7 weeks ago, # ^ | +18 A classic result is that if a directed graph with chromatic number$\chi$is edge-colored with$r$colors and$k^r < \chi$, then there exists a monochromatic path of length$k$. Problem F is just the construction to show that this result is sharp. •  » » 7 weeks ago, # ^ | +11 The second sample kinda gives away the solution. They should have made it more obscure. •  » » » 7 weeks ago, # ^ | ← Rev. 2 → +5 I mean if you already came up with something like k-nary numbers, then probably it might help. But I'm not sure you can deduce something without prior knowledge.EDIT: looking at the editorial, it seems more clear what did you mean by that. •  » » 7 weeks ago, # ^ | ← Rev. 2 → +18 I conjectured that the solution will be something like this.Btw why are you tagging me?? •  » » » 7 weeks ago, # ^ | +26 6 min between submits, also you are a legend :) •  » » » » 7 weeks ago, # ^ | +13 thanks for the compliment!!  » 7 weeks ago, # | +14 I liked F very much, thanks for the round :) •  » » 7 weeks ago, # ^ | +19 I think problem F is more like a MO problem than a OI problem.  » 7 weeks ago, # | ← Rev. 2 → -8 (Deleted)  » 7 weeks ago, # | -67 The parallel AtCoder abc223 had better quality of programming problems. •  » » 7 weeks ago, # ^ | +124 well, the quality of the problemset does not depend on whether you can solve them or not.  » 7 weeks ago, # | 0 Chinese problemsetting forces invading Russia lol  » 7 weeks ago, # | ← Rev. 2 → +8 Problems are great, but I personally think the duration is a bit short, especially for data structure problems like H. Sadly I wasn't able to debug my code in time :(more sadly, I succeeded in debugging it 10 minutes after the contest ended :(  » 7 weeks ago, # | 0 Did anyone else get WA on test 6 for problem E? •  » » 7 weeks ago, # ^ | +5 Your DP part is probably incorrect. 6 5 1 2 1 3 1 4 3 5 3 6 3 2 4 1 5 3 6 Output should be 3. •  » » » 7 weeks ago, # ^ | 0 I see thanks!  » 7 weeks ago, # | 0 Is C a segment tree problem? •  » » 7 weeks ago, # ^ | 0 More like dp-problem •  » » » 7 weeks ago, # ^ | 0 More like ad-hoc problem •  » » 7 weeks ago, # ^ | +1 No, much simpler than that.Hint: Consider under what situations will a single cell not be determinable. •  » » 7 weeks ago, # ^ | +1 It can be used (I used it) but not necessary •  » » 7 weeks ago, # ^ | +56 Solution in 1 sentenceThe subgrid is bad if there is ?X X?  •  » » 7 weeks ago, # ^ | -18 Nope, its dp combined with a sliding window like idea.The core idea is that if a cell can't exit the grid due to being blocked by cells above / to the left of it, it would be non-exitable regardless of whether it was$X$or not. So all cells in a subgrid with$1 \leq i \leq n$,$x_1 \leq j \leq x_2$must not be blocked for the answer to be yes.Basically let$minrow_{i, j}$and$mincolumn_{i, j}$be the smallest row and column reachable from a cell$(i, j)$. Then the minimum$x_1$for a given$x_2$is$max(mincolumn_{i, j})$where$1 \leq i \leq n$,$1 \leq j \leq x_2$and$maxrow_{i, j} \gt 1$. This can be calculated quickly for all$x_2$with an easy observation — Since the function is max,$x_1$never decreases as$x_2$increases. So we can just iterate first on increasing$j$then on$i$to calculate the answer in$O(n \times m)$time. Code#include #define int long long using pii=std::pair; using namespace std; int n, m, q; int32_t main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m; vector> grid(n, vector(m)), minrow(n, vector(m, n)), mincol(n, vector(m, m)); for(int i = 0; i < n; i++) { string s; cin >> s; for(int j = 0; j < m; j++) grid[i][j] = (s[j] == 'X'); } for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) { minrow[i][j] = i; mincol[i][j] = j; if(i > 0 && !grid[i - 1][j]) { minrow[i][j] = min(minrow[i][j], minrow[i - 1][j]); mincol[i][j] = min(mincol[i][j], mincol[i - 1][j]); } if(j > 0 && !grid[i][j - 1]) { minrow[i][j] = min(minrow[i][j], minrow[i][j - 1]); mincol[i][j] = min(mincol[i][j], mincol[i][j - 1]); } } vector minl(m); int curminl = 0; for(int j = 0; j < m; j++) { for(int i = 0; i < n; i++) if(minrow[i][j] != 0) curminl = max(curminl, mincol[i][j]); minl[j] = curminl; } cin >> q; for(int i = 0; i < q; i++) { int l, r; cin >> l >> r; l--; r--; if(minl[r] <= l) cout << "YES\n"; else cout << "NO\n"; } return 0; }  •  » » 7 weeks ago, # ^ | +3 My solution is if there's an empty cell on column i, and it is blocked, then it is bad.So I use dp to check the furthest left a cell could and store the max for all cell of that column, then use segment tree to check max(l,r) <= l •  » » 7 weeks ago, # ^ | 0 I aolved with seg tree tho idk it was the only soultion that came into my mind  » 7 weeks ago, # | -62 CF goes down every 2 minutes: Maybe Codeforces developers didn't do enough leetcode!!!  » 7 weeks ago, # | +32 Does anyone have a rigorous proof why arbitrary spanning tree works for E? •  » » 7 weeks ago, # ^ | +3 It suffices to prove that, for a given tree and$u,v,w \in V$, edges which appears in exactly one of the simple path$uv$and$vw$forms the simple path from$u$to$w$. This should be verified easily. •  » » 7 weeks ago, # ^ | 0 First let's think of it as a dfs tree after getting a dfs tree.what you can do if you have a range of edges of ones on this tree is that you remove this range and replace it with one edge with 1 which is a back edge this edge will also have a 1 and since this edge is mapped to a range of edges it's obvious that you can't make it into a 0.I think it's the same with spanning trees the difference is the edges are not back edges but they are still mapped to one range of edges. •  » » 7 weeks ago, # ^ | ← Rev. 2 → +10 The existence of an example is equivalent to all nodes participating in an even number of paths as endpoints. => is trivial, <= can be shown easily to hold for any tree (consider any edge, if it is used an odd number of times, the sum of usages in one of the subtrees would be odd as well). •  » » 7 weeks ago, # ^ | +41 path from u to v = (path from u to root) xor (path from v to root)  » 7 weeks ago, # | 0 Feeling dumb af for not solving B •  » » 7 weeks ago, # ^ | ← Rev. 2 → -68 NO!!!! you are not  » 7 weeks ago, # | ← Rev. 2 → 0 What is the solution for D? Best idea I got was a randomized algorithm with expected number of queries to be exactly 2*n(which didn't pass as expected) •  » » 7 weeks ago, # ^ | ← Rev. 4 → +12 Suppose we can find$p_n$in at most$n$queries, then we can find all other values in at most$n$queries by increasing$a_1, \ldots, a_{n - 1}$or$a_n$by the required amount for it to match each value$1 \leq k \leq n$, one at a time.As for finding$p_n$, suppose I set$a_1, \ldots, a_{n - 1} = 1$and$a_n = x$, then we will only get$0$as a response if$p_n + x > n + 1$(or$p_n + x > (n - 1) + 1$if$p_n$is$n$). So we can just iterate on all values of$x$from$2$upward and see the first value for which the condition fails to hold to exactly identify$p_n$. Code#include #define int long long using pii=std::pair; using namespace std; int n, query_cnt = 0; int query(vector& vals) { assert(vals.size() == n && ++query_cnt <= 2 * n); for(auto x : vals) assert(x >= 1 && x <= n); cout << "? "; for(auto x : vals) cout << x << " "; cout << endl; int resp; cin >> resp; return resp; } int32_t main() { cin >> n; vector ans(n, 0); for(int laval = 1; laval <= n; laval++) { if(laval == n) { ans[n - 1] = 1; break; } vector queryvals(n, 1); queryvals[n - 1] = laval + 1; int resp = query(queryvals); if(resp == 0) // p_n + laval (+ 1) = n + 1 (+ 1) { ans[n - 1] = n + 1 - laval; break; } } assert(ans[n - 1] != 0); for(int i = 1; i <= n; i++) { if(i == ans[n - 1]) continue; if(i < ans[n - 1]) { vector queryvals(n, ans[n - 1] - i + 1); queryvals[n - 1] = 1; int resp = query(queryvals); assert(resp != 0 && resp != n); ans[resp - 1] = i; } else // i > ans[n - 1] { vector queryvals(n, 1); queryvals[n - 1] = i - ans[n - 1] + 1; int resp = query(queryvals); assert(resp != 0 && resp != n); ans[resp - 1] = i; } } assert(ans.size() == n); set sanity_check; for(auto x : ans) sanity_check.insert(x); assert(sanity_check.size() == n); cout << "! "; for(auto x : ans) { assert(x >= 1 && x <= n); cout << x << " "; } cout << endl; return 0; }  •  » » 7 weeks ago, # ^ | ← Rev. 3 → +11 Hint: Create an undirected graph with N vertices where edge u-v indicates abs(p[u]-p[v])=1.If you figure this out it's simple. All that is left is running a dfs. •  » » » 7 weeks ago, # ^ | 0 wait, what? XD I need to think about it •  » » » » 7 weeks ago, # ^ | +3 aaah, smart •  » » 7 weeks ago, # ^ | -10 My solution:For any given$p_i=v$, suppose there is some$j$such that$p_j=v+1$.- If$ij$, this$(i,j)$pair can be found by a query with$a_i=1$and all other$a_k=0$, which will return$j$.So doing$n$queries with each$a_i=1$and another$n$queries with each$a_i=-1$gives us the exact ordered pair of indices at which each pair of consecutive values$v$and$v+1$occurs, as well as the exact location of$1$and$n$.Technicality: each query needs to have all$a_i>0$. Just add an offset to all query values. •  » » 7 weeks ago, # ^ | ← Rev. 2 → +2 You can also solve it with a tighter query limit using binary search:The idea is if you find the last element, you can find every other element in$n$queries. We can find the last element by performing a binary search to find$p_n - min(p_{n - 1}, p_{n - 2}, ...)$. If this value is negative, it means the last element is 1. So we only end up consuming$n + logn$queries :)  » 7 weeks ago, # | 0 problem D was really nice, I enjoyed it very much.  » 7 weeks ago, # | 0 Can someone point out my mistake on C? https://codeforces.com/contest/1586/submission/132256767 •  » » 7 weeks ago, # ^ | ← Rev. 2 → 0 I think, you should delete this line:$if(Grid[i][j] == 0){$EDIT: It still struggles with test 4, Idk what else is wrong. •  » » » 7 weeks ago, # ^ | 0 Oh , but if it's a X, then we can include that column rt?Like this, . . x . . . x . . x x . . x [.] . . . . . . . . . . . . . . . . .  •  » » » » 7 weeks ago, # ^ | 0 In such a construction of two diagonally adjacent 'X' cells, the cell between them will always be non-exitable, regardless of what is written in it. Thus, we can change its state and get a different initial table with the same set of exitable cells, so we have to consider the mentioned case too and include that column. •  » » » » » 7 weeks ago, # ^ | 0 Ah my bad, didn't understand the statement clearly.  » 7 weeks ago, # | 0 can anyone help me to indicate mistake in solution c:132264422  » 7 weeks ago, # | +34 Alex_Wei it's Unsuccessful hack for a reason :D Spoiler •  » » 7 weeks ago, # ^ | 0 Its 99.99% purposeful unsuccessful hacks to get last place. I've done it in the past when I felt I was getting too worried about my rating to the extent where the nervousness was ruining contests for me.Its trivial to copy paste the same input and change 1 value (can't use the same input twice on the same person) and make 20-30+ hacks / minute to quickly send yourself to last place.  » 7 weeks ago, # | 0 liked D very much ... though was'nt able to implement my logic in time , but felt really good after solving it! :D thnx authors for such good problems!  » 7 weeks ago, # | ← Rev. 2 → 0 132242048 C isn't a multitest problem but why I don't clear the array it makes my code FST ? After I clear the array I got accepted.132265702. Why ? When I change C++20 to C++17 in my FST code I have wrong in test 19 instead of 16. Why ?? :> •  » » 7 weeks ago, # ^ | +5 You are defining an array locally (inside of a function) rather than globally. The locally-defined array can contain anything at initialization. •  » » » 7 weeks ago, # ^ | 0 ya. It will be a big experience for me. Thanks •  » » 7 weeks ago, # ^ | +3 the array you defined is not global, if you didn't clear it then it just contain garbage :D Spoiler  » 7 weeks ago, # | 0 I am able to solve only 2 problems in most of the div 2 contests. can anyone give me suggestions to become a specialist •  » » 7 weeks ago, # ^ | +43 Try to solve 3 problems. •  » » » 7 weeks ago, # ^ | +3 Thanks. I will try. •  » » » » 7 weeks ago, # ^ | +4 Okay to be serious, here are some suggestions that may be helpful for you: Try to have a good format of code, this is helpful because it allows you to debug easier and code faster.(This means indentations and spaces) Try to think more before you code. Try to have an idea of what algorithm you will implement, and what are the details that may cause problems. Solve more problems in general. To be able to solve 3 problems, you need to be fluent in the language you code and be able to think logically to reach a solution. The third problem often needs some thinking, it isn't as direct, so it may need more practice. If you are sure that your algorithm is correct, and you fail to debug, try writing it over. Hope this may be helpful for you. •  » » » » » 7 weeks ago, # ^ | 0 Does it mean that the first two problems require no thinking at all? :) •  » » » » » » 7 weeks ago, # ^ | +1 Jokes aside, seeing how many people here (even high rating ones) completely blacked out on B, nope.Sometimes those "easy" problems actually requires you to figure out a specific trick, you get the problem if you do and you don't get it if you don't. Which is exactly what B is. •  » » » » » 7 weeks ago, # ^ | +3 okay.thank you so much  » 7 weeks ago, # | ← Rev. 2 → +7 The contest is nice ,problem D,E,F are interesting . It is sad that I can solve G if 5 more minutes are given :( •  » » 7 weeks ago, # ^ | ← Rev. 2 → 0 It is sad that I can solve D if 5 more minutes are given :D also 9 problems deserve way more than 2:15  » 7 weeks ago, # | ← Rev. 3 → +6 issue solved  » 7 weeks ago, # | +58 To not keep you waiting, the ratings are updated preliminarily. In a few hours/days, I will remove cheaters and update the ratings again!==Рейтинги предварительно обновлены. Через некоторое время я удалю читеров и пересчитаю рейтинг снова!  » 7 weeks ago, # | -23 This contest, I got rank 1328th (my previous rating is 1531) and my friend got rank 1446th (his pre rating is 1650) but my rating increased 75 and his rating increased 95. Can someone explain me this??? Many thanks •  » » 7 weeks ago, # ^ | +5 The rating calculation for new accounts is different. Maybe this is the reason.  » 7 weeks ago, # | +11 I'm curious about the special judge for problem B.How to check an output is valid or not quickly(I can only thought about a data structure which is O(n log^2 n))? •  » » 7 weeks ago, # ^ | 0 if b is on path between a and c, than dist(a,b)+dist(b,c)=dist(a,c) •  » » » 7 weeks ago, # ^ | 0 And? •  » » » » 7 weeks ago, # ^ | 0 this help's to check if the tree is valid •  » » » » » 7 weeks ago, # ^ | ← Rev. 3 → 0 Finding distance is not any faster than simply checking nodes on the way to the LCA.How is it relevant to the comment you replied to? •  » » » » » » 7 weeks ago, # ^ | ← Rev. 2 → 0 If there are$m$restrictions, we can check the validity of output in$O((n+m)logn)$. this is faster than$O(nlog^2n)$•  » » » » » » » 7 weeks ago, # ^ | 0 Can you elaborate? •  » » » » » » » » 7 weeks ago, # ^ | ← Rev. 2 → +6 first, we precalculate LCA(binary lifting) for each node & dist from root to each node. this takes$O(nlogn)$time&memory. next, for each of$m$restrictions like$a \space b \space c$we check if$dist(a,b) + dist(b,c) = dist(a,c)$. we do this in$O(logn)$time by finding the LCA for each pair of nodes. if so, the output is invalid. •  » » 7 weeks ago, # ^ | ← Rev. 3 → 0 Shouldn't it depend on$m\$ too?
 » 7 weeks ago, # |   0 I suspect that I read the C question incorrectly. Yesterday I wrote this question in a very complicated way, which always showed errors. Today I understood the ac code, but I entered what I was confused about yesterday, and something went wrong. https://codeforces.ml/contest/1586/submission/132311045 This is the code of my wa yesterday. https://codeforces.ml/contest/1586/submission/132313973 This is ac code. But I can't understand the ac code. 3 3 XXX XXX XXX one 1 3 NO4 5 ..XXX ...X. ...X. ...X. one 4 4 YES I hope someone can help me.
 » 7 weeks ago, # |   -7 Awesome contest!
 » 7 weeks ago, # | ← Rev. 2 →   0 Sorry, i was going to write that on commentary of 748 div.3, but i chose the wrong contest.
 » 7 weeks ago, # |   0 Hello please help me out. Just now I received a mail that my solution of problem 1586B of Codeforces Round #749 (Div. 1 + Div. 2, based on Technocup 2022 Elimination Round 1) conicides with user 1928311. First of all there is no chance of my solution getting leaked to any one because i didnt shared it. Secondly, kindly see the submission time of his solution , I submitted that at 17:21 and he submitted at 17:45. How could I cheat then. Please help me regarding this.
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   0 How could I cheat then you shared your solution. i didnt shared it any proof? it can't be coincidence, the solutions are very similar.
•  » » » 7 weeks ago, # ^ |   0 Arey how could one prove that he/she didn't shared his solution. Its not possible na. Atleast I proved that I didn't cheat. Please help me. Else it will simply demotivate me from CP
•  » » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 have you used an online editor like ideone?also for proving that you didn't cheat you need to prove that you didn't share any code, and that is almost impossible
•  » » » » » 7 weeks ago, # ^ |   0 No I used vscode. Wow got -113 without any fault :).I am impressed by your team and judgements for simply disqualifying a participant for not cheating :) Very good.
•  » » » » » » 7 weeks ago, # ^ |   0 i am just a cf user not an admin or something else.
•  » » » » » » » 7 weeks ago, # ^ |   0 So whom should I ask for this problem??
•  » » » » » » » » 7 weeks ago, # ^ |   +2 no one. Спойлерi know that you cheated.this definitely can't be just coincidence.even a function that wasn't needed was copy pasted.
•  » » » » » » » » » 7 weeks ago, # ^ |   0 You must be saying about the template.That is the xor function. I have a discord a server where I have shared my template with others. Many people use that
•  » » » » » » » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 only one small part of the template,also not only the template the rest of the code is also the same.you obviously cheated.
•  » » » » » 7 weeks ago, # ^ |   0 also for proving that you didn't cheat you need to prove that you didn't share any code, and that is almost impossible. Thats what i am saying na, you just say what kind of proof u need from me that i didn't shared the code. I am giving you.
•  » » » » » » 7 weeks ago, # ^ | ← Rev. 2 →   +1 There will be a person in charge in each round. You can go to 749 (div1+div2) comments to find out. One person said that he would launch a new ranking again within a few hours or days after the game. I think this person should be responsible for the ranking of the game.
•  » » » » » » 7 weeks ago, # ^ |   0 Hope it can help you
•  » » » » » » 7 weeks ago, # ^ |   0 just another indian cheater getting caught and still doesn't feel any guilt of itIt's amazing that he's still not ashamed of himself even with his EXACTLY same code.
•  » » » » » » » 7 weeks ago, # ^ |   -8 Yes that's because I didn't cheat. I was just explaining my solution to some of my friends in my hostel and one of them simply took the snap of it and wrote it as it is
•  » » » » » » » » 7 weeks ago, # ^ |   0 that's called CHEATINGFirst of all there is no chance of my solution getting leaked to any one because i didnt shared itand you lied :) Anything else you want to say
•  » » » » » » » » » 7 weeks ago, # ^ |   -8 That's simply because I solved the qs myself n I didn't wanna loose my ratings. Nyways I am guilty for what I did and paid it with my ratings down
•  » » » » » » » 7 weeks ago, # ^ |   -8 U better see the submission time and then decide who cheated
•  » » » » » » » » 7 weeks ago, # ^ |   0 sharing your code is also called cheatingare you dumb or something?you and your indian friends are all cheaters and you even lied that you didn't shared.you all deserves it ^-^
•  » » » » » » » » » 7 weeks ago, # ^ |   0 it is funny how cheaters lie and think we are stupid enough to believe them.
•  » » » » » » » » » 7 weeks ago, # ^ |   0 yea tru
 » 7 weeks ago, # | ← Rev. 2 →   0 Don't solve this contest. Let's play witcher