1574A - Правильные скобочные последовательности
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
t = int(input())
for i in range(t):
n = int(input())
for j in range(n):
print("()" * j + "(" * (n - j) + ")" * (n - j))
Идея: BledDest
Разбор
Tutorial is loading...
Решение (awoo)
for _ in range(int(input())):
a, b, c, m = map(int, input().split())
a, b, c = sorted([a, b, c])
print("YES" if c - (a + b + 1) <= m <= a + b + c - 3 else "NO")
Идея: BledDest
Разбор
Tutorial is loading...
Решение (Neon)
#include <bits/stdc++.h>
using namespace std;
using li = long long;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
vector<li> a(n);
for (auto &x : a) cin >> x;
sort(a.begin(), a.end());
li sum = accumulate(a.begin(), a.end(), 0LL);
int m;
cin >> m;
while (m--) {
li x, y;
cin >> x >> y;
int i = lower_bound(a.begin(), a.end(), x) - a.begin();
li ans = 2e18;
if (i > 0) ans = min(ans, (x - a[i - 1]) + max(0LL, y - sum + a[i - 1]));
if (i < n) ans = min(ans, max(0LL, y - sum + a[i]));
cout << ans << '\n';
}
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
int n;
vector<vector<int>> a;
int m;
vector<vector<int>> b;
int main() {
scanf("%d", &n);
a.resize(n);
forn(i, n){
int c;
scanf("%d", &c);
a[i].resize(c);
forn(j, c) scanf("%d", &a[i][j]);
}
scanf("%d", &m);
b.resize(m);
forn(i, m){
b[i].resize(n);
forn(j, n){
scanf("%d", &b[i][j]);
--b[i][j];
}
}
sort(b.begin(), b.end());
vector<int> ult(n);
forn(i, n) ult[i] = int(a[i].size()) - 1;
if (!binary_search(b.begin(), b.end(), ult)){
forn(i, n) printf("%d ", ult[i] + 1);
puts("");
return 0;
}
int mx = 0;
vector<int> ans(n, -1);
forn(i, m){
vector<int> tmp = b[i];
int sum = 0;
forn(j, n) sum += a[j][tmp[j]];
forn(j, n) if (tmp[j] != 0){
--tmp[j];
if (!binary_search(b.begin(), b.end(), tmp) && sum - a[j][tmp[j] + 1] + a[j][tmp[j]] > mx){
mx = sum - a[j][tmp[j] + 1] + a[j][tmp[j]];
ans = tmp;
}
++tmp[j];
}
}
forn(i, n){
printf("%d ", ans[i] + 1);
}
puts("");
}
Идея: Roms
Разбор
Tutorial is loading...
Решение (Roms)
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
const int N = 1'000'009;
int sum (int a, int b) {
int res = a + b;
if (res < 0) res += MOD;
if (res >= MOD) res -= MOD;
return res;
}
int n, m, k;
map <pair <int, int>, char> c;
int cntr[N][2], cntc[N][2];
int cntx[2];
set <int> badr, badc;
set<int> ur, uc;
int p2[N];
void upd2(int pos, int col, int add, int cnt[N][2], set <int> &bad, set<int> &u) {
cnt[pos][col] += add;
assert(cnt[pos][col] >= 0);
if (cnt[pos][0] > 0 && cnt[pos][1] > 0){
if (!bad.count(pos))
bad.insert(pos);
} else {
if (bad.count(pos))
bad.erase(pos);
}
if (cnt[pos][0] > 0 || cnt[pos][1] > 0){
if (!u.count(pos))
u.insert(pos);
} else {
if (u.count(pos))
u.erase(pos);
}
}
void upd(int x, int y, int t) {
int col = (x & 1) ^ (y & 1);
if (c.count({x, y})) {
int ncol = col ^ c[{x, y}];
--cntx[ncol];
upd2(x, ncol, -1, cntr, badr, ur);
upd2(y, ncol, -1, cntc, badc, uc);
c.erase({x, y});
}
if (t == -1)
return;
int ncol = col ^ t;
++cntx[ncol];
upd2(x, ncol, 1, cntr, badr, ur);
upd2(y, ncol, 1, cntc, badc, uc);
c[{x, y}] = t;
}
int main(){
p2[0] = 1;
for (int i = 1; i < N; ++i)
p2[i] = sum(p2[i - 1], p2[i - 1]);
scanf("%d%d%d", &n, &m, &k);
for (int i = 0; i < k; ++i) {
int x, y, t;
scanf("%d %d %d", &x, &y, &t);
--x, --y;
upd(x, y, t);
int res = 0;
if(badr.size() > 0 && badc.size() > 0) {
res = 0;
} else if (badr.size() > 0) {
assert(m - uc.size() >= 0);
res = p2[m - uc.size()];
} else if (badc.size() > 0) {
assert(n - ur.size() >= 0);
res = p2[n - ur.size()];
} else {
if (ur.size() == 0 && uc.size() == 0)
res = sum(sum(p2[n], p2[m]), -2);
else {
assert(m - uc.size() >= 0);
res = sum(res, p2[m - uc.size()]);
assert(n - ur.size() >= 0);
res = sum(res, p2[n - ur.size()]);
if (cntx[0] == 0 || cntx[1] == 0) {
assert(cntx[0] != 0 || cntx[1] != 0);
res = sum(res, -1);
}
}
}
printf("%d\n", res);
}
return 0;
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int add(int x, int y)
{
x += y;
while(x >= MOD) x -= MOD;
while(x < 0) x += MOD;
return x;
}
int mul(int x, int y)
{
return (x * 1ll * y) % MOD;
}
int main()
{
int n, m, k;
scanf("%d %d %d", &n, &m, &k);
vector<vector<int>> A(n);
vector<int> bad_num(k);
for(int i = 0; i < n; i++)
{
int c;
scanf("%d", &c);
A[i].resize(c);
for(int j = 0; j < c; j++)
{
scanf("%d", &A[i][j]);
A[i][j]--;
}
}
for(int i = 0; i < n; i++)
{
if(set<int>(A[i].begin(), A[i].end()).size() != A[i].size())
{
for(auto x : A[i])
bad_num[x] = 1;
}
}
vector<vector<int>> nxt(k);
vector<vector<int>> prv(k);
for(int i = 0; i < n; i++)
for(int j = 0; j + 1 < A[i].size(); j++)
{
nxt[A[i][j]].push_back(A[i][j + 1]);
prv[A[i][j + 1]].push_back(A[i][j]);
}
for(int i = 0; i < k; i++)
{
sort(nxt[i].begin(), nxt[i].end());
sort(prv[i].begin(), prv[i].end());
nxt[i].erase(unique(nxt[i].begin(), nxt[i].end()), nxt[i].end());
prv[i].erase(unique(prv[i].begin(), prv[i].end()), prv[i].end());
}
vector<int> used(k, 0);
vector<int> cnt(k + 1, 0);
for(int i = 0; i < k; i++)
{
if(used[i]) continue;
queue<int> q;
vector<int> comp;
q.push(i);
used[i] = 1;
while(!q.empty())
{
int z = q.front();
q.pop();
comp.push_back(z);
for(auto x : nxt[z])
if(!used[x])
{
used[x] = 1;
q.push(x);
}
for(auto x : prv[z])
if(!used[x])
{
used[x] = 1;
q.push(x);
}
}
bool bad = false;
int cnt_beg = 0;
for(auto x : comp)
{
if(prv[x].empty())
cnt_beg++;
if(prv[x].size() > 1 || nxt[x].size() > 1 || bad_num[x])
bad = true;
}
bad |= (cnt_beg == 0);
if(!bad)
cnt[comp.size()]++;
}
vector<int> nonzero;
for(int i = 1; i <= k; i++)
if(cnt[i] > 0)
nonzero.push_back(i);
vector<int> dp(m + 1, 0);
dp[0] = 1;
for(int i = 1; i <= m; i++)
for(auto x : nonzero)
if(x <= i)
dp[i] = add(dp[i], mul(cnt[x], dp[i - x]));
printf("%d\n", dp[m]);
return 0;
}
Thanks :)
nice editorial, love the problems, appreciate it
In problem E, we only have to keep track of same-colour cells with an even number of cells between them?
What about differently coloured cells with an odd number of cells between them? Doesn't that force a strip of width two as well?
Same colour is just a special case like adjacent cells, mentioned to arrive to the checkerboard intuition which works both for same colour and opposite colour cases without distinguishing them.
@maxplus can you explain Problem E. I am new to CP. Like for input 2 2 7 1 1 1 1 2 1 2 1 1 1 1 0 1 2 -1 2 1 -1 1 1 -1
o/p: 3 1 0 1 2 3 6 why 1 1 1 gives 3 as o/p . Initially the matrix is empty so there are 2 ways to fill it, either 0 or 1. then the answer should be 2 right. Similarly for 2 1 -1 whey o/p is 3. 2,1 wasn't filled yet, so it can filled in 2 ways with 0 or 1.
When the $$$2 \times 2$$$ matrix is empty, there are actually $$$6$$$ ways to fill it such that every square will add to $$$2$$$. Here are the options:
So when we set the cell with coordinates $$$(1, 1)$$$ we get only first $$$3$$$ options out of the above.
I guess
* The row and columns containing the cells of same color with even number of cells between them;can be confusing, so you're right, it's lines containing cells that correspond to both (contradicting) checkerboard line colourings that should be tracked.Thanks!
OK, I implemented my own version and I think the code is a bit more self-explanatory. If anyone has trouble understanding Roms' implementation (as I did), then maybe looking at mine (129556708) will help.
.
Problem E. What is cntx[] in Roms's solution and why are we (--res) only if it [0,1] or [1,0]. Shouldn't we always (--res) because same starting position shared between p2[n-ur] and p2[m-uc]?
cntx to the whole board as cntr to a row. If there is at least one strip, there are no colourings alternating nicely both vertically and horizontally so none are subtracted, and if no cells are coloured then there are two "shared" colourings.
Thank you. Got it: cntr and cntc keep parity info for each col and row. While cntx keep parity for all board — how many of them correspond to their (virtual) color and how many doesn't. But what information does it provide us — why should we (--res) in case all {correspond} or all {notcorrespond}? It tells us if there can be shared state in the start — the position from which we can shift either vertical lines or horizontal. If there points in both {correspond} and {notcorrespond} positions — there cannot be such common starting position.
Is there a way of solving problem D with a trie?
Yes, I solved D with Trie and DP (unfortunately I couldn't complete it during the contest).
Here is the code
The idea is put all the banned set into a trie. Then iterate through every possible prefixes. For each prefix, we will find the maximum possible suffix so that they will not form a banned set.
For example we have a prefix of length $$$i$$$, there are 6 items for slot $$$i + 1$$$, current node has 3 children numbered $$$3$$$, $$$5$$$, $$$6$$$. So we may choose $$$4th$$$ item for slot $$$i + 1$$$ and choose whatever we want from slot $$$i + 2$$$
The idea is simple but one should be careful while implement
As far as I can tell, I think I did it using a traverse of a trie structure without the structure itself. Take a look at my solution if you want to.
129399828
you can check my implementation
I saw everyone using PriorityQueue for D, can anyone explain that approach.
People used a funky priority_queue based Dijkstra implementation! A very clever approach in my opinion.
Each vertex is a build and each build is a vertex. However, these vertices aren't stored anywhere in memory but rather, they are procedurally generated. Two vertices (builds) are joined by an edge if and only if you get one of the builds by degrading exactly one item in the other build.
Then, just implement a Dijkstra on these builds and remember to skip the neighbours of a vertex if the vertex is not banned, since the neighbours (degraded builds) can only be worse, as noted in the editorial.
The idea is basically to store the build in the priority queue, and we use custom comparator so that builds in PQ are sorted according to their total strength. We add the strongest build first to the PQ (in this case, the last item in each slot). When PQ is not empty, check if its top is not banned, if so then we get the answer. Otherwise we iteratively swap an item in some slot for the one that is the previous one by power and add to PQ.
Got it... very clean.
can someone explain me the second approch giving in editorial for problem d
In D part,i did simple brute force approach with some sort of memorization. But to my extreme surprise the code got accepted.
129377465
By the way one of the best contest for me. This contest boosted my rating to a great extent.
lol its giving TLE for me though. My submission : https://mirror.codeforces.com/contest/1574/submission/129585401. Update : yeah i got it why im getting TLE
What was the reason for TLE in your case?
for (; max[ind]>=0; --max[ind]) { solve(ind+1, max, pos, set); } this loop makes the worst case complexity to O(10^(5n)).
I'm also getting TLE #6, but I haven't found the issue. Here's my code
Oh, sorry man, I cant understand the operations which u have made since I dont know Java that much!!
great short approach for D
Can somebody please explain why we do
and
in E? Thanks in advance.
I do not understand what the variable names mean exactly but based on what I've written in my solution, the first bit of code should be the embodiment of the following train of thought:
The second bit of code I couldn't decipher, but it's likely something similar.
ur == used in rows; uc == used in columns. It keeps indexes of rows and columns that already used — ones that have 1's and 0's written in one of their cell.
Now every possible permutation can be achieved in one of two ways: either by left-right shift/move of horizontal lines or by up-down shift/move of vertical line. And every shift is creating doubled-lines in that direction — except starting position end ending. They are identical (if we consider starting position — a permutation that looks like a chessboard, and ending position — 2^n or 2^m positions, when all rows or all columns are shifted (inverted chessboard)). This means that every vertical shift creates position unachievable by horizontal shift and vice versa. Except starting and ending positions — if we shift non vert (or all vert) — thay will be the same like if we would shift non (or all) horizontal. If both of ur and uc them is empty — we haven't written any numbers — both starting and ending positions are achievable, so we should substruct 2. If there at least one cell with written 1 or 0 — we wouldn't have same starting and ending position. We could maximum have only one of those 2 positions — corresponding to written number and its cell.
cntx is variable that keeps count of <black & white> 'parity'. If you'll imagine an m*n chess board with black square in upper left corner (that is {1,1} coordinate), than you can say that cntx[0] is counting how many 0s you placed on black cell and 1s on whites. cntx[1] is counting how many 0s you placed on white and 1s on black. If there some 1s (or 0s) on both black and whites — there cannot be same starting and ending position. We should not decrease result by on. But if all 1's are on same color and all 0s on other — there could be match for one position — this position is both contained in sum(res, p2[m — uc.size()]) and sum(res, p2[n — ur.size()]), so we should substruct it.
Sorry for asking noob question. I still don't understand why the total permutation is 2^n+2^m-2 (like the way to count up to a total of 2^n+2^m, then subtract 2 cases that is identical). Could you please explain in more detail with example.
Now every possible permutation can be achieved in one of two ways: either by left-right shift/move of horizontal lines or by up-down shift/move of vertical line. And every shift is creating doubled-lines in that direction
Thank you.
I don't know what to add. If you imagine a chess board of m*n — any permutation is achievable either by moving some horizontal "zebra-lines" 1 square left (or right — it doesn't matter, they are indistinguishable) OR by moving some vertical "zebra-lines" 1 square up (or down — doesn't matter). There 2^n variants of horizontal shifts — each line either shifted or not. And 2^m verticals — same logic.
If you observe 2^n horizontal shifting — there 1 "starting" position when none is shifted, and one "ending" position — when all shifted and chess board becomes inverted — they correspond to "starting" and "ending" position in 2^m vertical shifts. So those 2 should be substructed.
Case with cntx and -1 is much more interesting :)
Problem D please help! Can someone explain me this statement, "The optimal answer can be one of only two types. Either it contains the last item of each slot. Or it's some banned build with one item swapped with the previous one.
I couldn't understand the 2nd part how the answer can be part of banned build with one swapped with previous one ?? Thanks in advance
Suppose (b1,b2,b3,...bs) is a banned build.Then one of our possible candidate for the best possible build is (b1,b2,...bi-1,...bs), given bi>1.This build is adjacent to one of our banned build so if not banned too will be a potential candidate.
I actually used $$$BFS$$$ to solve problem $$$D$$$. This might not be the fastest solution to implement, but I think it's easy to understand. Here's my idea.
The state of the $$$BFS$$$ is the array $$$b$$$, which is the index of items chosen on each slot. The value of the state is the sum of the chosen items. We start with all index maxed out for each slot and manually calculate the sum of all the last index as the value. Every time we transition to another state, we decrease one of the $$$b[i]$$$ by $$$1$$$, iterating $$$i$$$ from $$$1$$$ to $$$n$$$. Thus, the value would only be affected by one of the slot. To maintain the value, we need to remove the previous value and add the current value, i.e. the value would decrease by $$$a[i][b[i]]-a[i][b[i]-1]$$$ ($$$b[i]$$$ here is before we decrease by $$$1$$$). By using $$$BFS$$$, we will get the states in descending order without skipping any states. We should use max heap for the $$$BFS$$$ because we prioritize the higher sum. We would stop when the current state is not banned and output it as the answer.
Complexity Analysis: Since we would directly stop when it is not banned, the number of states visited would only be $$$O(M)$$$ at most. Since we use a priority queue and assuming we check a visited state using set/map, the complexity would be $$$O(N^2MlogNM)$$$.
My code: https://mirror.codeforces.com/contest/1574/submission/129387703 (Note that I used a slightly different value definition, which is the difference of the current sum with the maximum sum, but the main idea is still the same)
Edit: I miscalculated the complexity. Big thanks to maxplus for pointing this out.
Thank you so much, I was having the same approach but I was struggling very much implementing , you makes it looks so simple
Glad to help!
Sorry just wanna ask, I'm wondering why "Glad to help!" got so many downvotes. Is it insulting or negative in any way?
Isn't it $$$O(N^2 M log N M)$$$? Although at most $$$M + 1$$$ states are extracted from priority queue, for each of them $$$O(N)$$$ children are processed in $$$O(N log N M)$$$ each.
I see, my bad I think you're right, sorry I will fix that.
I am thinking perhaps one could improve this solution's complexity by using hashing perhaps? Although in this problem, the N is small so it still passes the time limit.
With hashing we'll process each child in $$$O(N)$$$ since worst case we need to create each of them, so $$$O(N^2M + NMlogNM)$$$ (in your solution you'll need to provide pq with a custom comparator so that it can ignore state). $$$N^2M$$$ is hard to shake off because it's also the space complexity independent of lookup algorithm. Instead of hashing we could visit children in such a way that each gets exactly one parent — we can stop generating children after we encounter the first not maxed slot, same complexity.
If we use hashing, replace priority queue with queue, update best answer instead of terminating on the first not banned state and skip states whose children can't improve the answer, $$$O(N^2M)$$$.
If we update hash in $$$O(1)$$$, update current best answer before placing a child into the queue and skip useless children (that aren't better than current best answer), we get $$$O(NM)$$$ but it becomes hard not to notice that only banned states are placed into the queue and we don't need queue at all.
One also has to be careful with updating the best state if he wants to avoid $$$N^2$$$ (in the solution from the editorial too): if we assign it each time it gets improved, it can be up to $$$NM$$$ updates of length-N array.
Nice! Thanks for the insight. I learn a lot even when my code have already got Accepted.
Will anyone help me in upsolving C problem. I find that the editorial is giving TLE. Please help me
You may notice that test#5 has n = 2*10e5 took 1,7 secs. Test #6 has n = 2*10^5 size too (thought we don't know how big is m in both), but we can see that "a" now is not a bunch of 1s and 2s {1 2 1 2 1 2 1 2 ...} but big numbers like 873579811631 — which means they will took your algorithm longer to digest.
Take a look at "fast input output c++" topic. Google it.
And be sure to take a look at this.
Even though I have used binary search to find the heroes in question 1574C — Slay the Dragon it is giving TLE. Pls can someone check why is it giving so? my code is : 129554543
Your input/output is too slow. This is caused by using iostream (cin/cout) with stdio (printf/scanf) synchronisation. Add the following lines to boost the speed considerably.
Beware, however, that this makes it dangerous to use cin/cout alongside printf/scanf.
I submitted your code with these two lines and it works within the time limit (129564251), albeit still a bit slow.
Thanks a lot for helping me!
I solved C with ternary search
Hey, can someone please explain Geothermal's approach to question D: https://mirror.codeforces.com/contest/1574/submission/129399246
It runs in approx 400 MS and my pq method is running in ~2900 MS: https://mirror.codeforces.com/contest/1574/submission/129568774
A banned build is hashed into a pair in Geothermal's code. Your code just push the whole build into the heap, obviously it's much slower.
https://mirror.codeforces.com/submissions/Ashishgup# see this, he simply uses set
Yes, but he is not moving them through PQ.
What is impressive — is his strange "recurse" function with quick return shortcuts. And strange line < ans &= (i + 1 == c[idx]); >
yes :'), did you get his approach?
Yes, he is doing kind-of-dfs until he finds allowed build where all except current node are ones. Than he goes one node up and trying do the same. He is looking into same node that stupid-bfs does, but in different order. Thought bfs has chance of early exit, so it might not visit every blocked build, and this approach does not.
Thanks for the problems. Regarding problem C: how does the last paragraph explain that achievable m values form a range? Could someone clarify? I am thinking of different proof: Consider a string of form C...CB...BA...A that has maximum possible value of m (as in editorial A <= B <= C). Then take A or B and put it between some 2 letters C. This decreases number of equal adjacent pairs by 2. If one needs to decrease number of pairs by odd number, just put the A or B at the beginning of the sequence. It will decrease number of adjacent pairs by one.
someone please explain graphical approach of D.
In B,
"Now build the string for m=0"How to prove that we can always build for m = 0?
This means we have to try to build the string with no repetition, for ex if we are given input as 5A 2B 1C and we try to build the string for m = 0. the string should look like this A__A__A__A__A as you can see we have 4 empty spaces but not enough B's and C's to make a string with no same adjacent letters.
Using banned builds to get good build is crazy idea[problem:D]
I have a different solution for D.
It's based on the fact that if you have two arrays a and b of lengths n1 and n2, you can build the largest m+1 sum pairs (out of n1*n2 pairs) using binary search. You can do this sequentially for every array or use divide and conquer to find all largest m+1 possible builds. One of them must be the answer as only m builds are banned.
Here is the implementation.
Problem D. I have implemented the solution in the editorial, however, I'm getting TLE #6. Can anyone please take a look at my solution and figure out the reason for TLE? Thank you.
You never update your visited set
OMG! So silly mistake. Thanks!! Giving a long break in competitive programming has shown itself.
How can we solve problem F using FFT?
If someone found the editorial solution of E trickier to understand, probably this might help.
Convention:
Observations:
O1: A valid grid consists of either
O2: As we can see we can segregate the answer into two-part,
O3: Partially filled grid.
Code
C1 Mark columns that are already filled
C2 Similar to C1, mark rows that are filled
See implementation here: 130091893
(Solution was inspired by tourist's submission: 129358674)
Thank you so much!
For the tutorial of problem E, how to understand "If there are two cells of same color in the same row with even number of cells between them then there is the vertical strip (because there are always two adjacent cells with same color between them)?" Can someone help me with an example？Thanks.
In my opinion, there is obviously a counterexample: 1 0 0 1 0 1 1 0 There are no vertical strips?
On problem C:
Why we should only consider those 2 cases? Any proof on this?
For the second case maximum $$$a$$$? One way might be to look at the two possible cases for $$$a<x$$$, $$$s-a\ge y$$$ and $$$s-a<y$$$ and the costs for each case, and costs against one another.