Codeforces Round #878 (Div.3) Editorial

#	User	Rating
1	ecnerwala	3649
2	Benq	3581
3	orzdevinwang	3570
4	Geothermal	3569
4	cnnfls_csy	3569
6	tourist	3565
7	maroonrk	3531
8	Radewoosh	3521
9	Um_nik	3482
10	jiangly	3468

#	User	Contrib.
1	maomao90	174
2	awoo	164
3	adamant	162
4	TheScrasse	159
5	nor	158
6	maroonrk	156
7	-is-this-fft-	151
8	SecondThread	147
9	orz	146
10	pajenegod	145

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

int n, k, cmf; cin >> n >> k >> cmf; vector<int> arr(n); for(int i = 0; i < n; i++) cin >> arr[i]; vector<int> suffix(n, 0); for(int i = n - 1; i >= 0; i--) { if(i == n - 1) suffix[i] = (arr[i] <= cmf) ? 1 : 0; else suffix[i] = (arr[i] <= cmf) ? 1 + suffix[i + 1] : 0; } ll ans = 0; for(int i = 0; i <= n - k; i++) { int ind = i + k; int r1 = (ind >= n) ? 0 : suffix[ind]; int r2 = suffix[i]; int d = r2 - r1; if(d != k) continue; ans += (r1 + 1); } cout << ans << endl;

Comments (126)

Write comment?

Gazyeyes

11 months ago, # |

+11

Nice contest!!

→ Reply

kovir_aleksey_korroy

Where are constructivs?

Noobish_Monk

11 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

10 months ago, # ^ |

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.

ashraw321

I know the formal proof if you want to know go on and read Lets considered a trajectory of going forward and downward ,if the character goes through this trajectory at time t position x and y if character goes toward right in next move would not be stuck by weapon horizontally at that horizontal coordinate at all because then it would not be the solution. So if character goes from left right for some time without changing direction it would only encountered vertical firing and all other remaining horizontal firing would be missed. Following this claim considered at time 0 character moves forward from left to right now at this particular time total of k vertical firing happens now if this firing are not spaced and happens from vertical coordinate of 2 to k+1 then he cannot move forward for maximum of at least k interval and in this case that is maximum amount of wait he need to make considering above argument that he does not change direction in our optimal solution. In other cases he might get trapped by not waiting but the best option to move is when all these k firings has happened. So he waits at least k seconds. So this problem has been reduced to walking in straight line from left to right while firing happening in vertical direction. So lets says firing again happens after time interval t so character can move a maximum of t interval to constraint it in its previous position we need at least t firing spaced adjacent to each other because that is the maximum distance the character can travel when firing was not happening. so we keeping on arguing we can formally prove this thing

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

ok thx

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!

Impostor_Syndrome

You can have a look at my submission. It's easier to understand.

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

8 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

Thank you.

suparmaan

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

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

preeetiiii

Could someone explain D please

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

pratyushranjan

9 months ago, # ^ |

Did you find it?

Inori

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

ZXG_DZXX

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

AvikAB

One of the great contest!

Frosty_Jonson

Perfect Contest and Nice editorial!

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.

azizbeksheripboev07

Why k = min(k, 30); in B?

10^9 is <= 2^30

thanks

shivamsharrma

Can the problem D be solved using DP with partition concept?

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

Bhavesh_gurnani

But can you prove that this technique will work and is correct approach. Because your technique seems to use greedy in a good way but i learnt that we must prove that greedy is correct. Although I didn't understand given solution for D can you help

Code. At every step I am checking the time of next step of corner parts.

shahad_jeza

can someone explain to me why we added this line to B solution ? ( k = min(k, 30); )

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://mirror.codeforces.com/edu/courses

sakib61

Really, Really, Really Nice problems

Kidus

Problem D editorial: What does it mean to give the maximum prefix of toys? I'm a bit confused

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

yeah ,it works now. Thanks a lot for the help !

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.

Understood, thanks!

Jack_sparrow_06

I hope the code below helps.

0.1_Zishan

2 months ago, # ^ |

What will be the solution if k would at most?

CODE:

I used suffix array, it will be easy.

Lukauru

I gotta say the B problem gave me a stroke

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.

sumj25

[user:variety-jones]Can You help me where i'm doing wrong? Here is my submission i'dYour text to link here...

explanation- Everything is i do same as editorial but instead of queue I'm using map. To store position and time. Also tagging variety-jones If he can provide some test cases where I'm failing.

variety-jones

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

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://mirror.codeforces.com/contest/1840/submission/208754257

TKTO

The 2 strings should have equal length

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)

soumyadeepsarkar

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

TRAGIC11

Can someone explain why my BFS solution to Problem F-Railguns gives TLE. Here is the code 208900576. Thanks in advance.

Mayank_Bhakat

Can anyone figure out my mistake for E https://mirror.codeforces.com/contest/1840/submission/209068675

ajitkumar014

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

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

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

contact.thevarunsappa

10 months ago, # |

Attention!

Your solution 208750724 for the problem 1840C significantly coincides with solutions Cuber2113/208747849, contact.thevarunsappa/208750724, Parthivsinh_Vaghela/208761407, bruher/208771556, Sarvagna_30405/208785324, anujkumarsingh5669/208788416. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://mirror.codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

Yes this is the a coincidence has occurred due to the use of a common source published before the competition.I am providing the link for that source:https://leetcode.com/discuss/interview-question/1238078/number-of-weeks-for-which-heshe-can-work-on-projects I have followed the implementation given in the comments and I don't know anyone of the above people.The coincidence was maybe caused by a trivial approach to the problem

nishu2002

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

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

rushikeshgulve10

210626795 can anyone find a mistake in this

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

mage111

enerneo

can someone help me find out where am i missing out in my submission?

Phantom_601

can someone please help what is wrong in this code for problem c https://mirror.codeforces.com/contest/1840/submission/211770436

the_knight1

Can someone please explain the editorial of 1840B - Binary Cafe that why did we do min(2 pow k, n+1)????

__Timu__

9 months ago, # |

How to know if a problem can be solved by using Binary search.any short trick?

IvanovAl

5 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_

4 months ago, # |

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

Spoiler

cotx

7 weeks ago, # ^ |

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

diskoteka's blog