Codeforces Round #878 (Div.3) Editorial

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	165
2	maomao90	164
3	Um_nik	163
4	atcoder_official	161
5	adamant	160
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

Idea: isosto, preparation: isosto

Tutorial

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;
    }
}

Rate the problem

1840B - Binary Cafe

Idea: diskoteka, preparation: diskoteka

Tutorial

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;
}

Rate the problem

1840C - Ski Resort

Idea: pavlekn, preparation: playerr17

Tutorial

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)

Rate the problem

1840D - Wooden Toy Festival

Idea: diskoteka, preparation: diskoteka

Tutorial

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;
}

Rate the problem

1840E - Character Blocking

Idea: diskoteka, preparation: diskoteka

Tutorial

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;
}

Rate the problem

1840F - Railguns

Idea: diskoteka, preparation: diskoteka

Tutorial

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;
}

Rate the problem

1840G1 - In Search of Truth (Easy Version)

Idea: pavlekn, preparation: pavlekn

Tutorial

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;
}

Rate the problem

1840G2 - In Search of Truth (Hard Version)

Idea: pavlekn, preparation: pavlekn

Tutorial

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;
}

Rate the problem

Comments (91)

Show archived | Write comment?

Gazyeyes

17 months ago, # |

+11

Nice contest!!

→ Reply

kovir_aleksey_korroy

Where are constructivs?

Noobish_Monk

17 months ago, # ^ |

+18

On ROI 2023...

Hard_2_FaceReality

Problem F is a great problem, thank you

amitjoshi24

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?

mahir1

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

vgtcross

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

DottedCalculator

← Rev. 2 →

+110

I hacked the editorial solution for F. 208834351

VolkovMA

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.

steveonalex

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.

Geothermal

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

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

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

dumb_boi

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.

Frogmaster

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

arvindf232

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

kelzzin2_fan

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.

TripleM5da

+31

Problem G

Kilo_5723

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

FlyingElephant

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

the_coder_8297

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

The5threich

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

i_love_fumeShroom

-48

ugly G :(

ASHWANTH_K

+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

Java_programmer__

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

jeal0uspengu1n

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

BitSlayer

15 months ago, # ^ |

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

Ahmed_Ashraf_f

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

mridul_meerut

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

mason_24

Hi Ahmed, please can you explain why they used k = min(k, 30) ? what is the meaning of using 30 ?

yadavDipesh

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

to avoid integer overflow

suparmaan

For some reason, C is failing even though I implement the same logic. Can you please help me out?

https://codeforces.net/contest/1840/submission/208848852

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

shashwat_nayak

Anyone who solved F with recursive approach?

AverageBasilEnjoyer

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

Vengxeance

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://codeforces.net/contest/1840/submission/209091927

Accepted: https://codeforces.net/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.

Oleja123

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

_Aryan_

same

My congratulations !!!

readycoderone

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.

yuuma

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

robakibobaki

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://codeforces.net/contest/1840/submission/208812489

pratyushranjan

Did you find it?

Inori

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

JollyVictini

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://codeforces.net/contest/1840/submission/208869321

ZXG_DZXX

In problem G2, the solution d=(1000-k)/2 should be sqrt(d)=(1000-k)/2

pocket_acer

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.

Abdelaleem

-8

UPD : Fixed

eklavya_k

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

Xor_again

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

Verma_26

6 months ago, # ^ |

very nice approach, but not so intutive btw

vaibhav_1710

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;

myst-6

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?

propanol

← Rev. 6 →

CF Edu. https://codeforces.net/edu/courses

sakib61

Really, Really, Really Nice problems

sumantp001

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:

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

ikrr

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.

0.1_Zishan

9 months ago, # ^ |

What will be the solution if k would at most?

kimpro

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

HHY_zZhu

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

Airths

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

I am extremely grateful, you saved my life.

AntennaeVY

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

Saule_

Actually,it can be solved easily with segment tree and hashing.

Check this submission for more details : https://codeforces.net/contest/1840/submission/208754257

MickeyIsAwesome

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

variety-jones

Take a look at Ticket 16872 from CF Stress for a counter example.

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

nishu2002

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

Lice-wx

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

z-force

Nice contest

IvanovAl

11 months ago, # |

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.

p.cyanide_

10 months ago, # |

What dose it mean k = min (k , 30) If you have the time, give an in-depth explanation.

Spoiler

cotx

8 months ago, # ^ |

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

Xiao_2710

4 months ago, # |

I have a more intuitive solution for D. We basically binary search for x, where x is minimum possible wait time. Suppose I need to check if task can be done in x time or not: Greedily its best to assign a=v[0]+x; then we find the first v[i] for which abs(v[i]-a)>x; now assign b=v[i]+x; and do the same for c; do this obviously after sorting the array.

shubhanshu_mishra

3 months ago, # |

In E, I am getting TLE. I am using hash functions to determine whether the current strings are equal. How can I optimize it to pass the time limit? Please, anyone!

This is my code : [submission:https://codeforces.net/contest/1840/submission/277553096]

AlexTheFirelord

6 weeks ago, # |

Notice that the edutorial's G1 solution is similar to "baby-step giant-step" algorithm for computing the discrete logarithm.

diskoteka's blog