1132A - Regular Bracket Sequence

**Tutorial**

Tutorial is loading...

**Solution (BledDest)**

```
cnt = []
for i in range(4):
cnt.append(int(input()))
if(cnt[0] == cnt[3] and (cnt[2] == 0 or cnt[0] > 0)):
print(1)
else:
print(0)
```

**Tutorial**

Tutorial is loading...

**Solution (Roms)**

```
#include <bits/stdc++.h>
using namespace std;
const int N = 300009;
int n;
int a[N];
long long res[N];
int main() {
long long sum = 0;
scanf("%d", &n);
for(int i = 0; i < n; ++i){
scanf("%d", a + i);
sum += a[i];
}
sort(a, a + n);
memset(res, -1, sizeof res);
int m;
scanf("%d", &m);
for(int i = 0; i < m; ++i){
int c;
scanf("%d", &c);
if(res[c] == -1){
res[c] = sum - a[n - c];
}
printf("%lld\n", res[c]);
}
return 0;
}
```

**Tutorial**

Tutorial is loading...

**Solution (BledDest)**

```
#include <bits/stdc++.h>
using namespace std;
const int N = 5043;
int p1[N];
int p2[N];
int p3[N];
int n, q;
int l[N], r[N];
int solve(int idx)
{
memset(p1, 0, sizeof p1);
for(int i = 0; i < q; i++)
{
if(i == idx) continue;
p1[l[i]]++;
p1[r[i]]--;
}
memset(p2, 0, sizeof p2);
int c = 0;
for(int i = 0; i < n; i++)
{
c += p1[i];
p2[i] = c;
}
memset(p3, 0, sizeof p3);
for(int i = 0; i < n; i++)
p3[i + 1] = p3[i] + (p2[i] == 1 ? 1 : 0);
int ans = -int(1e9);
for(int i = 0; i < q; i++)
{
if(i == idx) continue;
ans = max(ans, p3[l[i]] - p3[r[i]]);
}
for(int i = 0; i < n; i++)
if(p2[i] > 0)
ans++;
return ans;
}
int main()
{
cin >> n >> q;
for(int i = 0; i < q; i++)
{
cin >> l[i] >> r[i];
l[i]--;
}
int ans = 0;
for(int i = 0; i < q; i++)
ans = max(ans, solve(i));
cout << ans << endl;
}
```

**Tutorial**

Tutorial is loading...

**Solution (PikMike)**

```
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int N = 200 * 1000 + 13;
const long long INF64 = 1e18;
int n, k;
long long a[N];
int b[N];
long long cur[N];
vector<int> qr[N];
bool check(long long x){
forn(i, k) qr[i].clear();
forn(i, n) cur[i] = a[i];
forn(i, n){
long long t = cur[i] / b[i] + 1;
cur[i] %= b[i];
if (t < k) qr[t].push_back(i);
}
int lst = 0;
forn(t, k){
while (lst < k && qr[lst].empty())
++lst;
if (lst <= t)
return false;
if (lst == k)
return true;
int i = qr[lst].back();
if (cur[i] + x < b[i]){
cur[i] += x;
continue;
}
qr[lst].pop_back();
long long nt = (cur[i] + x) / b[i];
cur[i] = (cur[i] + x) % b[i];
if (lst + nt < k)
qr[lst + nt].push_back(i);
}
return true;
}
int main() {
scanf("%d%d", &n, &k);
forn(i, n) scanf("%lld", &a[i]);
forn(i, n) scanf("%d", &b[i]);
long long l = 0, r = INF64;
while (l < r - 1){
long long m = (l + r) / 2;
if (check(m))
r = m;
else
l = m;
}
if (!check(r))
puts("-1");
else
printf("%lld\n", check(l) ? l : r);
return 0;
}
```

**Tutorial**

Tutorial is loading...

**Solution (BledDest)**

```
#include <bits/stdc++.h>
using namespace std;
const int N = 9;
const int L = 840;
typedef long long li;
li dp[N][L * N];
li W;
li cnt[N];
int main()
{
cin >> W;
for(int i = 0; i < 8; i++)
cin >> cnt[i];
for(int i = 0; i < N; i++) for(int j = 0; j < L * N; j++) dp[i][j] = -1;
dp[0][0] = 0;
for(int i = 0; i < 8; i++)
{
for(int j = 0; j < L * N; j++)
{
if(dp[i][j] == -1) continue;
int b = L / (i + 1);
if(cnt[i] < b)
b = cnt[i];
for(int k = 0; k <= b; k++)
{
li& d = dp[i + 1][j + k * (i + 1)];
d = max(d, dp[i][j] + (cnt[i] - k) / (L / (i + 1)));
}
}
}
li ans = 0;
for(int j = 0; j < L * N; j++)
{
if(j > W || dp[8][j] == -1)
continue;
ans = max(ans, j + L * (min(dp[8][j], (W - j) / L)));
}
cout << ans << endl;
}
```

**Tutorial**

Tutorial is loading...

**Solution (Roms)**

```
#include <bits/stdc++.h>
using namespace std;
const int N = 505;
int n;
string s;
int dp[N][N];
int calc(int l, int r){
int &res = dp[l][r];
if(res != -1) return res;
if(l > r) return res = 0;
if(l == r) return res = 1;
res = 1 + calc(l + 1, r);
for(int i = l + 1; i <= r; ++ i)
if(s[l] == s[i])
res = min(res, calc(l + 1, i - 1) + calc(i, r));
return res;
}
int main(){
cin >> n >> s;
memset(dp, -1, sizeof dp);
cout << calc(0, n - 1);
return 0;
}
```

**Tutorial**

Tutorial is loading...

**Solution (adedalic)**

```
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
#define x first
#define y second
int n, k;
vector<int> a;
inline bool read() {
if(!(cin >> n >> k))
return false;
a.assign(n, 0);
fore(i, 0, n)
cin >> a[i];
return true;
}
int T = 0;
vector< vector<int> > g;
vector<int> tin, tout;
void dfs(int v) {
tin[v] = T++;
for(int to : g[v])
dfs(to);
tout[v] = T;
}
vector<int> Tmax, Tadd;
inline void push(int v) {
Tadd[2 * v + 1] += Tadd[v];
Tadd[2 * v + 2] += Tadd[v];
Tadd[v] = 0;
}
inline int getmax(int v) {
return Tmax[v] + Tadd[v];
}
void addVal(int v, int l, int r, int lf, int rg, int val) {
if(l == lf && r == rg) {
Tadd[v] += val;
return;
}
int mid = (l + r) >> 1;
push(v);
if(lf < mid) addVal(2 * v + 1, l, mid, lf, min(mid, rg), val);
if(rg > mid) addVal(2 * v + 2, mid, r, max(lf, mid), rg, val);
Tmax[v] = max(getmax(2 * v + 1), getmax(2 * v + 2));
}
inline void solve() {
g.resize(n + 1);
tin.resize(n + 1, 0);
tout.resize(n + 1, 0);
vector<int> st;
for(int i = n - 1; i >= 0; i--) {
while(!st.empty() && a[st.back()] <= a[i])
st.pop_back();
int nxt = st.empty() ? n : st.back();
g[nxt].push_back(i);
st.push_back(i);
}
dfs(n);
Tmax.assign(4 * (n + 1), 0);
Tadd.assign(4 * (n + 1), 0);
fore(i, 0, k - 1)
addVal(0, 0, n + 1, tin[i], tout[i], +1);
for(int l = 0; l + k <= n; l++) {
addVal(0, 0, n + 1, tin[l + k - 1], tout[l + k - 1], +1);
cout << getmax(0) << " ";
addVal(0, 0, n + 1, tin[l], tout[l], -1);
}
cout << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cout << fixed << setprecision(15);
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
```

My solution for C:

Make an array

aofnvectors wherea_{i}contains all the painters who paint theith panel. Find 'total', the total number of painted panels using all of the painters. Then, we make a 2D array 'count' that is initialized to 0. Here, 'count[i][j]' is 'the number of sections that have no one painting them ifiandjare removed.So, loop over all elements of

a. If`a[i].size()==2`

, then`count[a[i][0]][a[i][1]]++`

and`count[a[i][1]][a[i][0]]++`

. If`a[i].size()==1`

, then for allj≠a[i][0], perform`count[a[i][0]][j]++`

and`count[j][a[i][0]]++`

.Then, simply find the minimum value of

`count[i][j]`

, and subtract that from`total`

to get your answer. Solution works inO(n^{2}).This took me an embarrassing amount of time to figure out, and, in addition to my A getting hacked (due to a REALLY embarrassing careless mistake which wasn't caught in the pretests), my rating really took a hit this contest :'( Which is such a shame because I got F pretty early and I thought this contest was gonna be one of the good ones... from 3rd place to 900something, lmao. Someone play Viva la Vida.

By the way, great contest! I wasn't able to get E, but i especially like it and shall try upsolving it later. The problems seem really interesting and generally should have been doable if I didn't choke so hard — oh well. My only comment is that F is WAY easier than E and D, and perhaps even C for a lot of us.

I did the same thing but without the crucial

`if(section[j].size() < 3)`

so it got MLE hacked. Although why exactly it MLE on that specific hack is still unclear to me.Oh wow, I did have that < 3 check in my solution, yeah. I didn't think it'd end up being important! That's a weird MLE

can you please share your submission on problem c. I am still struck on it. Thanks in advance

Can you please explain why did you ignore the painters when it's more than 2?

`if(section[j].size() < 3) section[j].push_back(i);`

We only care about the sections that could become unpainted if we removed 2 painters. If there are at least 3 people painting a section already, then no matter who you remove, that section is already 'locked in'.

Sorry for not responding to your other comment. I generally don't like debugging other people's code for them. But I think taking the min(ans) at each iteration of the loop is a mistake — if you look at my code, i have a big 2D array, do all the computations, THEN find the minimum at the end.

Third question is little bit more tricky from last div2"s third question.

I agree, that was much harder than C questions normally are. I think the next easiest question after B is actually F (which is a standard and straightforward DP)

Depends on how good you are with DP, I solved C and D, and found both of them pretty straight forward to be honest, the only thing was that the time limit for D was a bit tricky, but it took me quite a while to upsolve F after the competition ended actually. While I'm not completely hopeless at DP I still have a bit to go before I'm completely comfortable with it though.

Can someone explain problem F with example, I am not able to understand the dp state

1.let str[i][j] (i<=j) be the string formed by characters between ith and jth characters (inclusive). 2.define dp[i][j] to be the minimum number of steps to remove all the characters of str[i][j]. 3.This removal can be done in two ways. i.remove the jth character on its own, in this case dp[i][j]=1+dp[i][j-1] ii. dont remove the jth character on its own. rather remove it another character same as the jth. there may be many such characters . let nth character be same as jth and of course i<=n<j .So u must delete all the characters between nth and jth to bring jth and nth character side by side . And u have to do it in minimum step possible . there can be many such n's between i and j . u have to choose the one that makes ur steps minimum . so here dp relation is dp[i][j]= dp[n+1][j-1]+dp[i][n] . u have iterate through all the n's between i and j such that nth letter is same as jth letter and choose the minimum one

But this approach isn't taking into consideration if deleting jth elements say all three together. i.e.

`adaba`

, suppose (1-base indexed) j be 5, then we will only be checking if aa(1, 5) or aa(3, 5) or a(5) can be deleted together, why shouldn't we check deleting together aaa(1,3,5) ?if u want to delete aaa then first u have to get aa . then we will get aaa

that's my point, if we already got aa and you are deleting it in one operation, next time you have to delete remaining 'a' in another operation- thus increasing the deletions to 2, instead of 1.

For example, I was going with this greedy approach first compress the string, i.e. compressed array will have all the adjacent elements different, (e.g.

`aaabbabb`

changes to`abab`

). Then I was solving it considering the element with highest freq. to be deleted as the last all together. Its failing on 5th test case. But this approach of mine only covers the fact that, all occurrences of highest freq. element must be deleted all together at last — that's why this dp based question is still bugging me :(However ur greedy technique is wrong . Try this one 7 acbabca correct answer : 4 but ur greedy technique outputs 5

Thanks for such a short test case, will look into the dp based approach carefully then :)

My solution for E:

Notice that if the total sum is bigger or equal than W, the answer must be between W-8 and W. So I approached the total sum to between W and W+8 by greedly removing the itens and then I checked if I could remove the difference between the actual sum and the answer, this could be done using smaller knapsacks as the difference would be no more than 16 (W+8-(W-8)).

thanks for awesome tip.

The cool part is that this solution can solve the same problem with a larger limit and the knapsacks can also be optimized by using bitmasks. :)

Could someone please explain me why did my code get accepted? (I have no idea O.o, i thought that a pseudo brute force should work but i'm not sure why or maybe there are weak test cases, idk)

My code

Thanks in advanced.

Please take a look at this code. It is as yours but I just reduce the number of iterations performed by you in outermost for loop(100 -> 2) and it still gets accepted.

Interesting, but yes you were just lucky. Your code fails on

Basically take any test case that doesn't work with attempting greedily adding as much as you can from all permutations, and then just make sure that you more than max(j) (which is 100 in your case) extra of each type needed and it'll break. Like this you would need a j of about 10^16 for your code to pass

Edit: This is test case 21 from system tests with zeros added to each of the counts, your code outputs 5405 when it should output 5406

Edit2: Even simpler. Actually it's so easy to break. Take this case:

The answer is simply take 2 5s and an 8, but your code outputs 16 as it always tries either 3 5s first or 2 8s which won't work

I am not able to understand the solution of E .can some one elaborate it,please?How the equation could be written like this ? Thank you in advance.

I solved C in something like O(nlog(q) + q^2).

Keep two prefix sums of how many segments are covered by exactly 1 and exactly 2 painters respectively. You build these in O(nlog(q)) with a sweep line over the n segments keeping track of how many painters are in each. Also keep just a single integer keeping track of how many total segments are covered by at least one painter.

Now iterate over each pair of painters and for each pair take the number of segments covered by any painter and subtract from this number the number of segments which only 1 painter (this painter) covers. Then if they intersect subtract the number of segments with exactly two painters covering it (exactly these two painters). This can all be done in O(1) because of the prefix sums built before. In my code I also added back in the number covered by exactly 1 in the intersection but as I'm writing this I see that it's of course always zero as two painters are intersecting, so it's redundant.

code: https://codeforces.com/contest/1132/submission/50838090

there is a typo in the tutorial of F:clear the string. It should be s_i = s_l.

In C,my thought process was in the following direction. Sort all the pairs according to their interval length and then iterate over each interval along with maintaining a boolean array to mark which sections are painted.Can we reach the solution using this approach,if yes how?

I don't think so. As it's not only the length it's also the position. Imagine this list of segments

Obviously the answer would be taking the 0-5 interval, the 6-6 and 7-7 interval and then all rest are redundant but your algorithm would take the 0-5 interval and then the 4 redundant ones

Can C be solved using segment trees? If yes, then can someone please share an efficient solution?

It can but u dont need to cause there are no updation such as changing the range of a painter. So we will solve it using only cumulative sum array or prefix array.

Yeah a prefix array would be enough here. I just wanted to know if it was possible to write a segment tree solution. Thanks for the reply!

Indeed it is possible . U can determine range sum in O(logn) complexity using segment tree . However using prefix array complexity would be O(1).

check my solution, i used segment trees to count number of '1' and '2'

https://codeforces.com/contest/1132/submission/50845077

Thanks! I'll look at the solution.

My solution For G:

dsu on tree

https://codeforces.com/contest/1132/submission/50995547

Hey, I saw a few others with dsu solutions. Can you elaborate on your idea?

Why is G not Increasing subsequence problem? can someone elaborate the what does the meaning of the problem G in simple way.

For a = [1, 2, 100, 3, 4], you could not choose a index subsequence like [1, 2, 4, 5] because 4 is not the minimum number such that a[4] > a[2].

The only choice is [1, 2, 3].

G: Managed to squeeze HLD O(n * log^2(n)) with Fenwick tree and binary search 51106103

Solution shortly : go from right to left and keep multiset of possible ending of sequence, add and delete nodes as you go. While deleting node, erase it from multiset, and add it's children to multiset. While adding node, find highest parent which you can improve with HLD & binary search. After finding this node just do += 1 from added node to it.

In the editorial for G, what makes a vertex marked?

Is it "if it has a node that points to it in the current subsegment"?

we mark the first k vertex and the maximum is answer[1].

then we unmark vertex 1 and mark vertex k+1, and the maximum is answer[2].

and so on.

Can anyone help me. I find the test when a parsed program for problem G gives an incorrect result.

`6 6 3 29 5 5 28 6`

True answer : 3( a[0], a[2], a[5] )

Answer in program: 2

Or i have mistake?

Can someone provide a test case where this solution of E fail or provide a proof of its correctness? https://codeforces.com/contest/1132/submission/50862512

Can someone explain problem B ? I am not able to follow the tutorial.

//Solution: DIV2 — C

Simple Bruteforce Solution:

https://codeforces.com/contest/1132/submission/54590211

In problem F, the recurrence according to the editorial is

`f(l, r) = min f(l+1, i-1) + f(i, r)`

But since we are combining s[l] with s[i], can we not have a recurrence like:

`f(l, r) = min f(l+1, i-1) + 1 + f(i+1, r)`

the +1 coming from combining s[l] and s[i] and we start the 2nd recursive call from i+1 instead of i. How are the two different?

It is not written that we are exactly combining s[l] with s[i], instead it is written that s[l] and s[i](maybe along with some s[k]'s such that s[k]=s[l]) will be deleted in a single turn.

Your reccurence is for s[i] and s[l] only will be deleted in a single turn, which is wrong(since it may not be optimal).

canyou elaborate more i didnt understand why we arenot using i+1 in second?

Alternative solution for problem D

Binary search the answer. Suppose that you are checking the charger with power $$$x$$$. At the beginning, consider each laptop separately and charge it as late as possible, and keep an array $$$c$$$ with the number of laptops that should be charged each minute. There are two cases:

Of course, if the total number of charges becomes $$$\geq k$$$, we can just return false.

The problem with this approach is that we are not considering that we can't charge more than one laptop in a minute. However, we can consider the total number of laptops that should be charged until each minute by taking the prefix sums of the array $$$c$$$. The condition is easy: the charger with power $$$x$$$ can be used iff $$$c[i] \leq i + 1$$$ for each $$$i$$$.

Submission: 90456305

For C, https://www.youtube.com/watch?v=4GNUt5unEnM

Can someone please help me figure out why O(N^3) solution for Problem-F is getting accepted ?

Since N is 500 , N^3 should give TLE .

Who would have thought this will be the first question in Cisco's Online Assessment

which question?

in the tutorial of F in the last line in formula,Si=Sl not Sr

Added some

hintsandthought processfor F. Clear the String on CF Step.Essentially the same as the editorial, but also talks about different ways for DP transitions that might not really work, but are the first ones to come to mind during a contest.