Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
t = int(input())
for i in range(t):
input()
xs = []
ys = []
for j in range(3):
x, y = map(int, input().split())
xs.append(x)
ys.append(y)
print('YES' if len(set(xs)) == 3 or len(set(ys)) == 3 else 'NO')
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
x = a[0]
a = sorted(a[1:])
for y in a:
if y > x:
x += (y - x + 1) // 2
print(x)
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (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;
}
const int N = 143;
int n;
int a[N][N];
int dp[N][N];
bool check(int cnt, int last)
{
for(int i = 0; i < cnt; i++)
{
if(a[i][cnt - 1] == 0) continue;
if(a[i][cnt - 1] == 1 && last > i) return false;
if(a[i][cnt - 1] == 2 && last <= i) return false;
}
return true;
}
int main()
{
cin >> n;
for(int i = 0; i < n; i++)
{
for(int j = i; j < n; j++)
cin >> a[i][j];
}
if(a[0][0] != 2) dp[1][0] = 2;
for(int i = 1; i < n; i++)
for(int j = 0; j < i; j++)
for(int k : vector<int>({j, i}))
if(check(i + 1, k))
dp[i + 1][k] = add(dp[i + 1][k], dp[i][j]);
int ans = 0;
for(int i = 0; i < n; i++)
ans = add(ans, dp[n][i]);
cout << ans << endl;
}
Idea: Neon
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
string s;
cin >> n >> s;
int k = count(s.begin(), s.end(), '1');
for (int x = 1 << k; x <= (1 << n) - (1 << (n - k)) + 1; ++x)
cout << x << ' ';
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
int main() {
int n, m;
scanf("%d%d", &n, &m);
vector<int> c(n);
forn(i, n){
scanf("%d", &c[i]);
--c[i];
}
vector<int> x(m);
forn(i, m) scanf("%d", &x[i]);
vector<long long> g(m);
forn(i, n - 1){
g[c[i]] |= 1ll << c[i + 1];
g[c[i + 1]] |= 1ll << c[i];
}
g[c[0]] |= 1ll << c[0];
g[c[n - 1]] |= 1ll << c[n - 1];
int mid = m / 2;
vector<int> dp(1 << mid, 1e9);
forn(mask, 1 << (m - mid)){
long long chk = 0;
int tot = 0;
forn(i, m - mid){
if ((mask >> i) & 1)
tot += x[i + mid];
else
chk |= g[i + mid];
}
if (((chk >> mid) | mask) != mask)
continue;
chk &= (1ll << mid) - 1;
dp[chk] = min(dp[chk], tot);
}
forn(i, mid) forn(mask, 1 << mid) if (!((mask >> i) & 1)){
dp[mask | (1 << i)] = min(dp[mask | (1 << i)], dp[mask]);
}
int ans = 1e9;
forn(mask, 1 << mid){
long long chk = 0;
int tot = 0;
forn(i, mid){
if ((mask >> i) & 1)
tot += x[i];
else
chk |= g[i];
}
chk &= (1ll << mid) - 1;
if ((chk | mask) != mask)
continue;
ans = min(ans, dp[mask] + tot);
}
printf("%d\n", ans);
return 0;
}
Idea: shnirelman
Tutorial
Tutorial is loading...
Solution (shnirelman)
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
using li = long long;
using ld = long double;
using pii = pair<int, int>;
const int INF = 2e9 + 13;
const li INF64 = 2e18 + 13;
const int M = 998244353;
const int A = 2e5 + 13;
const int N = 2e5 + 13;
const int B = 2000;
const int SQRTA = 500;
const int K = N / B + 113;
int val[N];
vector<int> g[N];
int sz[N];
int gr[N];
int leaf[N], group_root[N];
int par[N];
bool heavy[N];
int tin[N], tout[N], T = 0, mid[N];
int et[N];
int valet[N];
void dfs1(int v, int pr, int depth) {
par[v] = pr;
sz[v] = 1;
int mx = -1;
for(int i = 0; i < g[v].size(); i++) {
int u = g[v][i];
if(u != pr) {
dfs1(u, v, depth + 1);
sz[v] += sz[u];
if(mx == -1 || sz[g[v][mx]] < sz[u])
mx = i;
}
}
if(mx != -1)
swap(g[v][mx], g[v][0]);
}
void dfs2(int v) {
et[T] = v;
tin[v] = T++;
for(int u : g[v]) {
if(u != par[v])
dfs2(u);
}
tout[v] = T;
}
struct Query {
int ind;
int v, u;
int lv, rv, lu, ru;
int b;
Query() {};
};
bool cmp(const Query& a, const Query& b) {
if(a.b != b.b)
return a.b < b.b;
else
return a.lu < b.lu;
}
int cnt[A];
int block_index[A];
int block_mx[A];
int block_cnt_of_cnt[A / SQRTA + 13][A];
inline void insert(int i) {
block_cnt_of_cnt[block_index[valet[i]]][cnt[valet[i]]]--;
cnt[valet[i]]++;
block_cnt_of_cnt[block_index[valet[i]]][cnt[valet[i]]]++;
if(cnt[valet[i]] > block_mx[block_index[valet[i]]])
block_mx[block_index[valet[i]]]++;
}
inline void erase(int i) {
if(cnt[valet[i]] == block_mx[block_index[valet[i]]] && block_cnt_of_cnt[block_index[valet[i]]][cnt[valet[i]]] == 1)
block_mx[block_index[valet[i]]]--;
block_cnt_of_cnt[block_index[valet[i]]][cnt[valet[i]]]--;
cnt[valet[i]]--;
block_cnt_of_cnt[block_index[valet[i]]][cnt[valet[i]]]++;
}
int get_mode() {
int mx = 0;
for(int i = 0; i < A / SQRTA + 1; i++)
mx = max(mx, block_mx[i]);
for(int i = 0; ; i++) {
if(block_mx[i] == mx) {
for(int j = i * SQRTA; ; j++) {
if(cnt[j] == mx)
return j;
}
}
}
}
Query queries[N];
int ans[N];
void solve() {
int n;
cin >> n;
for(int i = 0; i < n; i++)
cin >> val[i];
for(int i = 1; i < n; i++) {
int v, u;
cin >> v >> u;
v--;
u--;
g[v].push_back(u);
g[u].push_back(v);
}
dfs1(0, -1, 0);
vector<pii> ord(n);
for(int i = 0; i < n; i++) {
ord[i] = {sz[i], i};
gr[i] = -1;
}
sort(ord.begin(), ord.end());
for(int i = 0; i < n; i++) {
if(sz[i] >= B)
heavy[i] = true;
}
int cur = 0;
for(int i = 0; i < n; i++) {
int v = ord[i].s;
if(sz[v] < B || gr[v] != -1)
continue;
leaf[cur] = v;
int u = v;
while(gr[u] == -1 && sz[u] - sz[v] < B) {
gr[u] = cur;
group_root[cur] = u;
u = par[u];
}
cur++;
}
dfs2(0);
for(int i = 0; i < n; i++) {
if(sz[i] < B) {
gr[i] = cur + tin[i] / B;
}
}
for(int i = 0; i < n; i++)
valet[i] = val[et[i]];
for(int i = 0; i < A; i++) {
block_index[i] = i / SQRTA;
}
int q;
cin >> q;
for(int i = 0; i < q; i++) {
queries[i].ind = i;
cin >> queries[i].v >> queries[i].u;
queries[i].v--;
queries[i].u--;
queries[i].lv = tin[queries[i].v];
queries[i].rv = tout[queries[i].v];
queries[i].lu = tin[queries[i].u];
queries[i].ru = tout[queries[i].u];
if(queries[i].lv > queries[i].lu) {
swap(queries[i].v, queries[i].u);
swap(queries[i].lv, queries[i].lu);
swap(queries[i].rv, queries[i].ru);
}
queries[i].b = gr[queries[i].v];
}
sort(queries, queries + q, cmp);
int lv = 0, rv = 0, lu = 0, ru = 0;
li fir = 0, sec = 0;
int hs = 0;
for(int i = 0; i < q; i++) {
int qlv = queries[i].lv;
int qrv = queries[i].rv;
int qlu = queries[i].lu;
int qru = queries[i].ru;
fir += abs(lv - qlv) + abs(rv - qrv);
sec += abs(lu - qlu) + abs(ru - qru);
if(queries[i].b < cur) {
while(rv < qrv)
insert(rv++);
while(lv > qlv)
insert(--lv);
while(rv > qrv)
erase(--rv);
while(lv < qlv)
erase(lv++);
} else {
while(rv > lv)
erase(--rv);
lv = qlv;
rv = lv;
while(rv < qrv)
insert(rv++);
}
while(ru < qru)
insert(ru++);
while(lu > qlu)
insert(--lu);
while(ru > qru)
erase(--ru);
while(lu < qlu)
erase(lu++);
ans[queries[i].ind] = get_mode();
}
for(int i = 0; i < q; i++)
cout << ans[i] << endl;
}
mt19937 rnd(1);
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
// freopen("input.txt", "r", stdin);
solve();
}
I have become an Expert thanks to this contest! Great D by the way.
Don't worry , your new colour won't last long :D
Despite getting a lot of downvotes, your prediction was indeed correct.
In problem A, since the first line is empty. I read it as a string and never bothered to use it. It WA'd. This is my submission 185477892 . After the contest, I didn't even bother to read the first line and used the same code as above and it got AC. I am not sure why and could use some help.185647398
cin >> [whatever]
doesn't work as you think. The input data is split into tokens: a token is a sequence of characters. Tokens are separated by whitespaces (incl. normal spaces and newline characters). Doingcin >> [whatever]
reads the next token* and tries to convert it into the type of the variable. Doingcin >> [whatever]
always skips over any spaces and newline characters. Thus, yourcin >> s
reads the first integer into your string, messing up the values. In order to read a full line into a single string (including all spsces, but not the newline character) you need to do the following:*doing
cin >> [char]
only reads the next character, but it still skips whitespaces.I will have time to grow old before the moment when I completely read, understand and solve the problem F... The longest editorial I've ever seen
And that's why we're not there yet. You're blue, I'm green haahha
lol he went on to become orange and u a grey
Hahahah, indeed. Well done Tima3! You did incredible
so u still doing CP or left it
Left it. Haven't practiced much, which you can see on my graph ahaha.
I think the overall complexity of attached solution of E is $$$O(2^{m/2} \cdot m)$$$
problem A-E video Editorial for Chinese:
BiliBili
hi just a request.Please add english captions or if possible please speak in english.
Thanks for such a great video.
but you , my friend , you are the truly hero.
Full Detailed Solution with Explanation of Problem C
Problem A:
It never becomes a rectangle, rather it becomes a quadrilateral.
Please make the editorial more understandable.
Most of solutions and tutorials with "mask" are pretty hard to understand.
This editorial was hard to understand, please make it easier to understand next time
Alas, you are right, and there are too many hard-to-understand editorials on Codeforces. Sometimes I would rather directly learn top contestants' code.
There is an alternative solution for 1767E - Algebra Flash not using meet-in-the-middle, but employing an additional observation. I suspect that it works in $$$O(2^{m/2}*m)$$$ and system tests validate this, but I could use someone's help for a complete analysis.
A general idea is to activate every color in the beginning and deactivate colors one by one — well, actually two for one (at least). Firstly, we look at the lowest unselected color — call it $$$v$$$. Two options — either make it true (Deactivated) or false (Leave as activated).
First case: we make $$$v$$$ true. Then let's look at its neighbors. If neighboring color $$$u$$$ comes before $$$v$$$ $$$(u < v)$$$, this means we already assigned it some color. Otherwise we still didn't decide on color of $$$u$$$ and have to make it false (Because $$$v$$$ and $$$u$$$ cannot be deactivated simultaneously due to the same reasons as described in the editorial).
Second case: we make $$$v$$$ false. There is an important observation to use: If $$$v$$$ is false and all of its neighbors are false too, such color selection cannot be optimal.
If we make $$$v$$$ true (which we can do safely, because all neighbors are false), such selection would be a more optimal one. Hence, current selection is not optimal.
Now, when we set $$$v$$$ to false, at least one of the neighbors must be set to true. So let's select that neighbor and then apply a known procedure for true vertexes (mark its neighbors as false)
Partial proof of complexity.
Since we remove at least 2 vertexes at each state, the maximum depth of recursion is at most $$$m/2$$$. Also, at each state, we have two choices: either to make the lowest color $$$x$$$ true or false. In case of making $$$x$$$ true, we create at most one new state.
In case of making $$$x$$$ false, we select $$$x$$$'s neighbor $$$y$$$, which we mark as true. The number of such neighbors can be up to $$$m$$$, but let's look at each generated state individually. The state with $$$x$$$ false and $$$y$$$ true is a repeated state, which we will also cover when $$$y$$$ will be the lowest unselected color. How many times such states are visited — is something that I need a help with.
If we apply some clever memoization — then the complexity is for sure $$$O(2^{m/2}*m)$$$, but even without memoization the solution passes the System Tests quite confidently.
Note: There is an edge case to look at when marking non-deactivatable colors as false.
Submission: 189735982
In problem F, in the first solution, why do we need to separate queries into light and heavy? Help, please.
can someone share the n^2 approach for problem C.
n^2 solution: Code
can someone write the time complexity of problem [problem:1767D]D?
o(n) + log(n), n is max 18 steps. Its only linear since we need to parse the input string, the actual algorithm part is logarithmic.
It will be exponential, something of the order $$$O(2^n)$$$, that is the reason, in the constraints we have $$$n \le 18$$$ as $$$2^{18} \approx 2 \times 10^5$$$.