Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### diskoteka's blog

By diskoteka, 14 months ago, translation,

1840A - Cipher Shifer

Idea: isosto, preparation: isosto

Tutorial
Solution
Rate the problem

1840B - Binary Cafe

Idea: diskoteka, preparation: diskoteka

Tutorial
Solution
Rate the problem

1840C - Ski Resort

Idea: pavlekn, preparation: playerr17

Tutorial
Solution
Rate the problem

1840D - Wooden Toy Festival

Idea: diskoteka, preparation: diskoteka

Tutorial
Solution
Rate the problem

1840E - Character Blocking

Idea: diskoteka, preparation: diskoteka

Tutorial
Solution
Rate the problem

1840F - Railguns

Idea: diskoteka, preparation: diskoteka

Tutorial
Solution
Rate the problem

1840G1 - In Search of Truth (Easy Version)

Idea: pavlekn, preparation: pavlekn

Tutorial
Solution
Rate the problem

1840G2 - In Search of Truth (Hard Version)

Idea: pavlekn, preparation: pavlekn

Tutorial
Solution
Rate the problem
• +50

| Write comment?
 » 14 months ago, # |   +11 Nice contest!!
 » 14 months ago, # |   0 Where are constructivs?
•  » » 14 months ago, # ^ |   +18 On ROI 2023...
 » 14 months ago, # |   +7 Problem F is a great problem, thank you
 » 14 months ago, # |   0 Is this a rated contest? My name is there in the rankings if the "show unofficial" box is checked, but I'm not there otherwise? I'm not sure why I'm not being included in them. Anyone know why?
•  » » 14 months ago, # ^ |   0 Hacking phase is going on. Then, there will be a system test. Then, the final result will be published. It will be done by tomorrow I guess.
•  » » » 14 months ago, # ^ |   0 oh ok, I'm still not sure why I'm not a trusted and official participant though
•  » » » » 14 months ago, # ^ |   +3 Did you read the round announcement?To qualify as a trusted participant of the third division, you must: take part in at least five rated rounds (and solve at least one problem in each of them) not have a point of 1900 or higher in the rating. You have only competed in two rated rounds before this. Thus, you are not shown on the official leaderboard. Your rating will be updated regardless of this (but it might take some time).
 » 14 months ago, # | ← Rev. 2 →   +110 I hacked the editorial solution for F. 208834351
 » 14 months ago, # | ← Rev. 2 →   0 There is another solution for G1. Let's make + k queries with random k from 1 to 1e6 until one of the indexes repeats. Also, let's save for each index sum of all k for all queries done before it firstly appears (sum[next] = sum[current] + k). Thus, when an index repeats we can calculate length of the cycle (let it be L). As index repeats after L + 1 queries, n is a divisor of L. Let's iterate over all d that divide L for O(sqrt(L)) and check if index repeats after d + 1 queries. Minimal of the suitable d is the answer. Average amount of queries required to find a cycle is around 1250, the maximal number of divisors of L is around 1000, as L <= 1250 * 1e6, so no more than 2250 queries total. But on practice it is around 1700.Code: 208832871Upd1: Tested my solution on tests with random n and indexes 1, 2, 3 ... n. Average result is 1200 queries, but the dispersion is really high. The numbers were from 650 to 3000. Guess G1 tests are not that good.
•  » » 13 months ago, # ^ |   0 That's... kinda strange. According to the birthday paradox, the chance of an index repeating within 2023 queries, with n = 1e6, is 87%, and there are more than 30 test that is like this, which means that you should have received "Wrong Answer". Guess you have dream luck then.
 » 14 months ago, # | ← Rev. 3 →   +54 I'm not sure I follow the claim made in the editorial for F that if we can reach $(n, m)$ by traveling along some path, we can in fact do so while standing still at most $r$ times. For example, suppose $n = m = 3$ and our initial trajectory is to move from $(0, 0)$ to $(3, 0)$ to $(3, 3)$. Then suppose that at time $6$, the line $x = 3$ is targeted. If we don't stand still at all, we'll be at $(3, 3)$ at time $6$, while if we stand still once, we'll be at $(3, 2)$ at time $6$. In either case, we are at an inaccessible position, so if we want to follow the same trajectory we would need to stand still more than three times. Of course, we can choose another trajectory to follow that will require us to stand still only once, but I'm confused specifically about the stronger claim made by the editorial since I didn't immediately see how to prove that there exists any path with which we stand still at most $O(r)$ times. This weaker claim seemed intuitive enough to me to submit under the assumption that it's true, but looking back it seems a bit tricky to prove formally.By the way, does anyone know why the hacks on F were reversed? Was there an error in the generator that allowed invalid tests to be submitted?
•  » » 14 months ago, # ^ |   +60 Looking at the problem, it appears that the time limit has been changed to three seconds, which may be the reason the hacks were reversed. Will the round remain rated? This doesn't seem like too drastic a change, but it could reasonably have affected anyone who was hesitant to submit an $O(nm(n+m+r))$ solution due to the 1s time limit, and generally changing limits after the contest seems like a concerning precedent to set (e.g. in future rounds, should contestants submit solutions they think may get TLE due to a high constant factor and then complain after the contest hoping to have the TL raised?).Incidentally, I'm not a big fan of the bounds of the problem: if your intent was to allow $O(nm(n+m+r))$ to pass, then the 1s time limit in contest was a bit tight and allowed for some annoying constant factor/ML issues that presumably caused all of these hacks, while if your intent was to require $O(nmr)$, it seems more reasonable to set e.g. $n \cdot m \le 10^5$ and $r \le 50.$
•  » » » 14 months ago, # ^ |   +2 I guess the TL was increased because someone managed to make the author's solution TLE on the old TL.
•  » » » » 14 months ago, # ^ |   +4 This should not be a reason to extend time limits right? As long as someone was able to pass the time constraints smoothly, it is still solvable in 1s and should be considered a valid problem imo
•  » » » » » 14 months ago, # ^ |   0 Yes, I agree with you on this.
•  » » » » » 13 months ago, # ^ |   0 An Editorial-based solution passes the tests in 300 smth ms for me, the trick is to use bitwise operators in c++ when calculating the dp and then it works much faster
•  » » » 14 months ago, # ^ | ← Rev. 2 →   +22 I believe that the authors should explain why the time limits are changed. I am guessing it is due to the test consisting of $10^6$ integers upto $10^9$, and as a side effect $O(nm(n+m+r))$ gets basically a free pass. I don't believe $O(nm(n+m+r))$ solutions are concerning enough to justify a drastic time limit change.It is possible to squeeze $O(nm(n+m+r))$ solutions without too much efforts in the original constraints 208838975 (this is in Kotlin so it should be easy in C++) This is of course assuming "10000 1" is within the tests, and this cannot be done without taking a few TLE penalties. Even if all that fails, a simple modification to use bitsets suffices. (UPD: I missed a simple optimisation of not needing to make two dp arrays and copy as found in your solution. With that, the $O(nm(n+m+r))$ should pass very comfortably.)Though considering how the test "10000 1" is completely missing from the tests, I feel like the authors did not consider the $O(nm(n+m+r))$ solution properly, let alone designing the TL accordingly.During the contest, I thought a $nm(n+m+r)$ solution would be able to pass easily. I did not notice that in fact, it is $(n+1)(m+1)(n+m+r)$ and I would probably hesitate if I noticed that.
•  » » 14 months ago, # ^ |   0 For the weaker claim, did you figure out how to prove formally? I am not sure how to.
•  » » » 14 months ago, # ^ |   0 No; I've spent some time thinking about it and still don't have a proof (though perhaps I'm missing something obvious). I'm hoping the authors post a corrected proof (or clarify the existing proof) before too long since this claim is obviously pretty central to solving the problem.
 » 14 months ago, # |   +31
 » 14 months ago, # |   +24 What are the specific hacking rules for Codeforces? Percisely, should a solution be hacked for the seed of its random number generator? As far as I remember there are many solutions hacked this way, so why did you rejudge all submissions in G1 and G2?
 » 14 months ago, # | ← Rev. 2 →   0 So basically from problem B I understand the follwing. Suppose we have a number n, and let be 2^x the largest power of 2 which does not exceed x, so it's enough to have x bits to represent n. In this case, the total number of ways to set bits on such that n is not exceeded is n + 1. Is it correct?
•  » » 14 months ago, # ^ |   0 Each number can be written as a bitmask. If we can "buy" a bitmask, that means its total cost is $\le n$. As every price is $2^k$, this total cost is just a number and can be achieved in only one way, so yes, you are correct
 » 14 months ago, # |   0 Could anyone please explain the solution of Problem B, I had hard time in understanding the solution of the editorial. Thanks in advance!
•  » » 14 months ago, # ^ |   0 Tasting stuff here is like counting in binary where you can count using k-bits. we can simply count how many k-bit combinations are less than n (including all 0s).
 » 14 months ago, # |   -48 ugly G :(
 » 14 months ago, # | ← Rev. 2 →   +10 I have another similar approach for problem F. Step 1: Multisource BFS can be done up to a depth of $d$ for every R. $d = time[R] - currentTime + 1$ Step 2: Then make the entire row/col visited as 0 for each query R. $visited[i][j] = 0, (i/j = fixed, j/i = varies)$ $currentTime = time[R] + 1$ Repeat Step 1 and Step 2 until $(N,M)$ cell is reached. $visited[N][M] = 1$Time Complexity: $O(NMR)$Space Complexity: $O(NM)$ (better than editorial solution)Implementaion is easier and more intuitive idea than dp. Code: 208794165
 » 14 months ago, # | ← Rev. 2 →   0 1729E - Guess the Cycle Size another interactive Div3 task which uses probabilities. similar to 1840G1 - In Search of Truth (Easy Version)
 » 14 months ago, # |   +1 C, D, E were nice! Only if B was not so complicated, took me around 20 mins to understand+solve ;(
•  » » 11 months ago, # ^ |   0 Can you tell me what is the error in my solution for E.
•  » » » 11 months ago, # ^ |   +1 Can you give the submission link, if I'm not able to find out the error then maybe someone else can!
•  » » » » 11 months ago, # ^ |   0
 » 14 months ago, # |   +1 B took the most time from me I didn't get it fast :(
•  » » 14 months ago, # ^ |   0 if u got it now can u explain me please, i am not able to get the editorial also
•  » » » 14 months ago, # ^ |   0 You just check what is the maximum number you can buy if 2 pow k <= n you can buy n+1 elements from 0 to n else the maximum you can buy is all elements from k the number of ways is 2 pow k you can represent it in binary representation each element is 0 or 1
•  » » » » 14 months ago, # ^ |   0 Hi Ahmed, please can you explain why they used k = min(k, 30) ? what is the meaning of using 30 ?
•  » » » » » 14 months ago, # ^ |   0 constrains are upto 1e9 and 1e9 has 30 bits in binary
•  » » » » » 13 months ago, # ^ |   0 to avoid integer overflow
 » 14 months ago, # |   0 For some reason, C is failing even though I implement the same logic. Can you please help me out?https://mirror.codeforces.com/contest/1840/submission/208848852
•  » » 14 months ago, # ^ |   0 You should just use long long instead of integers in the vectors
 » 14 months ago, # |   0 Anyone who solved F with recursive approach?
 » 14 months ago, # |   0 For pD, what does maximum prefix and suffix mean? How do you prove this to be the best?I thought of using maybe a two-pointer approach to find which elements the carvers should handle, but that didn't end well.
•  » » 14 months ago, # ^ |   0 Ah, never mind. I understand it now. Surprised that I didn't think of binary search = =
•  » » 13 months ago, # ^ |   +1 I used a two-pointers approach without binary search, one for the right end of the prefix and one for the left end of the suffix. However, I was missing that I need to check only for the minimum between the updated prefix and suffix not the maximum between the 3 segments in each case (L+1 and R-1).Wrong Submission: https://mirror.codeforces.com/contest/1840/submission/209091927
•  » » » 13 months ago, # ^ |   0 Yeah I had pretty much the same idea and wrong observation like you. This pair with slow implementation really messed me up.
 » 14 months ago, # |   0 I hope I will reach an expert by the end of the final testing...
•  » » 14 months ago, # ^ |   +1 same
•  » » » 14 months ago, # ^ |   0 My congratulations !!!
 » 14 months ago, # |   +1 The fourth question could've been framed in a better way I think. I though about it for 3-4 hours but couldn't think of a solution. The reason being that I thought that the time of different carvings by the same Carver have to be added. But we had to only take the maximum as each Carver can carve multiple toys at once. But this isn't clearly mentioned in the question. It's written that the carvers are skilled and can work at multiple people at once. It should've been written that one Carver can work at multiple carvings at once.
•  » » 14 months ago, # ^ |   +1 Im tripped this at first too. But I think the statement is quite clear and example made it more clearDuring the preparation for the festival, the carvers will perfectly work out the technique of making the toy of the chosen pattern, which will allow them to cut it out of wood "instantly". To make a toy of pattern y for a carver who has chosen pattern x, it will take |x-y| time, because the more the toy resembles the one he can make "instantly", the faster the carver will cope with the work.Still imho many problem statements in contests use some hard and implied words that really hard to understand quickly for me, especially my english is not that good (but yeah that makes me improve better and better tho just need time for practice).
 » 14 months ago, # |   +3 Can someone help spot mistake in my solution for E? I am getting wrong 52nd token in test 2 which I can't see, and I can't find bug after 3 hours. My approach was slightly different: I preprocessed the modifications and then after all of them I answered all the queries.__ https://mirror.codeforces.com/contest/1840/submission/208812489
•  » » 12 months ago, # ^ |   0 Did you find it?
•  » » » 11 months ago, # ^ |   0 no
 » 14 months ago, # |   0 https://mirror.codeforces.com/contest/1840/submission/208865868 could someone help me find why i am getting WA? I cant find it.. :(
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 in your function where you are performing swap operation for query of type 2, in the second else if you are comparing op1 with both 1 and 2. Here is an accepted submission of your edited code https://mirror.codeforces.com/contest/1840/submission/208869321
 » 14 months ago, # |   0 In problem G2, the solution d=(1000-k)/2 should be sqrt(d)=(1000-k)/2
 » 14 months ago, # |   +2 B was too complicated for a Div3 contest.Sure the solution can be written in a single line but it was not obvious at all.
 » 14 months ago, # | ← Rev. 2 →   -8 UPD : Fixed
 » 14 months ago, # | ← Rev. 3 →   0 Simple approach to G2: firstly we have a number x, specify it's sector's index as 1. let there be a variable MXM to store maximum value obtained from queries, currently it's value is x get the consecutive 250 numbers to from x in clockwise order (can also be anticlockwise) by asking 250 queries. store their values as keys in a map along with their indices, assuming index of x as 1, simultaneously compare these values with MXM and update MXM generate 490 random numbers from up to 1000000 and query them, update MXM with these values, simultaneously keep updating index. we know that MXM is less than equal to n but closest value to n that we know. return to the index of x by asking a anticlockwise query. query MXM clockwise. if we encounter an already known value, compute the answer. Otherwise we're closest to n. now keep asking queries with a step size of 250 hoping to land anywhere in first 250 indices, after that we can easily get the value of n
 » 14 months ago, # |   +6 I have different approach to solve Problem D[problem:1840D] using Two pointer. we have to divide the sorted array into three parts, and maximum time for all three parts can be calculated in O(1) time. Here is my approach: 1. sort the array. 2. divide the array into three parts: part1 = (0,i-1), part2 = (i,j), part3 = (j+1,n-1). 3. calculate the time of all three parts, and store the maximum of them. 4. compare the time of 1(0,i) and 2(j,n-1) if 1>2 go to left (j--) else go to right (i++). — i is the left pointer and j is the right pointer and i starts from 1 and j starts from n-2. 5. print the minimum time. **maximum time for any part from i to j is (a[j] - a[i] + 1)/2 .**
•  » » 2 months ago, # ^ |   0 very nice approach, but not so intutive btw
 » 14 months ago, # |   0 In F's editorial Code what does this line means? if (0 <= t - coord - j && t - coord - j <= r) free[coord][j][t - coord - j] = false; 
•  » » 14 months ago, # ^ |   0 To get to the position (i, j) with k stops, it will take i + j + k seconds (since going vertically or horizontally by one unit takes 1 unit of time, and stopping takes one unit of time). The code snippet you gave is enforcing the principle that when a laser is fired horizontally, positions (coord, j) for j in [0, m] are not free at time t. So t = coord + j + k, ergo k = t - coord - j which is the expression in the third pair of brackets. Lastly we need to check that k is in the interval [0, r] so that it is not out of bounds.
 » 14 months ago, # |   0 Problem D really teaches a lot. Im new to this binary search on the answer. To somebody more experienced, could you please provide some problem which uses the same key concept?
•  » » 14 months ago, # ^ | ← Rev. 6 →   0
 » 14 months ago, # |   0 Really, Really, Really Nice problems
 » 14 months ago, # |   0 Could someone point out the problem in my submission for C ? I am getting wrong answer on test case 6.208749011
•  » » 14 months ago, # ^ | ← Rev. 2 →   +3 I believe it is integer overflow. See this code snippet: int main() { ll x = 0; int y = 1e6; x += y * y; cout << x << "\n"; return 0; } This would output -727379968, since the intermediate result y * y is an integer and exceeds the integer limit. Now see this code snippet: int main() { ll x = 0; int y = 1e6; x += 1LL * y * y; cout << x << "\n"; return 0; } This correctly outputs 1000000000000, since it creates an intermediate result 1LL * y of type long long so 1LL * y * y ends up being a long long too, rather than an integer.Hopefully this is enough to help fix your code now :)
 » 14 months ago, # |   0 In problem C, how did you get to C(l-k+2, l-k)?
•  » » 14 months ago, # ^ | ← Rev. 3 →   +3 The way I thought about it, is that if you have a section of length l and you want find the number of ways of choosing a subsection of length k<=x<=l, we can count up the ways of choosing subsections of all lengths x in [k, l] and add them up. We can fully describe choosing a subsection of length x by where it begins. So we just need to add up the number of starting positions for the subsections. There are l-x+1 different places that you can choose for the starting point (hopefully it shouldn't be too hard to convince yourself with some examples). So we end up adding (l-k+1) + (l-k) + (l-k-1) + ... + 1 which you should recognise as triangular numbers starting from (l-k+1) i.e. (l-k+1)(l-k+2)/2 which is the same as (l-k+2) choose 2 or (l-k+2) choose (l-k). Maybe there's an easier way to understand it with combinatorics that somebody else can let us know, but this was my approach.
•  » » » 5 months ago, # ^ |   0 What will be the solution if k would at most?
 » 14 months ago, # |   0 Can anyone help me if in problem D we call the number of carvers is k, and how to solve this problem if 1 <= k <= 200005, if it impossible to solve, what about 1 <= k <= 20
•  » » 13 months ago, # ^ |   0 You can binary search on the answer. Here's the implementation: 208734553
 » 14 months ago, # |   +3 Can someone help me to take a look at my Code for Problem E? I have been reviewing it for more than 1 hour and asked people around me, but I couldn't identify the issue.208958346
•  » » 14 months ago, # ^ |   +8 Both strings in type2 query can be same even if pos1==pos2. if(p1==p2) { swap(a[p1],b[p2]); } So just remove this if statement.208961664
•  » » » 13 months ago, # ^ |   +3 I am extremely grateful, you saved my life.
 » 13 months ago, # | ← Rev. 3 →   +3 How would you solve E if the block operation were defined like this:$1\ \ \ pos_1\ \ \ pos_2$Constraints: $0 \le pos_1 \le |s_1|$ $0 \le pos_2 \le |s_2|$ $pos_i = 0$ meaning that there's no character to be blocked in $s_i$ on this operation. Both strings may have different lengths. Operation $3$ is guaranteed to be queried only when $|s_1| = |s_2|$ (ignoring blocked characters) Examples:Input: 3 abcd abc 5 2 1 4 0 3 abc adbc 5 2 1 0 2 3 dabc abcd 5 2 1 1 4 3 Output: YES YES YES Explanation:First case: $(abcd, abc) \rightarrow (abc\color{red}{d}, abc)$ Second case: $(abc, adbc) \rightarrow (abc, a\color{red}{d}bc)$ Third case: $(dabc, abcd) \rightarrow (\color{red}{d}abc, abc\color{red}{d})$
•  » » 13 months ago, # ^ | ← Rev. 2 →   0 Actually,it can be solved easily with segment tree and hashing.Check this submission for more details : https://mirror.codeforces.com/contest/1840/submission/208754257
•  » » 11 months ago, # ^ |   0 The 2 strings should have equal length
•  » » » 11 months ago, # ^ |   0 Ok sry for the comment. I haven't understood your comment and I just realized what you meant (Plz do ignore my comments) (ps. how can i delete my comments)
 » 13 months ago, # | ← Rev. 2 →   0 Can anyone tell me problem D. How can one verify that the mid calculated satisfies the problem or not(Basically how can you create a check function for binary search). So that we can shift low and high variables. Thank you!
•  » » 11 months ago, # ^ |   0 You can use two pointers. I bs the maximum waiting time for each worker. if mid = 4, then for the following array: [1, 2, 3, 4, 5, 6, 7, 8] you can cover the entire array by only using 1 worker. So, you will start from head of array, and scan the other pointer to the right until you reach a point where a[j]-a[0]>2*mid. Because if a[j]-a[i]<=2*mid, you can always set x for this worker as (a[j]+a[i])/2 (in the middle). After you found the maximum orders the first worker can take, you move onto the next orders the second worker can take. At the end of loop, you should have <=3 worker used. Just in case my explanation isn't clear enough, here is my submission: 219646983
 » 13 months ago, # |   0 can anyone explain in problem C the number ways to choose a trip at least k ?
•  » » 11 months ago, # ^ |   0 For a subarray s from original array, with length m (m>=k). The first element of the subarray of s should only be at locations 1~m-k+1. When you fix the first element of the subarray of s at location m-k+1, only 1 subarray of length at least k can be created. When it is at m-k, 2 subarrays of length at least k can be created... This is an arithmetic sequence. So you can calculate the sum by: (m-k+1)*((m-k+1)+1)/2
 » 13 months ago, # |   0 Hi, can anyone spot the error in my submission for 1840E - Character Blocking -> 209220374I tried to generate tests (although most of them had all NO's as output), but I couldn't find a case where my solution is failing :(
•  » » 13 months ago, # ^ |   0 Take a look at Ticket 16872 from CF Stress for a counter example.
•  » » » 13 months ago, # ^ |   0 Thanks a lot man, was able to correct the error, really appreciate it. Really good website you made :)
 » 13 months ago, # |   0 Can anybody tell me where am I going wrong in problem E? submission — here
 » 13 months ago, # |   0 Seems a contest 3 weeks ago has been a ancient contest and nobody will care about it, but I still want to share my optimized BFS solution to problem F!An instant thought is applying naive BFS running on $O(n\times m\times r)$ 3-dimensional space. It's no need to consider a railgun shot which is at a very late time.But my time constant was high, for my unwise implementation with much unnecessary STL. Feeling too lazy to change my code greatly, I decided to try something to reduce my constant. In details, two optimization: I used set> to record every point (x, y, time) to avoid repeating. But it was BFS, so when a (x, y, t + 1) occurred, all the records that time = t turned useless. So a set> could be reuse again and again, reducing the size of the set greatly. Of course you can apply this on the 3-d bool array to reduce you memory cost. A well-known trick to boost BFS is A-star, and I designed a method to cut down the number of points in queue that familiar with A-star. If we have a nearest point (x, y) to the destination, taking railgun into consideration, we need no more than $d=n + m - x - y + r$ steps. For any point whose $n+m-x-y$ exceed the $d$, we just drop it. In my (suck) implementation, both optimization are essential, or it gets TLE.You may think it unnecessary to share such trivial things. Well, I just want to share my enjoyment of solving problems. Have a nice day. :)
 » 13 months ago, # |   0 Nice contest
 » 7 months ago, # |   0 There is a typo in the analysis of the G2 problem — the expression d=(1000-k)/2 should be as follows sqrt(d)=(1000−k)/2.
 » 6 months ago, # |   0 What dose it mean k = min (k , 30) If you have the time, give an in-depth explanation. SpoilerI greatly appreciate your help.<3
•  » » 4 months ago, # ^ |   0 N can be maximum 1e9 thus you can't buy the 31th item which costs 2^30 = 1073741824.