Idea: Roms

**Tutorial**

Tutorial is loading...

**Solution (Roms)**

```
for t in range(int(input())):
n = input()
l = filter(lambda x : x <= 2048, map(int, input().split()) )
print('YES' if sum(l) >= 2048 else 'NO')
```

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (PikMike)**

```
n = int(input())
for i in range(n):
print(''.join(['W' if (i + j) % 2 == 0 else 'B' for j in range(n)]))
```

Idea: Roms

**Tutorial**

Tutorial is loading...

**Solution 1 (BledDest)**

```
t = int(input())
for i in range(t):
c, m, x = map(int, input().split())
d = max(c, m) - min(c, m)
x += d
if(c > m):
c -= d
else:
m -= d
ans = min(c, m, x)
c -= ans
m -= ans
x -= ans
ans += (c + m) // 3
print(ans)
```

**Solution 2 (PikMike)**

```
#include <bits/stdc++.h>
using namespace std;
int main(){
int q;
cin >> q;
for (int i = 0; i < q; ++i){
int c, m, x;
cin >> c >> m >> x;
int l = 0, r = min(c, m);
int ans = 0;
while (l <= r){
int mid = (l + r) / 2;
if (c + m + x - 2 * mid >= mid){
l = mid + 1;
ans = mid;
}
else{
r = mid - 1;
}
}
cout << ans << "\n";
}
}
```

1221D - Make The Fence Great Again

Idea: Roms

**Tutorial**

Tutorial is loading...

**Solution (Roms)**

```
#include <bits/stdc++.h>
using namespace std;
const int N = int(3e5) + 99;
const long long INF64 = (long long)(1e18) + 100;
int t;
int n;
int a[N];
int b[N];
long long dp[3][N];
long long calc(int add, int pos){
long long &res = dp[add][pos];
if(res != -1) return res;
res = INF64;
if(pos == n) return res = 0;
for(long long x = 0; x <= 2; ++x)
if(pos == 0 || a[pos] + x != a[pos - 1] + add)
res = min(res, calc(x, pos + 1) + x * b[pos]);
return res;
}
int main() {
scanf("%d", &t);
for(int tc = 0; tc < t; ++tc){
scanf("%d", &n);
for(int i = 0; i < n; ++i){
scanf("%d", a + i);
scanf("%d", b + i);
}
for(int i = 0; i <= n; ++i)
dp[0][i] = dp[1][i] = dp[2][i] = -1;
printf("%lld\n", calc(0, 0));
}
return 0;
}
```

Idea: Roms

**Tutorial**

Tutorial is loading...

**Solution (Roms)**

```
#include <bits/stdc++.h>
using namespace std;
const int N = int(2e5) + 99;
int t;
int a, b;
string s;
int main() {
cin >> t;
for(int tc = 0; tc < t; ++tc){
cin >> a >> b >> s;
vector <int> v;
int l = 0;
while(l < s.size()){
if(s[l] == 'X'){
++l;
continue;
}
int r = l + 1;
while(r < s.size() && s[r] == '.') ++r;
v.push_back(r - l);
l = r;
}
bool ok = true;
int id = -1;
int cnt = 0;
for(int i = 0; i < v.size(); ++i){
if(b <= v[i] && v[i] < a) ok = false;
if(b + b <= v[i]){
if(id == -1) id = i;
else ok = false;
}
if(a <= v[i] && v[i] < b + b) ++cnt;
}
if(!ok){
cout << "NO" << endl;
continue;
}
if(id == -1){
if(cnt & 1) cout << "YES" << endl;
else cout << "NO" << endl;
continue;
}
ok = false;
int sz = v[id];
assert(sz >= a);
for(int rem1 = 0; sz - a - rem1 >= 0; ++rem1){
int rem2 = sz - a - rem1;
int ncnt = cnt;
if((rem1 >= b + b) || (b <= rem1 && rem1 < a)) continue;
if((rem2 >= b + b) || (b <= rem2 && rem2 < a)) continue;
if(rem1 >= a) ++ncnt;
if(rem2 >= a) ++ncnt;
if(ncnt % 2 == 0) ok = true;
}
if(ok) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}
```

Idea: Ne0n25

**Tutorial**

Tutorial is loading...

**Solution (Ne0n25)**

```
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define sz(a) int((a).size())
#define forn(i, n) for (int i = 0; i < int(n); ++i)
typedef long long li;
typedef pair<int, int> pt;
const int N = 1000 * 1000 + 13;
int n;
pair<pt, int> a[N];
vector<int> vals;
vector<pt> ev[N];
pair<li, int> t[4 * N];
li add[4 * N];
void build(int v, int l, int r) {
if (l == r) {
t[v] = mp(-vals[l], l);
add[v] = 0;
return;
}
int m = (l + r) >> 1;
build(v * 2 + 1, l, m);
build(v * 2 + 2, m + 1, r);
t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
}
void push(int v, int l, int r) {
if (add[v] == 0) return;
t[v].x += add[v];
if (l != r) {
add[v * 2 + 1] += add[v];
add[v * 2 + 2] += add[v];
}
add[v] = 0;
}
void upd(int v, int l, int r, int L, int R, int val) {
push(v, l, r);
if (L > R) return;
if (l == L && r == R) {
add[v] += val;
push(v, l, r);
return;
}
int m = (l + r) >> 1;
upd(v * 2 + 1, l, m, L, min(m, R), val);
upd(v * 2 + 2, m + 1, r, max(m + 1, L), R, val);
t[v] = max(t[v * 2 + 1], t[v * 2 + 2]);
}
pair<li, int> get(int v, int l, int r, int L, int R) {
push(v, l, r);
if (L > R) return mp(-li(1e18), 0);
if (l == L && r == R) return t[v];
int m = (l + r) >> 1;
auto r1 = get(v * 2 + 1, l, m, L, min(m, R));
auto r2 = get(v * 2 + 2, m + 1, r, max(m + 1, L), R);
return max(r1, r2);
}
int main() {
scanf("%d", &n);
forn(i, n) scanf("%d%d%d", &a[i].x.x, &a[i].x.y, &a[i].y);
forn(i, n) {
vals.pb(a[i].x.x);
vals.pb(a[i].x.y);
}
vals.pb(0);
sort(all(vals));
vals.pb(vals.back() + 1);
vals.resize(unique(all(vals)) - vals.begin());
forn(i, n) {
int x = lower_bound(all(vals), a[i].x.x) - vals.begin();
int y = lower_bound(all(vals), a[i].x.y) - vals.begin();
ev[min(x, y)].pb(mp(max(x, y), a[i].y));
}
n = sz(vals);
build(0, 0, n - 1);
li ans = -1;
int ansl = -1, ansr = -1;
for (int i = sz(vals) - 1; i >= 0; i--) {
for (auto it : ev[i]) upd(0, 0, n - 1, it.x, n - 1, it.y);
auto cur = get(0, 0, n - 1, i, n - 1);
if (cur.x + vals[i] > ans) {
ans = cur.x + vals[i];
ansl = vals[i]; ansr = vals[cur.y];
}
}
printf("%lld\n%d %d %d %d\n", ans, ansl, ansl, ansr, ansr);
}
```

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (BledDest)**

```
#include <bits/stdc++.h>
using namespace std;
const int N = 40;
const int M = 20;
long long incident_mask[N];
vector<int> g[N];
int n, m;
long long ans = 0;
long long cntmask[1 << M];
long long binpow(long long x, long long y)
{
long long z = 1;
while(y > 0)
{
if(y % 2 == 1) z *= x;
x *= x;
y /= 2;
}
return z;
}
int used[N];
void dfs(int x, int c)
{
if(used[x])
return;
used[x] = c;
for(auto y : g[x])
dfs(y, 3 - c);
}
long long countIsolated()
{
long long ans = 0;
for(int i = 0; i < n; i++)
if(g[i].empty())
ans++;
return ans;
}
long long countComponents()
{
memset(used, 0, sizeof used);
long long ans = 0;
for(int i = 0; i < n; i++)
if(!used[i])
{
ans++;
dfs(i, 1);
}
return ans;
}
bool bipartite()
{
memset(used, 0, sizeof used);
for(int i = 0; i < n; i++)
if(!used[i])
dfs(i, 1);
for(int i = 0; i < n; i++)
for(auto j : g[i])
if(used[i] == used[j])
return false;
return true;
}
long long countIndependentSets()
{
int m1 = min(n, 20);
int m2 = n - m1;
//cerr << m1 << " " << m2 << endl;
memset(cntmask, 0, sizeof cntmask);
for(int i = 0; i < (1 << m1); i++)
{
long long curmask = 0;
bool good = true;
for(int j = 0; j < m1; j++)
{
if((i & (1 << j)) == 0)
continue;
if(curmask & (1 << j))
good = false;
curmask |= ((1 << j) | incident_mask[j]);
}
if(good)
{
cntmask[curmask >> m1]++;
}
}
for(int i = 0; i < m2; i++)
for(int j = 0; j < (1 << m2); j++)
if(j & (1 << i))
cntmask[j] += cntmask[j ^ (1 << i)];
long long ans = 0;
for(int i = 0; i < (1 << m2); i++)
{
long long curmask = 0;
bool good = true;
for(int j = m1; j < n; j++)
{
if((i & (1 << (j - m1))) == 0)
continue;
if(curmask & (1ll << j))
good = false;
curmask |= (1ll << j) | incident_mask[j];
}
if(good)
{
//cerr << i << endl;
ans += cntmask[(i ^ ((1 << m2) - 1))];
}
}
return ans;
}
long long calc(int mask)
{
if(mask == 0)
return binpow(2, n);
if(mask == 1 || mask == 4)
return countIndependentSets();
if(mask == 2)
return binpow(2, countComponents());
if(mask == 3 || mask == 6)
return binpow(2, countIsolated());
if(mask == 5)
return (bipartite() ? binpow(2, countComponents()) : 0);
if(mask == 7)
return (m == 0 ? binpow(2, n) : 0);
return 0;
}
int main() {
cin >> n >> m;
for(int i = 0; i < m; i++)
{
int x, y;
cin >> x >> y;
--x;
--y;
g[x].push_back(y);
g[y].push_back(x);
incident_mask[x] ^= (1ll << y);
incident_mask[y] ^= (1ll << x);
}
for(int i = 0; i < 8; i++)
{
//cerr << i << " " << calc(i) << endl;
if(__builtin_popcount(i) % 2 == 0)
ans += calc(i);
else
ans -= calc(i);
}
cout << ans << endl;
return 0;
}
```

Very sorry gor noob question, but in G why is F(0.1) number of independent sets in graph?

$$$F(\{0, 1\})$$$ is such a coloring that no pair of vertices colored $$$1$$$ are connected by an edge. So the subtask is to count the number of ways to choose vertices to color them $$$1$$$ in such a way that no pair is connected by an edge. And that's the definition of an independent set.

Yeah, I figured it out by myself after some time... I think you should include this explanation in the editorial though, it's not immediately obvious.

Meh, I think it's fine. Editorials are not supposed to be immediately obvious for everybody.

Let me explain (I didn't test my solution yet though). And frankly making it partially for myself. Correct me if I'm wrong.

As PikMike said, F({0,1}) means that we can't put 1 on to two connected vertices.

Let's just consider on example of 5 verts graph (below are edges):

{1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 1}

First we can put 0 everywhere.

Another options?

For example, we put 1 on first vert (v1). Where else we can put 1 and how many ways to do it?

We can just put 0 on the rest.

In order to avoid edges with 2, we can put 1 only on vertices not connected to v1. And such vertices will form independent set. Amount of such combinations of ones (1) obviously is amount of independent sets. So in our case for v1 next combinations are allowed:

{v1}, {v1, v3}, {v1, v4}

and so on.

All together:

{v1}, {v1, v3}, {v1, v4}, {v2}, {v2, v4}, {v2, v5}, {v3}, {v3, v5}, {}

Total 9 combinations.

We should also count empty independent set, right?

I still don't understand Why it is not beneficial to increase the length of some board by three or more.... (Problem D) Can anyone help???

because there is no need. even if u increase by 2 or 1 or 0 u can de different from ur neighbors

Assuming $$$a_i = a_{i-1}$$$. We can increase $$$a_i$$$ or $$$a_{i-1}$$$ by 1.

If we decide to increase $$$a_i$$$ by 1, it doesn't change anything before, so the Fence is still great up to now.

If we decide to increase $$$a_{i-1}$$$ by 1, it can equal to $$$a_{i-2}$$$ and break the Fence's greatness. In this situation, we can continuously increase $$$a_{i-1}$$$ by 1 (now, it increased 2 units) or increase $$$a_{i-2}$$$ by 1.

That's the reason why we should increase every $$$a_i$$$ at most $$$2$$$.

The only requirement is that the height of two adjacent board should not be the same. Consider a board 'i' with a height ai, there can be 3 possibilities- 1. all adjacent board has the same height. 2. all adjacent board has a different height. 3. any two board has the same height.

In case 1 we can either increase the height first by 1, without altering the height of second, increase height of second or increase the height of second by 2 and third by 1 or vice versa. (this can be applied to any pair). Hence we do not need more than 2 increments for a particular board.

Case 2 and 3 are obvious.

3 case structure theorem

can someone explain 5th question . I dont think explanation is correct , how can u convert fourth type segment into 2nd type segment and what about the cases in a>=2*b

Can someone give me the proof for problem B?

Let's play chess. :v BTW, all black cells $$$(i,j)$$$ in a chess board have the same parity of $$$i+j$$$ and different from all white cells.

I did it using a bfs. Similar to bipartite colouring

I do the same with dfs :))

Fact 1.If we want to maximize the number of attacks, then we would put black horse on the board, such that any black horse always attacks only white horse. This happens if the black horses are placed in square of the same color. Easy to note that when placed a horse on a black square it always attacks a white squares.Fact 2.We can put an $$$id$$$ for each square of the board. Let $$$n$$$ the number of black squares and $$$m$$$ the number of white squares. A black horse that attacks a white horse is equivalent to claiming that a white horse attacks a black horse. That is:This is true because we can represent the attacks as a bipartite graph $$$G$$$. Let $$$G [X, Y]$$$ be a bipartite graph where $$$X$$$ corresponds to the black horse vertices and $$$Y$$$ to the white horse vertices. Clearly the number of attacks equals the number of edges.

Editorials solution is true . Lets construct a graph , (i,j) can attack (k,l) . That means (k,l) also can attack (i,j) . Lets connect (i,j) and (k,l) with an edge . Now using bicoloring idea , run a bfs . And you will see all the solution has a pattern repeat BW again and again . My BFS solution: https://codeforces.com/contest/1221/submission/61608838

Hold on, what is OR-convolution mentioned in G? I couldn't google it.

Google sum over subsets DP, that's the thing you need.

Yah I solve G using that, just wondering what is OR convolution

I remember seeing it here and here but idk if it's really needed in the solution.

Thanks a lot. As I know curiosity always leads me to sth more to learn

In problem A , how to prove that if sum of numbers other than numbers greater than 2048 is greater or equal to 2048 then answer will be Yes ?

Very weak test cases for A even my wrong code got accepted

?your code is correct

Yeah sorry I just saw that numbers were in powers of 2 if not then my code was incorrect

Can D be solved without dp???

can someone tell me what

`if (c + m + x - 2 * mid >= mid)`

means in problem C ?If $$$mid$$$ teams are formed, then $$$mid$$$ coders are already taken and $$$mid$$$ mathematicians are also taken. That leaves us with $$$(c - mid) + (m - mid) + x$$$ people to fill the empty spot in each of the $$$mid$$$ teams. So if that condition if true, then there are enough people to form at least $$$mid$$$ teams.

got it! Thank you sir!.

In Problem E, when we consider segments of type 4, where len >= 2*b, how can we say that Bob can always convert it into a segment of type 2? If (a+b) <= len < 3b, if Bob makes his move, the segment will become type 3

When $$$len \geq 2*b$$$, Bob can always get a segment of type $$$2$$$ by saving the $$$b$$$ right most places and then choosing his segment. Eg. if $$$b=2$$$ and $$$len=8$$$, $$$\ ........ \rightarrow\ ....XX..\ $$$ Now he can use the right most place when Alice doesn't have a move left.

Please Someone explain how to do D.

Problem F ,if I submit my code with GNU C++17 ,I would Wrong answer on test 2, if I submit my code with GNU C++14,it was Accepted.Could someone tell me why? my code: 60964098 60962460. Sorry for my poor English.

In 5, how are we sure that 2b>=a when it is only mentioned that a>b?

We don't. If a <= 2b then there is just no segment of the third type.

need a proof for problem "A" solution please

Can anyone give links to more questions like Problem C — classic Binary Search? I want to solve more of these Bin. Search questions.

There are accepted solutions (e.g. 60854023)

for

Problem C(Perfect Teams)which are just$$$min \{c, m, \left \lfloor{\frac{c+m+x}{3}}\right \rfloor\}$$$

Could someone please prove (or explain the idea behind) the formula?

By definition, each team consists of a coder, a mathematician, and exactly three people. The resource with minimal availability decides how many perfect teams you can build.

i can understand how minimal availability of c & m decide the outcome but what does (c+m+x)/3 here signify?

can you please explain? _/\_

You need enough people for 3 people per team.

The resource with minimal availability (either $$$c$$$ or $$$m$$$) defines an

upper boundfor the number of perfect teams (which is not necessarily the same as the number of perfect teams).Thus, it is not yet obvious to me what is the idea behind

provingthat the whole formula is valid for all possible test cases.haizz i am bad at implementation algorithm. That's why i rarely do well in the contest :< . Can someone give me advice on this matter, pls !! sorry for my poor english :D

Read and understand good codes of the questions you are doing... try to remember loopholes and learn to make your code short and simple. Also each line of the code should be important that is your code shouldn't be redundant.

Can E be solved like this? I am not sure! :3

First take segment length of dots, then sort them and obviously ignore the lengths smaller than b. Then we declare

which saves what happens if alice starts, if bob starts when there are firstvector < pair > infolengths only.iNow in these sorted lengths, take the first one and save who wins if there is only that first segment and alice starts the move, if there is only that last segment and bob starts the move

Then we iterate i from 1 to size of segment lengths array. For i-th element, we decide who will win if alice starts, if bob starts the move when there are only first i segments. We decide considering the i-th length and the information from

info[i-1]......and save it ininfo[i]......**sorry for my explanation.....i suck at explaining :(

problem A mathematical induction proof: (1) if the sum of the not larger than 1 elements is greater than 1, the numbers can merged into 1. obvious. (2)suppose the sum of not larger than 2^(k-1) elements is greater than 2^(k-1), the numbers can be merged into 2^k. Then if the sum smaller than 2^k elements of is larger than 2^k , the numbers can be merged into 2^k.

in D what is the proof that time complexity of the recursion won't be large I did not get how the dp is exactly working

because all boards will be increased by no more than two.

Yeah I know but there's a for loop with calc function with three possibilities x=0 x=1 x=2 so it's o(3^n) complexity isnt it ? Or if statement is making it o(n) but why

No it is 3*3*n

the proof is in the problem he say It is guaranteed that sum of all n over all queries not exceed 3*1e5 so it make dp fit in the time .

My recursive DP solution for problem D is timing out , It times out in the test case where answer is always 0 , the weird thing is that it times out even after I hardcode the case where number of elements are always 1! can someone please check and let me know where I can optimize ? Thanks ! https://codeforces.com/contest/1221/submission/61071469

I hope your problem is already solved by now, but I'm writing it for other people!

Use fastio. I was having the same problem! Write this inside main(): ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

Can anyone please help me in problem D. I am getting wrong answer on teset case 2. I am using tabulation approach instead of memoization. Here is also Link to my submission. Thanks in advance

just use temp=1e18 insted of LONG_MAX

Got AC !!!

Thanks @i_ll_try_123.

Can you please tell me why using 1e18 is working instead of LONG_MAX

can you please post it's recursive solution

You can check editorial solution for that.. which is a memoization approach

That's not memoization, that is bottom — up approach.Can you post top down approach

Hi, i am trying to understand the tutorial for 1221F where it says "let's reformulate the problem the following way: we have to find the segment (l,r), such that the sum of the segments fully covered by it is maximal." segment(l,r) is formed by the two points (l,l) and (r,r) belonging to the bisectrix? Is the sum about our cost function and if so why do we calculate it for the segments and not for the points?

I don't understand the formula of DIV2C

c + m + x — 2 * mid >= mid__ Please help...https://codeforces.com/blog/entry/69925?#comment-544378

Why am I getting a TLE in this solution to the D. Link: https://codeforces.com/contest/1221/submission/61306295

write this in your code

ios_base::sync_with_stdio(false); cin.tie(NULL);

I can't understand editorial for problem F. What do you store in the segment tree, also how do you initialize it?

In problem E if 2b<a then the class number 3 is mathematically incorrect. maybe use a+b instead of 2b?

In problem C.Perfect teams. For the test case where c=18 m=13 and x=0; the maximum possible number of teams can be 9...but the test cases give solution to be 10. I think the test case has wrong answer .Where am i wrong???Please help.

C C C C C C C C C C C

C C C C C C C M M M

M M M M M M M M M M

Helpp!! Why is this not working for A

I have an alternate solution and (maybe more intuitive) for problem A.

Let's ignore elements > 2048.

If 2048 is already in the multiset, we are done. Otherwise, notice that the merging of the smallest two equal elements in the multiset can be used in any sequence of merges that can obtain 2048 without making the "Yes" answer become "No". This is because that is the only way to merge any of those two elements with some other element. We keep doing this until we have 2048 in the multiset or we cannot merge any more elements. Due to our invariant that the merging at each step will not affect the answer, if we cannot obtain 2048, then the answer is clearly "No". Otherwise, the answer is "Yes".

Note that if at any point during the merging, if the smallest two elements in the set are not equal, we can discard the smaller one because that element cannot be merged with any element and can be declared useless.

To support the efficient merging and extraction of minimum elements, we can use a priority queue.

Time complexity: $$$\mathcal{O}(NlogN)$$$ for each test case because we can have $$$\mathcal{O}(N)$$$ merges/discards per test case.

My implementation.

Can anyone tell me the botton up solution of question D? Link is ->

Question D

Because both the tutorials have top down method