Codeforces Round #894 (Div.3) Editorial

#	User	Rating
1	tourist	3690
2	jiangly	3647
3	Benq	3581
4	orzdevinwang	3570
5	Geothermal	3569
5	cnnfls_csy	3569
7	Radewoosh	3509
8	ecnerwala	3486
9	jqdai0815	3474
10	gyh20	3447

#	User	Contrib.
1	maomao90	174
2	awoo	165
3	adamant	161
4	TheScrasse	160
5	nor	158
6	maroonrk	156
7	-is-this-fft-	152
8	orz	146
9	SecondThread	145
9	pajenegod	145

We would like to thank all the participants who helped us and Codeforces to overcome the 40.000 registered users for the first time

1862A - Gift Carpet

Idea: diskoteka

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
int32_t main() {
    int q;
    cin >> q;
    while (q--) {
        int n, m;
        cin >> n >> m;
        vector<string> carpet(n);
        for (int i = 0; i < n; ++i) {
            cin >> carpet[i];
        }
        string vika = "vika";
        int fnd = 0;
        for (int i = 0; i < m; ++i) {
            bool check = false;
            for (int j = 0; j < n; ++j) {
                if (carpet[j][i] == vika[fnd]) {
                    check = true;
                }
            }
            if (check) {
                ++fnd;
                if (fnd == 4) {
                    break;
                }
            }
        }
        if (fnd == 4) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
    return 0;
}

Rate the problem

1862B - Sequence Game

Idea: diskoteka

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
int32_t main() {
    int q;
    cin >> q;
    while (q--) {
        int n;
        cin >> n;
        vector<int> a;
        for (int i = 0; i < n; ++i) {
            int x;
            cin >> x;
            if (i && a.back() > x) {
                a.push_back(1);
            }
            a.push_back(x);
        }
        cout << a.size() << "\n";
        for (int el : a)
            cout << el << " ";
        cout << "\n";
    }
    return 0;
}

Rate the problem

1862C - Flower City Fence

Idea: playerr17

Tutorial

Solution

#include <iostream>
#include <vector>
 
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n + 1);
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        if (a[1] != n) {
            cout << "NO" << '\n';
            continue;
        }
        vector<int> b;
        for (int i = n; i >= 1; i--) {
            while (b.size() < a[i]) {
                b.push_back(i);
            }
        }
        bool meow = true;
        for (int i = 1; i <= n; i++) {
            if (a[i] != b[i - 1]) {
                cout << "NO" << '\n';
                meow = false;
                break;
            }
        }
        if (meow) {
            cout << "YES" << '\n';
        }
    }
    return 0;
}

Rate the problem

1862D - Ice Cream Balls

Idea: diskoteka, Ivang

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
int32_t main() {
    int q;
    cin >> q;
    while (q--) {
        int n;
        cin >> n;
        int l = 0, r = min<int>(2e9, 2 * n);
        while (r - l > 1) {
            int m = (l + r) >> 1;
            // m = x + y, answer = x + 2 * y
            if (m * (m - 1) / 2 + m < n) {
                l = m;
            } else {
                r = m;
            }
        }
        int y = n - r * (r - 1) / 2;
        if ((r + 1) * r / 2 <= n) {
            cout << min(r + y, r + 1 + n - (r + 1) * r / 2) << "\n";
        } else {
            cout << r + y << "\n";
        }
    }
    return 0;
}

Rate the problem

1862E - Kolya and Movie Theatre

Idea: pavlekn

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
int32_t main() {
    int t;
    cin >> t;
    for (int _ = 0; _ < t; ++_) {
        int n, m, d;
        cin >> n >> m >> d;
        vector<int> a(n);
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
        }
        int ans = 0;
        set<pair<int, int>> s;
        int sum = 0;
        for (int i = 0; i < n; ++i) {
            int cur = sum + a[i] - d * (i + 1);
            ans = max(ans, cur);
            if (a[i] > 0) {
                s.insert({a[i], i});
                sum += a[i];
                if (s.size() >= m) {
                    sum -= (s.begin()->first);
                    s.erase(s.begin());
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}

Rate the problem

1862F - Magic Will Save the World

Idea: diskoteka

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
int32_t main() {
    int q;
    cin >> q;
    while (q--) {
        int w, f, n;
        cin >> w >> f >> n;
        vector<int> s(n);
        int sum_s = 0;
        for (int i = 0; i < n; ++i) {
            cin >> s[i];
            sum_s += s[i];
        }
        vector<bool> dp(sum_s + 1);
        dp[0] = true;
        for (int i = 0; i < n; ++i) {
            for (int w = sum_s; w - s[i] >= 0; --w) {
                dp[w] = dp[w] || dp[w - s[i]];
            }
        }
        int ans = 2e9;
        for (int i = 0; i <= sum_s; ++i) {
            if (dp[i]) {
                ans = min(ans, max((i + w - 1) / w, (sum_s - i + f - 1) / f));
            }
        }
        cout << ans << "\n";
    }
    return 0;
}

Rate the problem

1862G - The Great Equalizer

Idea: diskoteka

Tutorial

Solution

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        scanf("%d", &n);
        vector<int> a(n);
        for (int i = 0; i < n; ++i) {
            scanf("%d", &a[i]);
        }
        if (n == 1) {
            int q;
            scanf("%d", &q);
            while (q--) {
                int pos, val;
                scanf("%d %d", &pos, &val);
                cout << val << " ";
            }
            cout << "\n";
            continue;
        }
        multiset<int> aset;
        for (int i = 0; i < n; ++i) {
            aset.insert(a[i]);
        }
        multiset<int> deltas;
        for (auto it = ++aset.begin(); it != aset.end(); ++it) {
            auto prev = it;
            --prev;
            deltas.insert(*it - *prev);
        }
        int q;
        scanf("%d", &q);
        while (q--) {
            int pos, val;
            scanf("%d %d", &pos, &val);
            auto it = aset.find(a[pos - 1]);
            auto nxt = it, prev = it;
            ++nxt; --prev;
            if (it == aset.begin()) {
                deltas.erase(deltas.find(*nxt - *it));
            } else if (it == --aset.end()) {
                deltas.erase(deltas.find(*it - *prev));
            } else {
                deltas.erase(deltas.find(*nxt - *it));
                deltas.erase(deltas.find(*it - *prev));
                deltas.insert(*nxt - *prev);
            }
            aset.erase(it);
            aset.insert(val);
            it = aset.find(val);
            nxt = it, prev = it;
            ++nxt; --prev;
            if (it == aset.begin()) {
                deltas.insert(*nxt - *it);
            } else if (it == --aset.end()) {
                deltas.insert(*it - *prev);
            } else {
                deltas.insert(*nxt - *it);
                deltas.insert(*it - *prev);
                deltas.erase(deltas.find(*nxt - *prev));
            }
            a[pos - 1] = val;
            cout << *--aset.end() + *--deltas.end() << " ";
        }
        cout << "\n";
    }
    return 0;
}

Rate the problem

#include<bits/stdc++.h> using namespace std; using vi = vector<int>; using vvi = vector<vi>; using ll = long long; using pii = pair<int, int>; using pll = pair<ll, ll>; using ull = unsigned long long; int mod = 1e9 + 7; void solve(){ ull n; cin >> n; ull x = ((ull)1 + sqrt(1 + 8*n))/2; ull count = x; ull y = 0; if(!(x&1)){ y = x/2; y *= (x-1); } else{ y = (x-1)>>1; y *= x; } count += n - y; cout << count << '\n'; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int t = 1; cin >> t; while(t--){ solve(); } return 0; }

include <bits/stdc++.h>

using namespace std;

long long knapsack(long long W, vector& weights, vector& values) { long long n = weights.size();

vector<long long> dp(W + 1, 0); for (long long i = 0; i < n; ++i) { for (long long w = W; w >= weights[i]; --w) { dp[w] = max(dp[w], values[i] + dp[w - weights[i]]); } } return dp[W];

}

long long minTimeToDefeatMonsters(long long w, long long f, vector& monsters, vector& values) { long long totalWeight = accumulate(monsters.begin(), monsters.end(), 0LL); long long low = 0, high = totalWeight / f + 1;

while (low < high) { long long mid = (low + high) / 2; long long takenWeight = knapsack(mid * w, monsters, values); if (totalWeight - takenWeight <= mid * f) { high = mid; } else { low = mid + 1; } } return low;

}

int main() { ios_base::sync_with_stdio(false); cin.tie(NULL);

long long t; cin >> t; while (t--) { long long w, f, n; cin >> w >> f >> n; vector<long long> values(n); vector<long long> monsters(n); for (long long i = 0; i < n; ++i) { cin >> monsters[i]; values[i] = monsters[i]; } long long result = minTimeToDefeatMonsters(w, f, monsters, values); cout << result << endl; } return 0;

} CAN YOU PLEASE HELP ME , THIS SOLUTION GIVING TLE ON TESTCASE 29 , HOW CAN I OPTIMIZE IT EVEN FURTHER

#include <bits/stdc++.h> using namespace std; #define LL long long int w, f; int dp(int curr_w, int curr_f, int curr_time, int i, const vector<int>& monsters) { const auto n = monsters.size(); if (i == n) { return curr_time; } const auto monster = monsters[i]; if (curr_w < monster && curr_f < monster) { return dp(curr_w + w, curr_f + f, curr_time + 1, i, monsters); } auto s1 = INT_MAX, s2 = INT_MAX; if (curr_w >= monster) { s1 = dp(curr_w - monster, curr_f, curr_time, i + 1, monsters); } if (curr_f >= monster) { s2 = dp(curr_w, curr_f - monster, curr_time, i + 1, monsters); } return min(s1, s2); } int main() { int t; cin >> t; while (t--) { cin >> w >> f; int n; cin >> n; auto monsters = vector<int>(n); for (int i = 0; i < n; i++) cin >> monsters[i]; const auto res = dp(0, 0, 0, 0, monsters); cout << res << endl; } }

#define um map um<ll,um<ll,um<ll,ll>>> dp; ll dfs(ll arr[], ll i, ll m, ll d, ll a, ll cnt) { if(i==a || m<=0) { return 0; } if(dp[i][m][cnt]) { return dp[i][m][cnt]; } ll watch = ( arr[i] - d*cnt ) + dfs(arr, i+1, m-1, d, a, 1); ll notWatch = dfs(arr, i+1, m, d, a, cnt+1); return dp[i][m][cnt] = max(watch, notWatch); } void solve(){ ll a,m,d; cin>>a>>m>>d; ll i=0, arr[a]; while(i<a) { cin>>arr[i]; i++; } dp.clear(); cout<<dfs(arr, 0, m, d, a, 1)<<endl; } int main() { fast_cin(); ll t; cin >> t; for(ll it=1;it<=t;it++) { solve(); } return 0; }

Comments (139)

Write comment?

ilovenandini

8 months ago, # |

Code of problem C is giving WA on test 1 and it is written that ai <= n ( There won't be any memory issues since all ai≤n ) but in the problem it is given that ai is upto 1e9

→ Reply

josebambu

8 months ago, # ^ |

I mean this solution is not optimized. You can achieve in O(n).

I am wrong. b.push_back(i) is executed only n times.

0duncu

I don't know if there is an optimized solution, but I solved it like this:

Basically, there is a first condition: if n != a[0], the answer is always NO. The explanation is that if you flap that, you won't get the first height every time.

The main part is binary search because you have to find which stick will end after each second. In order to do that, you start seconds from 0 (because the first height is when nothing changes on first). You binary search every time from 0 to n — 1 and take the position. The upper bound you have is the position which, till that, everything will get their end. After that, the count will be n — pos.

https://codeforces.com/contest/1862/submission/220221050 I only check every height (altura means height).

Rick

I have solved it using the difference array method to construct the solution fast with O(1) range update, so when I finished iterating over all the list given to me, I constructed the new array from the difference array that I made, and then it will be just enough to check if the original array and the one one are the same or not.

Number_72

yes but the first element is N and the numbers are sorted in decreasing order so all numbers are at most N.

thanks for the help

xiongdx

Probably not, because if ai > n, "NO" is already output and continues, so there should be no memory problem.

orange_trie

Why there are only 3 comments, even though the edt was published 8 hours ago?

parth_bh

because the editorial has not been attached to the round so only those people who search the recent actions will get it

liuhao24

To be honest, the solution was not very good.

bunkerman

← Rev. 2 →

In D, if x represents 2 balls shouldn't we seek to minimise 2x+y? I am not getting the part with the inequalities:(

BootsHua

the same question (but actually it's problem D lol) I was always thinking how to minimise 2x+y and ended up with no ideas

ah! sorry, yes D.

noobiesAG

+20

If someone prefers video explanations. Here is my Live Screencast of solving problems [A -> F] (with commentary).

PS: Don't judge me by my current rating :(

thanhdno

Mohd_Arbaz

Seems like some master handed his account to a newbie.

humblebose

marne maarne ko hum bhi ni darte.6 ke 6 marunga.

Sajalpandey

Impressive graph, but someone who has been a master, then how you reached to newbie and pupil again? You handed your account to someone?

PS : Your solutions and explanations were good, thank you, Good luck.

anshukumar_729

Helpful.

himanshubanerji

Can anyone explain me the thought process of C, I cannot seem to understand from the editorial :(

jenicius

Which part did you had trouble understanding ?

The main part

vector<int> b;
        for (int i = n; i >= 1; i--) {
            while (b.size() < a[i]) {
                b.push_back(i);
            }
        }

This part while (b.size() < a[i]) why are we doing this?

lekkoo

U can try to draw an example and ovserve, it's easy to find that when you rotate the original shape, the 'height' (the value of a[i]) is the wide(the number of 'i's) of the new shape. just do it by using this code.（maybe my code is clearly enough and U can have a look)

Ahh I think I'm somewhat getting what you are trying to say, I look into it again with this thought process

oloy

your code are kind of different from the editorial. But I think they are same in thoughts

thx, I might caught you up after this contest.(XD)

alright. see you in next div1 + 2, I must become Blue earlier than you!

AsignIntheTell

Oh two funny friends

smit_384

in third question i am getting --> wrong answer Answer contains longer sequence [length = 10000], but output contains 9969 elements. does anyone know how to fix this?

show me your code plz

https://codeforces.com/contest/1862/submission/220417160

Actually, it's index of pre out of bound. So I change it into map and got accepted. https://codeforces.com/contest/1862/submission/220468121

Thank you :)

jwacker

When will we get the ratings for the problems we've solved? Im new here and just started giving contests so im sorry i dont properly know how things happen and how long it takes

brokie

after maybe 5 hours the main tests will run which will take roughly 2 hours to complete, after that it takes another 2-4 hours for the rating changes to update. You can use an extension like cf predictor to predict your rating change accurately.

cool thanks a lot!

taochenyu

I'm so bad that I only thought of the dichotomy of O (n log n) for problem C. I'm sorry for my poor English

xiojoy

← Rev. 4 →

220231839 Maybe there is another way to solve D.

nkp30

No... sqrt() takes logarithmic time complexity, the same as binary search...

Thanks for your comment! I didn't know this until you told me.

You're most welcome! Although, I like the thing that you have revised your comment 3 times!

garv7m

can u explain ur approach?

pranjaljha

would you mind explaining it? i don't get the logic

Seriously_Its_Sameer

Cant the problem c sollution be more optimized?;

VolodiaHeizenberg

You can use difference array to add a constant on a segment. https://codeforces.com/contest/1862/submission/220218223 it looks like this.

Aftershock007

https://codeforces.com/contest/1862/submission/221691703

JasonMendoza2008

There are many grammar typos in Problem D if someone wants to correct them for future people upsolving it.

abdulrahman_204

Why is it giving WA if I use Combination to solve problem D?

pCode14

Combinatorics isn't entirely wrong, but requires some observations.

Take the sample of making 179 different ice creams as an example. If we use a combinatorics approach, we find that; 19C2 = 171 and 20C2 = 190

However, note that the question asks for 179 to be the exact number of ice creams; therefore 190 is in fact incorrect as there are TOO MANY flavours.

The work-around is the observation that we can increment the number of flavours by 1 simply by doubling up on a same-kind flavour. Thus, we can use combinatorics to find the lowerbound with distinct flavours, and then double up on each flavour until we end up with the correct answer.

My solution is attached for clarity: https://codeforces.com/contest/1862/submission/220240409

Note that you must optimise your starting point to prevent TLE

Thanks a lot, I forgot about"exactly n".

azizbeksheripboev07

In C, I submitted 2 solutions, first checking if a1 == n and second one creating the array b. Got wa for first and mle for second, didn't think about combining them, ehhh.

Hazer_BJU

+13

Actually, problem F can be solved using random algorithm, which means you can randomly swap several monsters and defeat them from left to right using water mana first and then fire mana. After approximately 10000 times of attempts, you may pass all the tests, and it runs really fast.

eternal_happiness

RIP scam failed

RHEXAOC

Actually, problem F can be solved using random algorithm, which means..

Hello (from RHEXAOC), don't be upset (too much) about system retesting. I (as well as you) enjoy nondeterministic approaches.

You basically, changed, so-called, knapsack, which is, taking advantage of natural numbers, to sampling a permutation of monsters. There are too many permutations but the specific projection of that permutations to { yes, no } allowed you to pass preliminary tests. I made a test by myself that your program behaved differently than my program. I would be surprised in other case, that's why.

As a bonus let me teach you a knapsack, if you wish. Here we, as I said before, take advantage, that a problem is defined on natural numbers. Which allows us to allocate a cell to every sum. So we can store in that sell a maximum cost. In this problem there are no costs just sum.

bitset<10000 * 100 + 1> btst;
btst[0] = true; // don't forget (I have had forgotten)
for (auto a : aa)
    btst |= btst << a;

Now we have bits set on every possible sum. In case you don't see: when we don't take any element, we have all sums { 0 }; than we take an element and we have { 0, a }, then we take the next element and sums become { 0, a, b, a + b } and so on.

In general case of knapsack, for all possible sums, we store a maximal cost, not just one bit. I guess it is somehow possible to do the opposite (for all costs store something...). You might enjoy a math notation of knapsack problem for some purposes of your own. That's it.

qbning

My D question is WA9 at C++20, but the code passes when I hand it over to C++17, can any god help me to explain the reason of this condition, thanks!

C++20

C++17

mzv

i wonder how did your code pass the test case tho, i mean i checked your code, the "(ans*(ans-1)/2);" in your code actually was reaching the max value of long long in the last test case. it should give wrong answer.

Thank you very much for the heads up, it did overflow. I wasn't sure how my code could pass the data in the C++17 compilation.

i3mr125

use sqrtl not sqrt

Thank you, problem solved!

kenkapo

Is this round unrated?

psn2706

It's rated, see this comment on the rules. I think the ratings will be updated in a few hours, about 6-8 hours, maybe before that.

KevinYang07_fan

what is y?

unrepeated balls, it's in the editorial

I think you misunderstood a little bit here (the editorial isn't that clear as well, in my opinion) $$$\newline$$$ We're not minimizing $$$x+y$$$, we're maximizing it. Let assume that we've found a suitable value of $$$x+y$$$, denote this value $$$x+y=m$$$. Then solving for $$$x$$$ and $$$y$$$, we get $$$x=n-\frac{m(m-1)}{2}$$$, $$$y=\frac{(m+1)m}{2}-n$$$ and $$$2x+y=n-\frac{m(m-3)}{2}$$$. $$$\newline$$$ (Keep in mind that $$$m$$$ has to be chosen such that $$$x,y$$$ are non-negative, this will be important later)$$$\newline$$$ Now consider the function $$$f(x)=\frac{x(x-3)}{2}$$$, we want to maximize it. Because $$$f(1)=f(2)$$$ , we can just ignore the case where $$$m=1$$$ and just consider $$$m \geq 2$$$. Since $$$f(x)$$$ is strictly increasing for $$$x\geq 2$$$, we just have to maximize $$$m$$$ now. From $$$x \geq 0$$$ and $$$n=x+\frac{m(m-1)}{2}$$$ we get $$$n\geq \frac{m(m-1)}{2} (*)$$$. $$$\newline$$$ Let $$$m_0$$$ be the largest integer such that that when plugging $$$m=m_0$$$ in $$$(*)$$$, the inequality is true. Our correct answer is obtained when $$$m=m_0$$$ and we can prove it, $$$2x+y$$$ is minimized because $$$m$$$ is maximized, $$$x$$$ is obviously non-negative, $$$y$$$ has to be positive, because if $$$y\leq 0$$$ then $$$n\geq \frac{(m_0+1)m_0}{2}=\frac{(m_0+1)(m_0+1-1)}{2}$$$. $$$\newline$$$ This will contradict our choice of $$$m_0$$$ at $$$(*)$$$ because now the largest such integer $$$m$$$ is $$$m=m_0+1$$$, not $$$m=m_0$$$ and we're done

____L___

5 months ago, # ^ |

This proof is quite hard to think during the time of the contest !

I agree! I believe the author created the problem base on a famous result in math that is the function $$$f(x,y)=x+\frac{(x+y)(x+y+1)}{2}$$$ is a bijection from $$$\mathbb{N^2}\to \mathbb{N}$$$. But in the end, it's not a math competition so proofs aren't that necessary as long as you're doing the right things even if you can't prove it :D

3 months ago, # ^ |

does this famous result have a name if I want to learn more about it and those like it?

Sorry for replying late but if you're still interested, you can search for "Bijection from NxN to N" like in this post: https://math.stackexchange.com/questions/2781594/bijective-function-from-n-to-n-x-n

Srijal20

4 months ago, # ^ |

just get minimum value x such that x(x-1)/2 <= n
//number of ways of choosing 2balls from x balls

now add the diff //repeated balls

int n; cin >> n;

int x = sqrt(2 * n);

if (x * (x + 1) <= 2 * n) x++;

int diff = n — (x * (x- 1) / 2);

cout << x + diff << endl;

sin_shark

Can someone tell me why greedy approach doesn't work for F.
The problem breaks down to checking whether all the items can be filled inside 2 bags of different sizes.
Here's what I thought:
- Sort the items by their weight in descending order.
- Iterate over the items array and put them inside the bag which has more space left.

no_oneplb

sin_shark Consider the bag sizes to be — 14 and 10.The items are- 10,8 and 6. If we use greedy approach,1st item goes in bag 1 (new size=14-10=4),2nd item goes in bag 2(new size=10-8=2) ,3rd item will be left as bag are of sizes 4 and 2.

Instead, we can put 2nd and 3rd item in bag 1 and 1st item in bag 2.(works)

Thanks, but can you give an intuitive idea on why it wouldn't work.

mustard_with_fries69420

Can anyone explain to me the first part of the tutorial of G?

aditya_108

Lets say the sorted array is

a1 a2 a3

3 2 1

As you can see we are adding 2 to a2 and 3 to a1.It means the difference between the adjacent elements is reduced by 1 when we add this AP to sorted sequence. This will go on until the maximum difference between the adjacent elements is reduced to zero. Then we will have same elements and we can remove one element.

Thus the answer is maximum element + maximum difference.

Hope it helps !!

leylinfarlier

Can anyone tell me, why Online Judge is giving different output than my local machine for following code:

220249582

Its because you have used sqrt. Use sqrtl for long long integers. You can also use binary search to find the square root.

Thanks, it seems there is compiler issue as well. When I use GNU G++20, then I get correct answer.

Edit: yeah that was sqrtl issue.

hrishabh613

Hi, in problem F, the knapsack method that is used, wont the number of computations be of the order 10^8, since knapsack is of time complexity O(N*SUM). How is it accepted then?

+10

10 ^ 8 operations work fine on CF.

oniechan

Then whats the limit in CF, I am pretty confused rn.

Capron

I created dp[100*1e6] in F problem but this gives me memory limit exceed why? https://codeforces.com/contest/1862/submission/221041512

faizanhussain2310

6 months ago, # ^ |

this is because due to binary search it will become almost 30*dp[1e8] which will definately get TLE or MLE

changinmong10

What about E?I can't able to solve E.Can u give me hint ?

For every positive movie show we will take at most m-1 positive shows before it and subtract currentIndex*cnt from the sum because of the penalty.

TL is 4s, even with 1s I think it can (barely) pass with optimizations Not to mention there's the bitset optimization

rock_nroll

USE space optimisation for better Space Complexity ...

+11

I just tested it, you can easily pass without bitsets in only 109ms 220410300

olegmak

Maybe tests aren't good? I solved it using binary search (that means I solve knapsack log(SUM) times instead of just once) and my solution still passes with just about 200ms runtime.

BrownMunda

Hey, could you please share your solution? I was trying to solve using binary search too during the contest but failed.

https://codeforces.com/contest/1862/submission/220434809

Problem F: Can some one tell me why isn't the tutorial solution giving TLE as it is order of O(sum*n) i:e O(10^8), or am I wrong...

SakiBee

for which problem?

i_love_turtles

It is guaranteed that the sum of n over all test cases does not exceed 100.

So the total time complexity is O(10^8) as u said, and this fits perfectly for the time constraint :D

← Rev. 3 →

-19

Because vector<bool> can be understood as bitset, they are both very fast and have a complexity of O(n*sum/64).

vector does not support shift operations thus you can't get 1/64 constant factor improvement which is possible when using bitset.

This is a very common scenario for bitset.

As a math person, I find problem D very interesting. The problem of proving that any positive integer $$$n$$$ can be written as $$$x+\frac{(x+y)(x+y-1)}{2} $$$ for some non-negative integers $$$x,y$$$ was once given to a provincial math contest in my country. Props to the problem setter!

dark_soul9

[can anyone help me in finding the error in my code of [problem:1862E]] 220407220

DarkWillow

Problem B,

For b=[4,6,3] why a=[4,6,3,3] is not a valid sequence ?

It is a valid sequence.

-10

In third question i am getting --> wrong answer Answer contains longer sequence [length = 10000], but output contains 9969 elements. does anyone know how to fix this?

pragunb02

how to do E ques by dp (knapsack maybe dp[currIdx][prevIdx][moves_till_now])

To be precise, this is recursion.

soumil1234

Check this solution

ggk227

Can someone please explain as to why commented code is giving TLE for G.

Thanks in advance for the help :).

yuuma

erase invalid iterator position cause unexpected behavior Your condition it != end can break prev iterator if it == begin

socotra

Problem C:

There is a cleaner way to construct the fence when planks are laid horizontally. The idea is to update all the points starting from 0 to a[i]-1 by height 1 when plank a[i] is laid horizontally.

This can be done by a very simple yet efficient algorithm: range update, point query in offline queries.
Initialize array b of length n with zeros. Now if you want to update the range L to R, do b[L]++, b[R+1]-- for all the ranges and finally take prefix sum of array b.
Finally you can check if array a and b are equal

Submission: https://codeforces.com/contest/1862/submission/220436621

Moaaz-Mahmoud

I thought I'm the only one who names his boolean flags "meow" LOL

BLACKBULLET

Hello, can anyone explain for me why we use this code in problem F ?

                ans = min(ans, max((i + w - 1) / w, (sum_s - i + f - 1) / f));

I can only understand the reason for the code below is use to mark all strength possible

                dp[w] = dp[w] || dp[w - s[i]];

i'm newbie :<

just a way to calculate the ceil value : ceil( a/b) = (a+b-1)/b ...

hmm, I think can understand that but why we need to minus for 1 ? :

subhamjha4444

Can somebody explain that dp state in the solution for problem F?

dp[i] == true means putting weight i into knapsack is possible.

$$$dp[i]$$$ means that if we can get the value i from the sum of any number in s(the vector in the solution).

map<int, bool> ex; what does ex define in your solution

It means the sum exists(can be made by adding any number of monster's value).

thumbass

Note that the total strength of the monsters is given to us. Therefore, it is enough for us to spend as much of the available water mana as possible, so that there is enough fire mana left for the remaining monsters. This is a well-known knapsack problem.

Can anyone tell me which well-known knapsack (variation) this is?

0-1 knapsack.

ccpp

Can you please explain why is it a 0-1 knapsack.
Where are weights and capacities etc. which are parts of knapsack.
I can't understand.
Also, If possible suggest some resources(problems) to learn these types of implicit knapsack.

The total sum of the monsters' strength is the knapsack' s capacity. Each strength of the monster is both its weight and capacity.

Then in my first solution(220277552) which is MLE dp[i][j] means The maximum amount of capacity that the first i monsters can occupy without exceeding the capacity j.Then I used scrolling array optimization in my second solution(220282293) and AC.

Then we can get a set including the sum of the strength by selecting any number of monsters from all and adding their strength together.

Then we can enumerate all the divisions of the sum of the strengths of all monsters into two parts, and use the set we just got to judge whether it can be divided in this way, and constantly update the least amount of time, that is, the answer.

I don't have good advice on the specific problems of some implicit knapsack, you can search the Internet to find them.

Thanks

arf01

chharshch123

220277336 can anyone tell why im getting tle

N-E-O

can someone explain the TC of problem F.

Worst Tutorial. Instead of giving explanations, the author has written 'This can be done', 'This is well known',etc.etc.

_NonSense_

Can someone please tell me why this works in D '''mid=low+(high-low)/2+1;''' and this doesn't '''mid=low+(high-low)/2;''' in the binary search https://codeforces.com/contest/1862/submission/220505346

rajat_jaiswal

Better Solution for C (space optimized): https://codeforces.com/contest/1862/submission/220502761

mmattyboi

Could someone please explain why my approach for F does not work?

strokeme

Anybody else think Vika is an greedy, picky h*e on that carpet problem?

dnx04

problem G is bad because of its TL and n = 1 case

henryzhan13

The code of problem F will cause time to exceed on test 11. Is there another solution?

If anyone was looking for a DP approach to E, although inefficient, It is what I thought of when I saw this question:

haryadi

7 months ago, # |

I don't understand the A.. Doesn't it will make fnd to 4 in this case 4 4 vkak iiai avvk viaa and will result to YES?

meliodas_mc

the result for this cases is NO, is one letter for each colum, v in colum 0 -row 0, i in colum 1 — row 1, but k is the next letter but not is in the colum 2 of any row.

4 months ago, # |

For problem D

muhhaaaa

11 days ago, # |

Why we take min(2e9, 2 * n) in D?

diskoteka's blog

include <bits/stdc++.h>