Идея: BledDest
Разбор
Tutorial is loading...
Решение (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
string s;
cin >> s;
cout << (count(s.begin(), s.end(), 'N') == 1 ? "NO\n" : "YES\n");
}
}
1620B - Triangles on a Rectangle
Идея: BledDest
Разбор
Tutorial is loading...
Решение (awoo)
for _ in range(int(input())):
w, h = map(int, input().split())
ans = 0
for i in range(4):
a = [int(x) for x in input().split()][1:]
ans = max(ans, (a[-1] - a[0]) * (h if i < 2 else w))
print(ans)
Идея: BledDest
Разбор
Tutorial is loading...
Решение (awoo)
for _ in range(int(input())):
n, k, x = map(int, input().split())
x -= 1
s = input()[::-1]
res = []
i = 0
while i < n:
if s[i] == 'a':
res.append(s[i])
else:
j = i
while j + 1 < n and s[j + 1] == s[i]:
j += 1
cur = (j - i + 1) * k + 1
res.append('b' * (x % cur))
x //= cur
i = j
i += 1
print(''.join(res[::-1]))
Идея: adedalic
Разбор
Tutorial is loading...
Решение (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())
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
return out << "(" << p.x << ", " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
fore(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
int n;
vector<int> a;
inline bool read() {
if(!(cin >> n))
return false;
a.resize(n);
fore (i, 0, n)
cin >> a[i];
return true;
}
bool p(int val, int c1, int c2, int c3) {
fore (cur1, 0, c1 + 1) fore (cur2, 0, c2 + 1) {
if (cur1 + 2 * cur2 > val)
continue;
if ((val - cur1 - 2 * cur2) % 3 != 0)
continue;
if ((val - cur1 - 2 * cur2) / 3 <= c3)
return true;
}
return false;
}
bool possible(int c1, int c2, int c3) {
for (int v : a) {
if (!p(v, c1, c2, c3))
return false;
}
return true;
}
inline void solve() {
int m = *max_element(a.begin(), a.end());
int ans = int(1e9);
const int MAG = 3;
fore (c1, 0, MAG) fore (c2, 0, MAG) {
int c3 = max(0, (m - c1 - 2 * c2 + 2) / 3);
assert(c1 + 2 * c2 + 3 * c3 >= m);
if (possible(c1, c2, c3))
ans = min(ans, c1 + c2 + c3);
}
cout << ans << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
#endif
int t; cin >> t;
while(t--) {
read();
solve();
}
return 0;
}
Идея: Neon
Разбор
Tutorial is loading...
Решение 1 (Neon)
#include <bits/stdc++.h>
using namespace std;
const int N = 500 * 1000 + 13;
int main() {
int q;
scanf("%d", &q);
vector<int> t(q), x(q), y(q);
for (int i = 0; i < q; ++i) {
scanf("%d%d", &t[i], &x[i]);
if (t[i] == 2) scanf("%d", &y[i]);
}
vector<int> p(N);
iota(p.begin(), p.end(), 0);
vector<int> ans;
for (int i = q - 1; i >= 0; --i) {
if (t[i] == 1) {
ans.push_back(p[x[i]]);
} else {
p[x[i]] = p[y[i]];
}
}
reverse(ans.begin(), ans.end());
for (int &x : ans) printf("%d ", x);
}
Решение 2 (Neon)
#include <bits/stdc++.h>
using namespace std;
const int N = 500 * 1000 + 13;
int n, q;
vector<int> pos[N];
int main() {
scanf("%d", &q);
while (q--) {
int t, x, y;
scanf("%d", &t);
if (t == 1) {
scanf("%d", &x);
pos[x].push_back(n++);
} else {
scanf("%d%d", &x, &y);
if (x != y) {
if (pos[x].size() > pos[y].size()) pos[x].swap(pos[y]);
for (int &i : pos[x]) pos[y].push_back(i);
pos[x].clear();
}
}
}
vector<int> ans(n);
for (int x = 0; x < N; ++x)
for (int &i : pos[x])
ans[i] = x;
for (int &x : ans) printf("%d ", x);
}
Разбор
Tutorial is loading...
Решение 1 (Neon)
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); ++i)
const int INF = 1e9;
const int N = 1000 * 1000 + 13;
int n;
int p[N], a[N];
int dp[N][2][2];
pair<int, int> pr[N][2][2];
void solve() {
scanf("%d", &n);
forn(i, n) scanf("%d", &p[i]);
forn(i, n) forn(pos, 2) forn(sg, 2)
dp[i][pos][sg] = INF;
dp[0][0][0] = dp[0][0][1] = -INF;
forn(i, n - 1) forn(pos, 2) forn(sg, 2) if (dp[i][pos][sg] != INF) {
forn(nsg, 2) {
int x = sg ? -p[i] : p[i];
int y = dp[i][pos][sg];
if (pos) swap(x, y);
int z = nsg ? -p[i + 1] : p[i + 1];
if (z > x) {
if (dp[i + 1][0][nsg] > y) {
dp[i + 1][0][nsg] = y;
pr[i + 1][0][nsg] = make_pair(pos, sg);
}
} else if (z > y) {
if (dp[i + 1][1][nsg] > x) {
dp[i + 1][1][nsg] = x;
pr[i + 1][1][nsg] = make_pair(pos, sg);
}
}
}
}
int pos = -1, sg = -1;
forn(j, 2) forn(k, 2) if (dp[n - 1][j][k] != INF)
pos = j, sg = k;
if (pos == -1) {
puts("NO");
return;
}
for (int i = n - 1; i >= 0; i--) {
a[i] = sg ? -p[i] : p[i];
tie(pos, sg) = pr[i][pos][sg];
}
puts("YES");
forn(i, n) printf("%d ", a[i]);
puts("");
}
int main() {
int t;
scanf("%d", &t);
while (t--) solve();
}
Решение 2 (Neon)
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); ++i)
const int INF = 1e9;
const int N = 1000 * 1000 + 13;
int n;
int p[N], a[N];
int dp[N][2], pr[N][2];
void solve() {
scanf("%d", &n);
forn(i, n) scanf("%d", &p[i]);
forn(i, n) forn(j, 2) dp[i][j] = INF;
dp[0][0] = dp[0][1] = -INF;
forn(i, n - 1) forn(j, 2) if (dp[i][j] != INF) {
int x = j ? -p[i] : p[i];
int y = dp[i][j];
if (x < y) swap(x, y);
forn(nj, 2) {
int z = nj ? -p[i + 1] : p[i + 1];
if (z > x) {
if (dp[i + 1][nj] > y) {
dp[i + 1][nj] = y;
pr[i + 1][nj] = j;
}
} else if (z > y) {
if (dp[i + 1][nj] > x) {
dp[i + 1][nj] = x;
pr[i + 1][nj] = j;
}
}
}
}
int j = -1;
forn(i, 2) if (dp[n - 1][i] != INF) j = i;
if (j == -1) {
puts("NO");
return;
}
for (int i = n - 1; i >= 0; i--) {
a[i] = j ? -p[i] : p[i];
j = pr[i][j];
}
puts("YES");
forn(i, n) printf("%d ", a[i]);
puts("");
}
int main() {
int t;
scanf("%d", &t);
while (t--) solve();
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int N = 23;
const int A = 26;
const int S = 20043;
int n;
string inp[N];
char buf[S];
int cnt[N][A];
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 sub(int x, int y)
{
return add(x, -y);
}
int mul(int x, int y)
{
return (x * 1ll * y) % MOD;
}
void flip_all(vector<int>& a)
{
int msk = (1 << n) - 1;
for(int i = 0; i < (1 << (n - 1)); i++)
swap(a[i], a[i ^ msk]);
}
int val[S];
int* where[S];
int cur = 0;
void change(int& x, int y)
{
where[cur] = &x;
val[cur] = x;
x = y;
cur++;
}
void rollback()
{
--cur;
(*where[cur]) = val[cur];
}
void zeta_transform(vector<int>& a)
{
for(int i = 0; i < n; i++)
{
for(int j = 0; j < (1 << n); j++)
if((j & (1 << i)) == 0)
a[j ^ (1 << i)] = add(a[j ^ (1 << i)], a[j]);
}
}
void mobius_transform(vector<int>& a)
{
for(int i = n - 1; i >= 0; i--)
{
for(int j = (1 << n) - 1; j >= 0; j--)
if((j & (1 << i)) != 0)
a[j] = sub(a[j], a[j ^ (1 << i)]);
}
}
int cur_max[A];
vector<int> mask_cnt;
void rec(int depth, int mask)
{
if(depth == n)
{
mask_cnt[mask] = 1;
for(int i = 0; i < A; i++)
mask_cnt[mask] = mul(mask_cnt[mask], cur_max[i] + 1);
}
else
{
int state = cur;
for(int i = 0; i < A; i++)
change(cur_max[i], min(cur_max[i], cnt[depth][i]));
rec(depth + 1, mask + (1 << depth));
while(state != cur) rollback();
rec(depth + 1, mask);
}
}
int main()
{
scanf("%d", &n);
for(int i = 0; i < n; i++)
{
scanf("%s", buf);
inp[i] = buf;
for(auto x : inp[i])
cnt[i][x - 'a']++;
}
for(int i = 0; i < A; i++)
cur_max[i] = S;
mask_cnt.resize(1 << n);
rec(0, 0);
flip_all(mask_cnt);
mobius_transform(mask_cnt);
flip_all(mask_cnt);
int sum = 0;
for(int i = 0; i < (1 << n); i++) sum = add(sum, mask_cnt[i]);
zeta_transform(mask_cnt);
vector<int> res(1 << n);
for(int i = 0; i < (1 << n); i++)
res[i] = sub(sum, mask_cnt[((1 << n) - 1) ^ i]);
long long ans = 0;
for(int i = 0; i < (1 << n); i++)
{
int c = 0, s = 0;
for(int j = 0; j < n; j++)
{
if(i & (1 << j))
{
c++;
s += j + 1;
}
}
ans ^= res[i] * 1ll * c * 1ll * s;
}
//for(int i = 0; i < (1 << n); i++) printf("%d\n", res[i]);
printf("%lld\n", ans);
}
In my opinion, I think that the positions of E and D should have been swapped.
In the problem E-Replace the Number, alternate solution mentions the small to large method. Can anyone explain how it has complexity of O(n log n)? Any resource added would also be helpful.
With small to large method you want to take the smaller set and add it the larger one. When you do this if you had an element in the smaller set, now it is, for sure, in a set with size at least twice the one beforehand. So you can move each element at most log(n) times since the set can't become more than the number of elements.
Here in the task you can keep them in vectors and if needed just swap the vectors after adding the smaller one to the larger.
Hope that explains it.
When you merge a smaller set into a larger set, the size of the generated set is at least twice of the smaller one. So the set-size will exceed N in no more than log(N) merges.
You can have a look at this blog: http://codingwithrajarshi.blogspot.com/2018/06/small-to-large.html
I have upsolved E using map of list as merging list is O(1).
Mike, please please remove cheaters, I am at 1899
your performance graph is pretty good, You will obviously make it to Red soon even if there are cheaters.
Thanks for saying I might be red one day, I don't really care much about cheaters. I am just hoping I get +1 rating point to get CM for the first time and that can happen only when someone above me is removed.
Congrats dude on making it to CM
Thank you :)
I upsolved E using map of list as merging list is O(1) operation.
Can someone please explain why this DSU based solution for E is failing TC 4?
I am using a hashmap and a pointer array to map the representatives to the values and vice-versa; and everything seems to be working fine.
My Submission.
Don't update when x=y in query of 2nd type
Omg, thank you so much.
I was not able to find this bug when testing with smaller sets of numbers because after "merging" indices of a number to itself, I was not performing any more operations on the set...
Can you check why am I getting MLE on my solution Problem E
mine worked https://pastebin.com/VFVg0qB1
In case you are interested in video solutions, Here they are(for A-E)
Amazing content sir as always
In C , are there any constraints on the total number of strings possible ? Will it be always in the INT range ?
We can fill at most K b's, so total number will be K^cnt, where cnt is the number of asterisks. It will easily overflow 9e18
Yes ,I totally I understand this , but have a look at this code once https://codeforces.com/contest/1620/submission/139857428
Getting TLE in Problem E, with this solution. Can somebody tells why because it seems more efficient than one in the solution 2 of tutorials.
https://codeforces.com/contest/1620/submission/139879128
TLE because of how you are processing your 2nd type of querry.
consider 10^5 querries of 2nd type like
2 1 2
2 2 3
2 3 4
....
that is in the end converting all 1 to some large number
if the vector containing index of 1 has 10^5 elements
Do you see where you are going wrong?
10^5 x 10^5 operations there is your TLE
https://codeforces.com/contest/1620/submission/139877833 Can someone explain why this submission gives TL on E? It should be O(n) since double-linked list concatenation is O(1) operation... Thanks.
It is due to this line
val_map[y] = val_map[x];If y has no entry till now you are copying x's list to y which might be O(n).
You can instead do
val_map[y] = move(val_map[x]);https://codeforces.com/contest/1620/submission/139901581
In problem E why my solution is wrong this one.any suggestion or testcase
I think you should handle the case when 2 x y and x = y
I am not able to understand why this case
when 2 x y and x = yhas to be specially handled?what is wrong with updating
xwithparent[x]?it depends on your solution, in my case, it was because :
so I'm deleting the old color although I should keep it. you can check my solutions and compare.
Can someone tell me some similiar problem as E, or some algorithm tag?
In the editorial of D,
I think you meant,
Because, in the given solution code, you are iterating from $$$i = 0$$$ to $$$i \lt 3$$$. And, I have also done the same :)
C problem is really amazing. And the solution is lot more amazing.
I have a different solution to F
following the editorial, there can't exist $$$i<j<k$$$ such that $$$a_{i} > a_{j} > a_{k}$$$. if an array satisfies this condition then the array can be decomposed entirely into two or less increasing subsequences.
Proof: consider doing a pass through the array and greedily picking out an increasing subsequence. Do two such greedy passes through the array let $$$S$$$ be the sequence chosen by the first pass and $$$T$$$ the sequence chosen by second pass. Assume there exist an index $$$k$$$ that isn't chosen by either sequences pick such smallest $$$k$$$, indexes $$$1$$$ to $$$k-1$$$ can't be all in $$$S$$$ otherwise $$$k$$$ would be in $$$T$$$, this implies there exist an index $$$i$$$ with $$$i+1$$$ < $$$k$$$ such that $$$i$$$ is in $$$S$$$ and $$$i+1$$$ is in $$$T$$$. Pick $$$j$$$ such that all indexes from $$$i$$$ to $$$j$$$ are in $$$T$$$ but $$$j+1$$$ is not. then $$$a_{i} > a_{j}$$$ otherwise some index between $$$i+1$$$ and $$$j$$$ would had been chosen by $$$S$$$ and $$$a_{k} > a_{j}$$$ otherwise $$$k$$$ would have been chosen by $$$T$$$ so we get $$$a_{i} > a_{j} > a_{k}$$$ which is impossible. For the other direction if there exist a length 3 decreasing subsequence then all three must be in different increasing subsequences.
Great!now we can construct a dp that tries to builds two or less increasing subsequences. Let $$$dp_{0 / 1,i}$$$ be the minimum possible value of the end of the increasing subsequence that $$$i$$$ is not part of(consider the end of the subsequence to be $$$-\infty$$$ if its empty) , $$$0/1$$$ denotes whether we choose to flip the sign of $$$p_{i}$$$, the transitions are deciding whether or not to stick $$$p_{i}$$$ into the same subsequence as $$$p_{i-1}$$$ ,the answer is yes if either $$$dp_{0,n}$$$ or $$$dp_{1,n}$$$ $$$\neq\infty$$$
my submission :140109080 (in hindsight the dp I described should be equivalent to the editorial dp, but I think this interpretation is cleaner and easier to understand)
It seems you proved Dilworth Theorem.
please can someone tell me why is this code failing for C ?? https://codeforces.com/contest/1620/submission/140169385 I have lost my mind at debugging this for 3 hours at this point,also is there a way to see the full testcase in this website ?
Nice problems
In problem C, for this test case
TC: 1 8 3 18 a***a*The output of the editorial code is abbabbb i.e; (2+1) * (3+1) => 12th lexicographically smaller but I asked for 18th right. How is this correct?
Your test has n=8 and the string is length 6 — something is wrong.
However, that's not how you obtain the number from its digits. Consider base 10. If you have a number, consisting of digits 1, 2 and 3, then this number is 1 * 10 * 10 + 2 * 10 + 3. Same here. You have a number, consisting of digits 2 and 3 (the lengths of b segments in the answer). Thus, the number is 2 * (3 + 1) + 3 = 11. So this is the 12th string but if n was equal to 6 in your test.
If the string instead was *a***a* and the answer was babbabbb, then the number would be retrieved as 1 * (3 + 3 + 3 + 1) * (3 + 1) + 2 * (3 + 1) + 3. So you have to multiply each digit by the bases of lower digits and add up the results.
I really dont understand the problem D. Why there is no need to take more than 3 coins 1 and more than 3 coins 2? In my opinion, there is no need to take more than one coin 1 (i.e. one coin 1 at most) because if any ai required two coins 1, two coin 1 could be replaced by one coin 2; and ,similarly, there is no need to take more than two coins 2. This really confuses me. Could anyone explain it? Thanks in advance!
Your approach is correct. My solution works similar to your idea. Submission
I solved E using Linked list in O(n) https://codeforces.com/contest/1620/submission/141979731
Here is the casework solution for D https://codeforces.com/contest/1620/submission/142005976
Does anyone know why this solution to E is getting an MLE on testcase 4? 143353188
same happening with me 143433175
Edit: I see why because of this link: https://codeforces.com/blog/entry/64625 check it. Problem G: Some contestant solved this problem using inclusion-exclusion, let cnt be the number of strings that are subsequence of the strings given by the mask, they do +cnt when the amount of bits is odd and -cnt when is even. Then, they do dp[mask] = cnt and apply SOS DP at the end. SOS Dp is clear, but what is the argument of that inclusion-exclusion when adding and decreasing depending on the bits?
Sorry for my English, thanks in advance.
Haha, for C I got the solution but instead of going from the least significant digit to the highest, I went the other way.
This lead to some quick Integer overflow D:
What is the simplest solution, newbies like me follow ? we take one more coin and dont make fuss of it.