Idea: isosto, preparation: isosto

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
int main() {
int t; cin >> t;
while (t--) {
int n; cin >> n;
string s; cin >> s;
int i = 0;
while (i < n) {
int start = i;
cout << s[i++];
while (s[i++] != s[start]);
}
cout << endl;
}
}
```

Idea: diskoteka, preparation: diskoteka

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
int32_t main() {
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
k = min(k, 30);
cout << min(n, (1 << k) - 1) + 1 << "\n";
}
return 0;
}
```

Idea: pavlekn, preparation: playerr17

**Tutorial**

Tutorial is loading...

**Solution**

```
testCases = int(input())
for testCase in range(testCases):
n, k, q = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
ans = 0
len = 0
for i in range(n):
if a[i] <= q:
len += 1
else:
if len >= k:
ans += (len - k + 1) * (len - k + 2) // 2
len = 0
if len >= k:
ans += (len - k + 1) * (len - k + 2) // 2
print(ans)
```

Idea: diskoteka, preparation: diskoteka

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
sort(a.begin(), a.end());
int l = -1, r = 1e9;
while (r - l > 1) {
int m = (l + r) >> 1;
int i = 0;
while (i + 1 < a.size() && a[i + 1] - a[0] <= 2 * m) {
++i;
}
int j = n - 1;
while (j - 1 >= 0 && a.back() - a[j - 1] <= 2 * m) {
--j;
}
++i; --j;
if (i > j || a[j] - a[i] <= 2 * m) {
r = m;
} else {
l = m;
}
}
cout << r << "\n";
}
return 0;
}
```

Idea: diskoteka, preparation: diskoteka

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
int main() {
int x;
cin >> x;
while (x--) {
vector<string> s(2);
cin >> s[0] >> s[1];
int n = s[0].size();
int bad = 0;
for (int i = 0; i < n; ++i) {
if (s[0][i] != s[1][i]) {
++bad;
}
}
int t, q;
cin >> t >> q;
queue<pair<int, int>> unblock;
for (int i = 0; i < q; ++i) {
while (!unblock.empty() && unblock.front().first == i) {
if (s[0][unblock.front().second] != s[1][unblock.front().second]) {
++bad;
}
unblock.pop();
}
int type;
cin >> type;
if (type == 1) {
int pos;
cin >> pos;
if (s[0][pos - 1] != s[1][pos - 1]) {
--bad;
}
unblock.emplace(i + t, pos - 1);
} else if (type == 2) {
int num1, pos1, num2, pos2;
cin >> num1 >> pos1 >> num2 >> pos2;
--num1; --pos1; --num2; --pos2;
if (s[num1][pos1] != s[1 ^ num1][pos1]) {
--bad;
}
if (s[num2][pos2] != s[1 ^ num2][pos2]) {
--bad;
}
swap(s[num1][pos1], s[num2][pos2]);
if (s[num1][pos1] != s[1 ^ num1][pos1]) {
++bad;
}
if (s[num2][pos2] != s[1 ^ num2][pos2]) {
++bad;
}
} else {
cout << (!bad ? "YES" : "NO") << "\n";
}
}
}
return 0;
}
```

Idea: diskoteka, preparation: diskoteka

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int q;
cin >> q;
while (q--) {
int n, m;
cin >> n >> m;
int r;
cin >> r;
bool free[n + 1][m + 1][r + 1];
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= m; ++j) {
for (int k = 0; k <= r; ++k) {
free[i][j][k] = true;
}
}
}
for (int i = 0; i < r; ++i) {
int t, d, coord;
cin >> t >> d >> coord;
if (d == 1) {
for (int j = 0; j <= m; ++j) {
if (0 <= t - coord - j && t - coord - j <= r) {
free[coord][j][t - coord - j] = false;
}
}
} else {
for (int j = 0; j <= n; ++j) {
if (0 <= t - coord - j && t - coord - j <= r) {
free[j][coord][t - coord - j] = false;
}
}
}
}
bool dp[n + 1][m + 1][r + 1];
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= m; ++j) {
for (int k = 0; k <= r; ++k) {
dp[i][j][k] = !(i || j || k);
if (free[i][j][k]) {
if (i && dp[i - 1][j][k]) {
dp[i][j][k] = true;
}
if (j && dp[i][j - 1][k]) {
dp[i][j][k] = true;
}
if (k && dp[i][j][k - 1]) {
dp[i][j][k] = true;
}
}
}
}
}
int ans = -1;
for (int t = r; t >= 0; --t) {
if (dp[n][m][t]) {
ans = n + m + t;
}
}
cout << ans << "\n";
}
return 0;
}
```

1840G1 - In Search of Truth (Easy Version)

Idea: pavlekn, preparation: pavlekn

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e6 + 7;
int pos[MAXN];
int32_t main() {
int num;
cin >> num;
int ans = 0;
int cur = 1;
pos[num] = 1;
for (int i = 0; i < 1000; ++i) {
cout << '+' << " " << 1 << endl;
++cur;
cin >> num;
if (pos[num]) {
cout << '!' << " " << cur - pos[num] << endl;
return 0;
}
pos[num] = cur;
}
while (true) {
cout << '+' << " " << 1000 << endl;
cur += 1000;
cin >> num;
if (pos[num]) {
cout << '!' << " " << cur - pos[num] << endl;
return 0;
}
pos[num] = cur;
}
return 0;
}
```

1840G2 - In Search of Truth (Hard Version)

Idea: pavlekn, preparation: pavlekn

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e6 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int pos[MAXN];
const int K = 400;
const int T = 300;
int get() {
return rng() % MAXN;
}
int32_t main() {
int num;
cin >> num;
int start = num;
int cur_delta = 0;
int N0 = num;
for (int i = 0; i < K; ++i) {
int delta = get();
cout << '+' << " " << delta << endl;
cur_delta += delta;
cin >> num;
N0 = max(N0, num);
}
cout << '-' << " " << cur_delta << endl;
cin >> num;
cout << '+' << " " << N0 - 1 << endl;
cur_delta = N0 - 1;
cin >> num;
pos[num] = N0;
for (int i = 0; i < T; ++i) {
++cur_delta;
cout << '+' << " " << 1 << endl;
cin >> num;
pos[num] = N0 + i + 1;
if (num == start) {
cout << '!' << " " << N0 + i << endl;
return 0;
}
}
cout << '-' << " " << cur_delta << endl;
cin >> num;
int ans = 0;
while (true) {
cout << '-' << " " << T << endl;
ans += T;
cin >> num;
if (pos[num]) {
cout << '!' << " " << ans + pos[num] - 1 << endl;
return 0;
}
}
return 0;
}
```

Nice contest!!

Where are constructivs?

On ROI 2023...

Problem F is a great problem, thank you

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?

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.

oh ok, I'm still not sure why I'm not a trusted and official participant though

Did you read the round announcement?

To qualify as a

trusted participant of the third division, you must:at least five rated rounds(and solve at least one problem in each of them)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).

I hacked the editorial solution for F. 208834351

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

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

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?

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

I guess the TL was increased because someone managed to make the author's solution TLE on the old TL.

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

Yes, I agree with you on this.

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

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.

For the weaker claim, did you figure out how to prove formally? I am not sure how to.

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.

Problem G

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?

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?

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

Could anyone please explain the solution of Problem B, I had hard time in understanding the solution of the editorial. Thanks in advance!

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

ugly G :(

I have another similar approach for problem F.

$$$d = time[R] - currentTime + 1$$$

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

1729E - Guess the Cycle Size another interactive Div3 task which uses probabilities. similar to 1840G1 - In Search of Truth (Easy Version)

C, D, E were nice! Only if B was not so complicated, took me around 20 mins to understand+solve ;(

Can you tell me what is the error in my solution for E.

Can you give the submission link, if I'm not able to find out the error then maybe someone else can!

219706876

B took the most time from me I didn't get it fast :(

if u got it now can u explain me please, i am not able to get the editorial also

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

Hi Ahmed, please can you explain why they used

`k = min(k, 30)`

? what is the meaning of using`30`

?constrains are upto 1e9 and 1e9 has 30 bits in binary

to avoid integer overflow

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

You should just use long long instead of integers in the vectors

Anyone who solved F with recursive approach?

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.

Ah, never mind. I understand it now. Surprised that I didn't think of binary search = =

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

Accepted: https://mirror.codeforces.com/contest/1840/submission/209090257

Yeah I had pretty much the same idea and wrong observation like you. This pair with slow implementation really messed me up.

I hope I will reach an expert by the end of the final testing...

same

My congratulations !!!

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.

Im tripped this at first too. But I think the statement is quite clear and example made it more clear

`During 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).

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

Did you find it?

no

https://mirror.codeforces.com/contest/1840/submission/208865868 could someone help me find why i am getting WA? I cant find it.. :(

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

In problem G2, the solution d=(1000-k)/2 should be sqrt(d)=(1000-k)/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.

UPD : Fixed

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.very nice approach, but not so intutive btw

In F's editorial Code what does this line means?

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

CF Edu. https://mirror.codeforces.com/edu/courses

Really, Really, Really Nice problems

Could someone point out the problem in my submission for C ? I am getting wrong answer on test case 6.

208749011

I believe it is integer overflow. See this code snippet:

This would output

`-727379968`

, since the intermediate result`y * y`

is an integer and exceeds the integer limit. Now see this code snippet: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 :)

In problem C, how did you get to C(l-k+2, l-k)?

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.What will be the solution if k would at most?

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

You can binary search on the answer. Here's the implementation: 208734553

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

Both strings in type2 query can be same even if pos1==pos2.

So just remove this if statement.208961664

I am extremely grateful, you saved my life.

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

`Output:`

`Explanation:`

First case:

Second case:

Third case:

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

The 2 strings should have

equal lengthOk 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)

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!

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

can anyone explain in problem C the number ways to choose a trip at least k ?

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

Hi, can anyone spot the error in my submission for 1840E - Character Blocking -> 209220374

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

Take a look at Ticket 16872 from

CF Stressfor a counter example.Thanks a lot man, was able to correct the error, really appreciate it. Really good website you made :)

Can anybody tell me where am I going wrong in problem E? submission — here

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<tuple<int, int, int>>`

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<pair<int, int>>`

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

Nice contest

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.

What dose it mean

k = min (k , 30)If you have the time, give an in-depth explanation.SpoilerI greatly appreciate your help.<3

N can be maximum 1e9 thus you can't buy the 31th item which costs 2^30 = 1073741824.