I_love_Chris_Evans's blog

By I_love_Chris_Evans, history, 2 months ago, ,

The problem is as follows:
There is a long string of paper, of length at most $10^{6}$ and we have $n$ pieces of colored tape with us, of varying lengths. We have to process some queries online. In a single query, we have two options: apply a single tape on a segment of the paper, or remove a previously applied tape from the paper. If any segment has multiple tapes covering it, only the queried tape will be removed. After each query, we have to print the amount of paper which has at least one tape covering it.

e: Suppose n=3, and the tapes are of lengths [3,4,5], and the queries are as follows:
1. Apply tape-1 on segment [8,10]
2. Apply tape-2 on segment [10,13]
3. Apply tape-3 on segment [5,9]
4. Remove tape-2
5. Remove tape-1
6. Remove tape-3
7. Apply tape-2 on segment [1,4]

Then, the output is:
3
6
9
6
5
0
4

You can assume that the queries are valid, ie: a tape has to be applied before it can be removed, and the number of times a tape is applied is either the same number of times it's removed in the queries or one more than it, in any prefix of the list of queries. Tapes are reusable. The length of segment covered in a query is same as the length of tape, for each apply type query.

How to solve it? All my segment tree ideas for this problem are wrong.

• 0

By I_love_Chris_Evans, history, 2 months ago, ,

I have a O($2^{n} \cdot n$) solution, which fails on 2 test cases. So, I don't know if my logic is wrong, or it's a bug. Seems like logic is wrong. So, what's the correct logic?

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long
#define N 200005
#define all(v) v.begin(),v.end()
#define pii pair<int,int>
#define piii pair<ll,pii>
#define print(x) cout << #x << "=" << x << "\t";
#define newline cout << endl;

int n;
int x;
int a[25];
ll sum[1 << 21];
pii dp[1 << 21];

int main() {
ios::sync_with_stdio(false); cin.tie(NULL);
cin >> n >> x;
for(int i=0;i<n;i++)
cin >> a[i];

int lim = (1 << n);
for(int i=1;i<lim;i++) {
sum[i] = a[__builtin_ctz(i)] + sum[i - (i&-i)];
}

dp[0] = {1, 0};

for(int i=1;i<lim;i++) {
int p = i;
int p2 = 0;
pii ans = {1e9, -1};
while (p) {
int c = p&-p;
p -= c;
int k = p + p2;
if (ans.first > dp[k].first + (sum[dp[k].second + c] > x)) {
ans.first = dp[k].first + (sum[dp[k].second + c] > x);
if (sum[dp[k].second + c] <= x) {
if (k - dp[k].second > 0 && sum[k - dp[k].second] <= sum[dp[k].second + c])
ans.second = k - dp[k].second;
else
ans.second = dp[k].second + c;
}
else {
if (dp[k].second > 0 && sum[dp[k].second] <= sum[c])
ans.second = dp[k].second;
else
ans.second = c;
}
}
p2 += c;
}
dp[i] = ans;
}

cout << dp[lim - 1].first;
return 0;
}


• +3

By I_love_Chris_Evans, history, 3 months ago, ,

• +44

By I_love_Chris_Evans, history, 3 months ago, ,

My logic:
1. Check if the query can be satisfied completely with just one segment.
2. Sort segments first based on increasing left endpoint and then based on decreasing right end point. Traverse the sorted segments from left to right. Remove unnecessary segments. Each segment that remains must be the longest segment connecting the previously connected segments, going as far right as possible. Therefore, any three consecutive segments A, B, C which are remaining should not satisfy ((A union C) intersect B) == B.
3. Sort the trimmed array based on increasing right endpoint, and then based on increasing left endpoint.
4. Use lower_bound to find the first and last segment in the trimmed array corresponding to left and right ends of the query, and check one segment to the right from the first segment (the one we found for the left endpoint).
5. Check if the segments found are valid, and print the outcome.

Can anyone help me find the reason for WA?
Thanks!

Edit: Nvm, found a test case
segments : [1, 4] [2, 6] [3, 8] [5, 9] [7, 10]
queries : [2, 9]
Correct answer is 2, I'm printing 3 because I removed the needed segments.

• 0

By I_love_Chris_Evans, history, 3 months ago, ,

I just can't figure out why TLE. Complexity seems to be $n^{2}logn$. Please help.

• +5

By I_love_Chris_Evans, history, 12 months ago, ,

There's an array A of N elements. You don't know the element values, but you do know that each of them is a power of 2. You are given xor of some segments of this array, and your task is to determine one valid array, which satisfies all the segment xor.

eg: N = 6, segments = 3
xor: [1, 2] = 3, [2, 3] = 0, [3, 6] = 12
one valid value of A is [1, 2, 2, 8, 2, 4].

• +26

By I_love_Chris_Evans, history, 12 months ago, ,

Hello everyone!

Can anyone please help me with this problem : Given a graph with positive weighted edges, how to choose a subset of edges with maximum sum such that no two edges share a common vertex?

This wasn't taken from any judge, I'm just interested in knowing how it can be solved. As it's not from any judge, there are no constraints except what I already mentioned above.

Thanks!

• -5

By I_love_Chris_Evans, history, 13 months ago, ,

If anyone's looking for a teammate, please let me know. Female participants preferred(as then we have all girls team). No restriction on ratings :)

Thanks!

PS: Requesting to not spam in comments.