Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
for _ in range(int(input())):
n = int(input())
p = [int(x) - 1 for x in input().split()]
ans = 3
for i in range(n):
if p[p[i]] == i:
ans = 2
print(ans)
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (adedalic)
fun main() {
repeat(readln().toInt()) {
val s = readln().map { it.code - '0'.code }
val zeroes = s.count { it == 0 }
val cnt = intArrayOf(0, 0)
var ans = 0L
for (c in s) {
cnt[c]++
if (c == 0)
ans += if (cnt[1] > 0) 1 else 0
else
ans += (zeroes - cnt[0])
}
println(ans)
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
using li = long long;
const li INF = 1e18;
int main() {
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
vector<li> a(n);
for (auto& x : a) cin >> x;
vector<vector<li>> dp(n + 1, vector<li>(k + 1, INF));
dp[0][0] = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= k; ++j) {
li mn = INF;
for (int d = 0; j + d <= k && i + d < n; ++d) {
mn = min(mn, a[i + d]);
dp[i + d + 1][j + d] = min(dp[i + d + 1][j + d], dp[i][j] + (d + 1) * mn);
}
}
}
cout << *min_element(dp[n].begin(), dp[n].end()) << '\n';
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
#define sz(a) int((a).size())
using li = long long;
int main() {
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
vector<int> a(n), b(n);
for (auto& x : a) cin >> x;
for (auto& x : b) cin >> x;
vector<int> ord(n);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int i, int j) {
return b[i] > b[j];
});
li f = 0, p = 0;
for (int i : ord) p += max(0, b[i] - a[i]);
li ans = 0;
multiset<int> s;
if (sz(s) == k) ans = max(ans, p - f);
for (int i : ord) {
p -= max(0, b[i] - a[i]);
s.insert(a[i]);
f += a[i];
if (sz(s) > k) {
f -= *s.rbegin();
s.erase(--s.end());
}
if (sz(s) == k) ans = max(ans, p - f);
}
cout << ans << '\n';
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
#define sz(a) int((a).size())
vector<int> t, p;
void push(int v) {
if (v * 2 + 2 >= sz(t)) return;
t[v * 2 + 1] += p[v]; p[v * 2 + 1] += p[v];
t[v * 2 + 2] += p[v]; p[v * 2 + 2] += p[v];
p[v] = 0;
}
void upd(int v, int l, int r, int L, int R, int x) {
if (L >= R) return;
if (l == L && r == R) {
t[v] += x; p[v] += x;
return;
}
int m = (l + r) / 2;
push(v);
upd(v * 2 + 1, l, m, l, min(m, R), x);
upd(v * 2 + 2, m, r, max(m, L), R, x);
t[v] = min(t[v * 2 + 1], t[v * 2 + 2]);
}
int get(int v, int l, int r, int L, int R) {
if (L >= R) return 1e9;
if (l == L && r == R) return t[v];
int m = (l + r) / 2;
push(v);
return min(
get(v * 2 + 1, l, m, l, min(m, R)),
get(v * 2 + 2, m, r, max(m, L), R)
);
}
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (auto& x : a) cin >> x, --x;
t = p = vector<int>(4 * n);
vector<vector<int>> pos(n);
int ans = 0, st = 0;
for (int i = 0; i < n; ++i) {
int x = a[i];
pos[x].push_back(i);
int k = sz(pos[x]);
if (k > 0) upd(0, 0, n, st, pos[x][k - 1] + 1, +1);
if (k > 1) upd(0, 0, n, st, pos[x][k - 2] + 1, -2);
if (k > 2) upd(0, 0, n, st, pos[x][k - 3] + 1, +1);
if (get(0, 0, n, st, i + 1) == 0) {
ans += 1;
st = i + 1;
}
}
cout << ans << '\n';
}
int main() {
int t;
cin >> t;
while (t--) solve();
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include<bits/stdc++.h>
using namespace std;
mt19937_64 rnd(12341234);
int n, k;
vector<int> deck;
vector<int> dp;
vector<vector<bool>> odd;
vector<bool> full_odd;
vector<long long> val;
vector<long long> hs;
bool bad(const vector<bool>& v)
{
for(int i = 0; i < k; i++)
if(!v[i])
return false;
return true;
}
vector<bool> inv(const vector<bool>& v)
{
vector<bool> res(k);
for(int i = 0; i < k; i++)
res[i] = !v[i];
return res;
}
vector<bool> get_suffix(int l)
{
vector<bool> v(k);
for(int i = l; i < n; i++) v[deck[i]] = !v[deck[i]];
return v;
}
int get_next(long long cur, int x)
{
for(int i = x; i <= n; i += 2)
if(hs[i] == cur)
return i;
return -1;
}
int main()
{
cin >> n >> k;
deck.resize(n);
for(int i = 0; i < n; i++) cin >> deck[i];
for(int i = 0; i < n; i++) --deck[i];
val.resize(k);
for(int i = 0; i < k; i++)
while(val[i] == 0)
val[i] = rnd();
int max_score = 0;
dp.resize(n + 1);
full_odd.resize(k);
odd.resize(n + 1, vector<bool>(k));
hs.resize(n + 1);
long long cur_hash = 0;
for(int i = 0; i < n; i++)
{
cur_hash ^= val[deck[i]];
if(full_odd[deck[i]]) max_score++;
full_odd[deck[i]] = !full_odd[deck[i]];
odd[i + 1] = full_odd;
hs[i + 1] = cur_hash;
}
for(int i = k; i <= n; i++)
dp[i] = 1e9;
long long start = 0ll;
for(int i = 0; i < k; i++) start ^= val[i];
int pos = get_next(start, k);
if(pos == -1)
{
cout << max_score << endl;
}
else
{
dp[pos] = 0;
int ans = 1e9;
for(int p = k; p <= n; p += 2)
{
if(dp[p] > 1e8) continue;
vector<bool> suff = get_suffix(p);
vector<int> o, e;
for(int j = 0; j < k; j++)
if(suff[j])
e.push_back(j);
else
o.push_back(j);
int es = e.size();
int os = o.size();
bool flag = true;
for(int i = 0; i < os && flag; i++)
for(int j = 0; j < i && flag; j++)
{
int x = o[i];
int y = o[j];
int add = 0;
long long h = hs[p] ^ val[x] ^ val[y];
int pos = get_next(h, p);
if(pos == -1)
{
flag = false;
ans = min(ans, dp[p] + add);
}
else
dp[pos] = min(dp[pos], dp[p] + add);
}
for(int i = 0; i < os && flag; i++)
for(int j = 0; j < es && flag; j++)
{
int x = o[i];
int y = e[j];
int add = 1;
long long h = hs[p] ^ val[x] ^ val[y];
int pos = get_next(h, p);
if(pos == -1)
{
flag = false;
ans = min(ans, dp[p] + add);
}
else
dp[pos] = min(dp[pos], dp[p] + add);
}
for(int i = 0; i < es && flag; i++)
for(int j = 0; j < i && flag; j++)
{
int x = e[i];
int y = e[j];
int add = 2;
long long h = hs[p] ^ val[x] ^ val[y];
int pos = get_next(h, p);
if(pos == -1)
{
flag = false;
ans = min(ans, dp[p] + add);
}
else
dp[pos] = min(dp[pos], dp[p] + add);
}
}
cout << max_score - ans << endl;
}
}
Good editorial, but for problem C I have a question, If we increase K to a number M. Which is the maximum value that M can achieve auch that there exist a solution that fits in 5 seconds?
"there exist a solution that fits in 5 seconds" is a rather vague requirement imo, since it depends on many factors outside of your own codes (i.e. OS and hardware).
As far as we keep on the $$$\mathcal{O}(nk^2)$$$ as benchmarking, and assuming using my own solution which ran in 0.3s (rounded down for simplicity), we could reach a $$$k$$$ of about $$$\lfloor {10 \times \sqrt{\frac{5}{0.3}}} \rfloor = 40$$$.
Of course 0.3s might not be the fastest $$$\mathcal{O}(nk^2)$$$ solution out there. If benchmarking using other faster ones, resulting $$$k$$$ might be slightly bigger (not too much, since the complexity relates to $$$k$$$ quadratically). Also this estimation is rather rough due to various constant factor not yet addressed in the time complexity.
I think I have another solution for D: 258763428
But, I am not sure why it works :)
helpfull
Why the dip in your graph?
About problem F: How do you handle the case, when the deck becomes empty and we still have duplicate cards on the hand? How do you choose the pair to go with?
This is handled by the fact that the dynamic programming stores the number of pairs we "broke" instead of the number of pairs we made, and it is subtracted from the number of pairs we can make from a sequence of cards in the best case scenario (i. e. if we could pair any two cards without having both of them in hand at the same time). The value in dp increases by $$$1$$$ every time we play a non-paired card such that the remaining number of cards of that type is odd, since it means that the number of pairs we could possibly make with that type of card decreases by $$$1$$$.
So, the pairs that are left in our hand after we've drawn the whole deck are simply not counted as "broken", we don't subtract them from the number of possible pairs we can make.
Mad respect to everyone who went for $$$\mathcal{O}(n^2)$$$ in Problem F
Actually, assume that $$$dp[i]=dp[j]+?$$$ , we can find that $$$j$$$ corresponds to at most one $$$(x,y)$$$ (the kinds we delete). To find all the $$$(x,y)$$$, we may use a queue to simulate the process, thus it runs in $$$O(n^2)$$$.
see my code: 259118010
How is O(N^3) fast enough for problem F, given you have N = 1000 possibly?
Although $$$N \leq 1000$$$, we pick out two cards at a time. So, the "actual" $$$N$$$ is actually 500.
Though, in general, a low-constant $$$\mathcal{O}(N^3)$$$ should be fast enough for $$$N=1000$$$
In problem D, for a fixed set of alice's items, isn't it better for bob to take items' that profits Alice the most ? ( the one with bigger $$$B[i]$$$ — $$$A[i]$$$ )
No, Alice has already paid for these item, Bob can only take k free items and take the rest from Alice. So Bob takes k items with the max b value.
Just want to make sure. The solution basically boils down iterating through all divide points where we will take and also minimizing $$$K$$$ elements from the left side to be given freely to Bob and finding all "profit" element from the right side of the element?
Yes. But you can ignore all items where a[i]>=b[i], as these items will always make Alice lose profit.
If with item i, a[i] >= b[i], i in the item Bob will pay Alice, then profit of item i is b[i]-a[i]<=0, so do not include item i.
If number of items with a[i] < b[i] is less than k, then Alice won't buy anything.
If we already have k items, each with a[i] < b[i] and Bob will get them free, if we need to include item i in the list of free item, then an item j will be removed. We have a[j] < b[j] <= b[i] <= a[i], so a[j] < a[i] and the cost Alice will have to pay will increase.
My solution got WA. Do you mind to see my solution? 258978737
You missed checking result when i+1==k
Oh ya I forgot to consider that. Thank youu!!
Hi,any non DP solution for problem C?
Problem E can be solved using monotonic stack.
We maintain a stack with item is (nexti, seen_values), nexti decreasing. Traverse from left to right.
nexti is the index that if reaching, will create a subarray with no unique elements. seen_values is the set of elements in the subarray.
https://codeforces.net/contest/1969/submission/258961901
Can you expand on it a bit more? seems interesting...
Solution in C++
https://codeforces.net/contest/1969/submission/258986735
Somehow the C++ version gives TLE, even though it's the same as Go version.
There is a similar idea, but instead of using seen_values to check if the element is already encountered, here use previous index to check, and stack item is (start, end)
The time complexity is O(n)
https://codeforces.net/contest/1969/submission/258805932
There is a non-greedy approach for problem E.
Suppose $$$dp_i$$$ is the answer for the prefix with len $$$i$$$ if the last updated element was $$$i$$$. We wan't to do transitions like $$$dp_i = min_{j<i} dp_j + 1$$$ for good $$$j$$$, where $$$j$$$ is the position of previous update. Since we can set an element to some value which isn't in the array, we only need to care about subsegments of interval $$$(j, i)$$$. To check whether all subsegments are unique, for each $$$r$$$ we want to precalculate max $$$l$$$ such that segment $$$[l, r]$$$ is not unique. Let's call this $$$l$$$ $$$bad_r$$$.
To find $$$bad_i$$$ we want to find all unique subarrays. Turns out we can do that. Suppose element $$$i$$$ makes the subarray unique. What can we say about $$$L$$$ and $$$R$$$ (ends of segment)?
$$$prv_i < L \le i$$$, $$$i \le R < nxt_i$$$
Where $$$prv_i$$$ is the previous occurence of $$$a_i$$$ or $$$-1$$$, and $$$nxt_i$$$ is the next occurence of $$$a_i$$$ or $$$n$$$ (in zero-indexation).
So all unique segments are union of rectangles $$$(prv_i + 1, i, i + 1, nxt_i)$$$ (I define rectangles as a quadruple $$$(x1, y1, x2, y2)$$$, rectangle has all points $$$(x, y)$$$ satisfying $$$x1 \le x < x2$$$, $$$y1 \le y < y2$$$). All non-unique segments are out of this union. To find $$$bad_r$$$ we can do scanline with segment tree and for each $$$r$$$ search the right-most $$$0$$$ (or $$$-1$$$ if all values are greater than $$$0$$$).
Now our $$$dp$$$ can be reformulated as $$$dp_i = min_{bad_{i-1} \le j < i}(dp_j) + 1$$$. This can be counted using another segment tree or with monotonous stack and binary search. The answer is either $$$0$$$ when $$$bad_{n-1} = -1$$$ or minimum amongst $$$dp_i$$$ with $$$i \ge bad_{n-1}$$$
can anyone help me provide a clearer explanation for problem C please? How can we get the answer by using min of dp[n]. Updated: I got it now, sorry for bothering
It depends on your dp statements.You must have seen the tutorial $$$dp[i]$$$ means if we considered the first elements and already done $$$j$$$ operations,and the best answer.After considering all n elements ,we get the answer.
Isn't dp[n][k] should be the minimum?
sure,it is.
I solved $$$D$$$ with dp
In question C, if we are able to reach till i + d + 1 using d operations then why aren't we taking the minimum till that index as well?
For me , it's hard to solved the problem C. Also , the tutorial is too short making me difficultly to understand! May be i am beginner to DP.>_<.
In Problem C where the editorial said that the segment of length d+1 can be converted to a minimum using d steps. But what if all of the elements in the segment are equal let's say (2) then their is no need to waste any operations so wouldnt the transitions change. Why is the dp still working ?
Problem F can be changed into another question.There are n points with different colors on a line,which numbered from $$$1$$$ to $$$n$$$.Each time we make a segment whose endpoints have same color. What we are currently requesting is the maximum number of line segments we can make,satisfying that every point between $$$a_{2i}$$$ and $$$a_{2i+1}$$$ is covered no more than $$$k-2$$$ times and every point between $$$a_{2i-1}$$$ and $$$a_{2i}$$$ is covered no more than $$$k-1$$$ times.This is too much like a problem that can be solved with greed or flow.I'm still figuring out the solution.Can somebody teach me how to solve it?
In problem B if I do the operation on index [2,5], making the cost 4 resulting string: 10001 and I do the operation on index [1,4] making the cost 8 now. resuting string:00011. this makes the cost 8 rather than 9, I dont think the answer given is write. My code is giving all other test cases right, but not this case.
You are supposed to put last character to first position not first character to last position.
Transformation of 1000 would be 0100 not 0001.
oh yes, now I see my mistake
I have a doubt in problem C why will a normal greedy solution fail in this case. Please anyone reply to this i'm not able to understand what i am getting wrong or where am i failing. So for each k i am just traversing the whole array and the swap that reduces my some the most i just do that and i do this at most k times. For reference i am attaching my solution here. 261251605
I have the same question, but I have a guess:
For example, consider the array [10, 1, 2, 11]. We can obtain [1, 1, 2, 11] and [10, 1, 2, 2], which, while giving the same total sum, leads to different arrays.
My guess is that for some test cases where this also happens, the total sum changes after more operations on the different arrays with same sum.
Maybe you can try 1 10 11 2, and k = 2. ->1 1 11 2 -> 1 1 1 2 -> 9+10 = 19 ->1 10 2 2 -> 1 1 2 2 -> 9+9 = 18
Wow, it was right under my nose, thank you!
Also, if you wouldn't mind, could you do an example of the dp algorithm with the same array? I'm reading the tutorial but I'm still not getting it
Problem C is very similer to atcoder dp contest problem N.
Edit: No, it is not.XD
please someone explain the solution of problem C in detail . Thank you
Hey, So my solution was also through dp, but a little different from the editorial. Here it is:
$$$dp[i][j]$$$ refers to min sum from $$$a[1..i]$$$ using at most $$$j$$$ operations. Now, I declare a $$$dp$$$ array of size $$$(n+1) \times (k+1)$$$. (Note that I am using 1-based indexing for $$$a$$$)
Initialisation: $$$dp[0][j] = 0 \, \forall j$$$ (since no elements are there) and $$$dp[i][0] = pre[i]$$$, where $$$pre[i] = a_1 + a_2 + \dots a_i$$$ (prefix-sum till $$$a_i$$$) [Obvious, when you can't perform any operations, the ans will be the sum simply]
Transition: This is a little tricky part, but still simple to think. You can have three possibilities:
And that's it! Our final solution looks like:
$$$dp[i][j] = min(case 1,case 2,case 3)$$$
My submission for reference: 265745935 . Hopefully, the solution was easy to understand. If you cannot deduce any of the bracketed stuff, kindly let me know in the comments.
Good work !!
Another Approach for problem B:
we can find the first position of '1' and keep it updating once we encounter a '0' afterwards. and also keep adding substring length to answer. Solution
hope it will be helpful :)
I did not understand the solution for problem B , kindly help me . Thanks