Auto comment: topic has been translated by TheEvilBird (original revision, translated revision, compare)

Автокомментарий: текст был обновлен пользователем TheEvilBird (предыдущая версия, новая версия, сравнить).

Great contest, fast editorial

C was harder than D for me

A question about D: My solution is sorting all the "1"s by the Manhattan Distance to the bottom left corner, and add them one by one. Why it is true?

Why is it still not possible to upsolve problems?

for whose who ask why the optimal answer for problem $$$D$$$ is $$$\frac{k} {2}$$$ :

first the total answer if we make each part has $$$\frac{k} {2}$$$ ones is $$$\frac{k^{2}} {4}$$$.

now lets assume that in the first part we have $$$\frac{k} {2} + m$$$ for some positive $$$m$$$, then the answer will be:

$$$(\frac{k} {2} + m) * (k - \frac{k} {2} - m) = (\frac{k + 2 m} {2}) * (\frac{k - 2 m} {2})$$$ = $$$\frac{k^{2} - 4m^{2}} {4}$$$ = $$$\frac{k^{2}} {4} - m^{2}$$$ $$$ \lt $$$ $$$\frac{k^{2}} {4}$$$

similarly if we assume the answer is $$$\frac{k} {2} - m$$$ then the answer will be the same which is strictly less than $$$\frac{k^{2}} {4}$$$.

I solved E a bit differently, here was my thought process:

There's exactly 1 cell on every diagonal we visit for every path from $$$(1,1)$$$ to $$$(n,m)$$$. That is, for every $$$c$$$ from 1 to $$$n+m$$$, there is exactly one $$$(x,y)$$$ on the path where $$$x+y = c$$$. The proof is just by noting that every step on this path increments $$$(x,y)$$$ by exactly 1.

Now let $$$dp1[i][j]$$$ be the max enjoyment from $$$(1,1)$$$ to $$$(i,j)$$$, excluding the enjoyment from the cell $$$(i,j)$$$. Let $$$dp2[i][j]$$$ be the max enjoyment from $$$(i,j)$$$ to $$$(n,m)$$$, including the enjoyment from the cell $$$(i,j)$$$. The reason why I'm defining the dp's asymmetrically about counting cell $$$(i,j)$$$ is so that $$$dp1[i][j] + dp2[i][j]$$$ is the max enjoyment going through $$$(i,j)$$$. Both these dps are standard, can be calculated in $$$O(mn)$$$ time.

Now for the key idea: what's the max enjoyment if you don't go through $$$(i,j)$$$? Since you visit exactly 1 cell in each diagonal, you can just find the max enjoyment by going through every cell on the "$$$i+j$$$" diagonal except $$$(i,j)$$$. This gave me the idea to just store $$$dp1[i][j] + dp2[i][j]$$$ separately, now if you want to find the max enjoyment by negating $$$i,j$$$, modify the value of $$$dp1[i][j] + dp2[i][j]$$$ in the "$$$i+j$$$" set by decrementing it by $$$2*a[i][j]$$$, and find the max value of that set. Do this for every element of the grid and you have your answer.

Yes this answer has an extra log factor because of sets but I think you can remove that too by instead of maintaining sets, storing the max and second max value alone for every diagonal.

For D, I Really thought of using DP

Realising I was so wrong But ig mind literally burned out after 1.5 hrs giving a lot of time to solve C

.

You can solve E in a really scuffed way:

Can anyone help me why my O(2*k*n*sqrt(n)) gives TLE, My solution is exactly same as what was discussed in first part

void solve(){
    int n,k; cin>>n>>k;
    vector<string>mat(k);
    for(string& st:mat) cin>>st;

    vector<int>factors;
    for(int i=1;i*i<=n;++i){
        if(n%i!=0) continue;
        factors.pb(i);
        factors.pb(n/i);
    }
    sort(all(factors));
    debug(factors);
    string res="";
    for(int fact:factors){
        if(fact==n) continue;
        bool ok=true;
        debug(fact);
        for(int i=0;i<fact;++i){
            vector<vector<int>>freq(fact,vector<int>(26,0));
            for(int j=i;j<n;j+=fact){
                // debug(j);
                vector<int>fr(26,0);
                for(int t=0;t<k;++t){
                    fr[mat[t][j]-'a']++;
                }
                for(int p=0;p<26;++p){
                    if(fr[p]!=0)
                    freq[j%fact][p]++;
                }
            }
            bool ok1=false;
            for(int c=0;c<26;++c){
                bool can=(freq[i][c]==n/fact);
                if(can){
                    res+=char(c+'a');
                    ok1=true; break;
                }
            }
            if(ok1){
                continue;
            }
            res=""; ok=false; break;
        }
        if(ok) break;
    }
    if(res.empty()){
        res=mat[0];
        cout<<res<<endl; return;
    }
    string ans="";
    while(ans.size()<n){
        ans+=res;
    }
    cout<<ans<<endl;
}

for d whos not getting just assume total number of ones as t and b will be t-a then at-a^2 since t is a constant differentiate it wrt a and wed get t-2a and equate it to zero its pretty clear a will be t/2 and hence b will be t/2 its a maxima point cause a and b are positive so yeah pretty simple d and e today tbvh

in C, rather than storing a frq array for each index, store a bitmask of 26bits of which letters are possible for that index, then if you want to see if there's some character which is possible for a group of indices, then their AND should be non-zero, indicating there's at least 1 set-bit common in all, and then use __builtin_ctzll(x) to get your required character for this group. This could be useful if constraints on n were a bit tighter like 2e5, by redicing TC from O(26n√n) to O(n√n)

those who are having difficulty in understanding d lower bound k/2 you can just differentiate ab with respect to a cause a+b=total total is concstant and b=t-a so at-a2 and diff wrt a you get t=2a since a is always positive thus you get this as your maxima and then just use constructive algo to form answer

#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;

const ll mod=1e9+7;

void solve(){
    ll n, m;
    cin >> n >> m;
    vector<bool> v(n * m); 
    ll ones = 0;

    for(ll i = 0; i < n; i++){
        for(ll j = 0; j < m; j++){
            int x;
            cin >> x;
            
            v[i * m + j] = x; 
            ones += x;
        }
    }

    ll limit = ones / 2;
    ll i, j, stat = 1;
    
    for(i = 0; i < n; i++){
        for(j = m - 1; j >= 0; j--){
            
            if(v[i * m + j] == 1) limit--;
            
            if(limit == 0){
                stat = 0;
                break;
            }
        }
        if(stat == 0) break;
    }

    ll k = 0;
    string s;

    
    if(j == 0){
        k = i + 1;
        while(k--) s += 'D';
        k = m;
        while(k--) s += 'R';
        k = n - i - 1;
        while(k--) s += 'D';
    } else {
        k = i;
        while(k--) s += 'D';
        k = j;
        while(k--) s += 'R';
        s += 'D';
        k = m - j;
        while(k--) s += 'R';
        k = n - i - 1;
        while(k--) s += 'D';
    }

    cout << (ones / 2) * ((ones + 1) / 2) << endl;
    cout << s << endl;
}

int main(){
    
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    ll t = 1;
    cin >> t;

    while(t--){
        solve();
    }
}

Help me! Memory limit exceeded, have seen memory exceed first time

SPOILER , CODE PRESENT

2194D — Table Cut :

        while (testcases>0) {
            int x=input.nextInt();
            int y=input.nextInt();
            int[][] arr = new int[x][y];
            int sum=0;
            int[] y_ones=new int[y];
            for(int i=0;i<x;i++){
                for(int j=0;j<y;j++){
                    arr[i][j]=input.nextInt();
                    sum+=arr[i][j];
                    y_ones[j]+=arr[i][j];
                }
            }
            int req=sum/2;
            long ans=req;
            if(sum%2==0){
                ans*=req;
            }
            else{
                ans*=(req+1);
            }
            int break_at_y=0;
            int count=0;
            int start=0;
            if(count<req){
                while(true){
                    count+=y_ones[start];
                    start++;
                    break_at_y++;
                    if(count==req){
                        break;
                    }
                    if(count>req){
                        break_at_y--;
                        break;
                    }
                }
            }
            int extra = count-req;
            int break_at_x=x-1;
            if(break_at_y<y){
                for(int i=x-1;i>=0;i--){
                    if (extra==0) {
                        break_at_x=i;
                        break;
                    }
                    if(arr[i][break_at_y]==1){
                        extra--;
                    }
                }
            }
            
            String ans_str="";
            for(int i=0;i<break_at_y;i++){
                ans_str+="R";
            }
            for(int i=0;i<=break_at_x;i++){
                ans_str+="D";
            }
            if(break_at_y<y){
                ans_str+='R';
                break_at_y++;
            }
            while(break_at_x<x-1){
                ans_str+="D";
                break_at_x++;
            }
            while(break_at_y<y){
                ans_str+="R";
                break_at_y++;
            }
            out.println(ans);
            out.println(ans_str);
            testcases--;
        }
}

I am not able to figure out the issue here , my break_at_y ranges from [0,y] , 0 means , I dont move right at the start ,and n means i move to complete right. And my break_at_x ranges from [0,x-1] My break_at_y will try to break just before the count of prefix_y_1 becomes more than sum/2.I am taking care of some columns not having any 1. My break at x ranges from 0 to x-1 , because I try to decrement x only in case I required more 1 , if the break_y didnt get enough 1's , if not , I go till end of x , so I always need atleast 1 row here.

Wanted to discuss what I might be doing wrong.

Why does my O(nm) solution 362095542 TLE at test case 49?

can someone explain how they approced B?

In F, shouldn't dp[v][x] be added to dp[v][xor_subtree[v]] instead?

Good round!

I had a slightly different solution for problem E (2194E - The Turtle Strikes Back), that is perhaps slightly simpler, though it has the same complexity.

Consider the cells that lie on an antidiagonal of the grid, for example:

...x
..x.
.x..

Since Michaelangelo's path can only go right or down, each path from top-left to bottom-right must pass through exactly one of the cells on this diagonal (and that is true for each parallel line). We can calculate the value of the optimal path going through each of these cells using the dpS and dpT memos as described in the editorial.

Now, the key point is that we only need to consider the best 2 cells on the diagonal. If the cell through which the maximal path runs has a positive value, then Raphael can invert it to reduce the value of the path going through it. It might still be the best possible path, or maybe Michelangelo will have to switch to the path with the second-best value, but he never has to switch to any of the other paths.

So we can process each diagonal one by one, covering all possible cells, for an $$$\mathcal{O}(nm)$$$ solution.

Slightly messy solution I submitted during the contest: 361983731

Очень хороший раунд, особенно понравилась задача B, спасибо dope за такую задачу я твой фанат

why d cannot have multiple answers?? i have taken a iterator and iterated till count of 1 divided by 2 and if there is 1 in the 1st block greater than count1/2 (which will divide whole array in two parts)then i will take a iterator such that it elements 1 till count1/2== no of 1s in first block, and then i will iterate till right and down till till i have reached end of block 1 and then totally down and then totally right. where i am wrong? ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ //This is the code

include <bits/stdc++.h>

using namespace std; using ll = long long; void solve(){ int n,m; cin>>n>>m; int arr[n][m]; string s; int count1=0; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cin>>arr[i][j]; if(arr[i][j]==1) count1++; } } int tempc=0; int checkc=0; for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(arr[j][i]==1) tempc++; checkc=i; } if(tempc>=count1/2) break; } int extra=tempc-count1/2; int temp=extra; int checki=0; int checkj=0; if(extra>0){ for(int i=0;i<n;i++){ for(int j=checkc;j>=0;j--){

if(arr[i][j]==1) extra--;
            checki=i;
            checkj=j;
            if(extra==0) break;
        }
        if(extra==0) break;
    }
    cout<<checki<<" "<<checkj<<endl;
    int j=0;
    while(j<checkj){ s.push_back('R'); j++;}
    int i=0;
    while(i<=checki){ s.push_back('D');i++;}
    int k=j;
    while(k<=checkj){ s.push_back('R');k++;}
    while(i<n){ s.push_back('D'); i++;}
    while(k<m){s.push_back('R'); k++;}
}
else{
    for(int j=0;j<=checkc;j++) s.push_back('R');
    for(int i=0;i<n;i++) s.push_back('D');
    for(int k=checkc+1;k<m;k++) s.push_back('R');
}
int ans=0;
if(count1%2==0) ans=(count1/2)*(count1/2);
else ans=(count1/2+1)*(count1/2);
cout<<ans<<"\n"<<s<<"\n";

} int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; cin>>t; while(t--) solve(); return 0; } // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ can anyone please help?

Thank you for the great contest and editorial. Nevertheless I found problem F1 a bit difficult for me, even with the help of the editorial. Can anyone share more details on the solution and thought process and also can share similar problem to practise?

I have a question about problem E.

I have a solution where there is 3d dp n*m*2. I will call this dp 2-layered:

• layer-zero, where each cell (i, j) presents the best result when none of cell was turned into bad one;
• layer-one, where one of cells in path to cell (i, j) was turned into bad one and we went through it.

The logic I used:

• we can get into dp[i][j][0] only from it's left or upper cells on the same layer;
• to get into dp[i][j][1] we have two oprions:

1. current cell (i, j) is turned into bad, so we can get there only from layer-zero: dp[i][j][1] = max(dp[i - 1][j][0], dp[i][j - 1][0]) - a[i][j];
2. some cell before (i, j) was turned into bad, so we can get there only from layer-one: dp[i][j][1] = max(dp[i - 1][j][1], dp[i][j - 1][1]) + a[i][j];

• as the second turtle decides which cell to turn into a bad one, so we need to pick min of these two options (as I think)

Summing up, have this moves:

dp[i][j][0] = max(dp[i - 1][j][0], dp[i][j - 1][0]) + a[i][j];

dp[i][j][1] = max(min(dp[i - 1][j][0], dp[i][j - 1][0]) - a[i][j]), min(dp[i - 1][j][1], dp[i][j - 1][1] + a[i][j]));

In most, that is all my solution.

But it doesn't work on test 1. And I still cannot undestand why.

Can anybody explain what is wrong with this approach?

Thanks in advance

I think D is harder than E.

Here is an approach to F1 that does not use XOR basis.

Since XOR is its own inverse, removing a subgraph that has an XOR sum of $$$b_j$$$ from a subtree $$$u$$$ is equivalent to applying an XOR of $$$b_j$$$ on $$$u$$$. Thus, we just need to maintain the parity of the number of times we have cut a subgraph with XOR sum $$$b_j$$$.

Our dp state is $$$dp[u][mask]$$$, where $$$u$$$ is the subtree and $$$mask$$$ stores the parity of the number of times $$$b_j$$$ has been cut.

Our transitions can be done with an XOR convolution, so our solution runs in $$$O(n*4^k)$$$.

Submission: 362338987

Does anyone know how we can generate tests for problem F2 ?

Neat and Clean explanations especially in C and D. Thank you!

though I didn't join this contest , I still think it is a great round !!!

In question E, shouldn't it be at most 1 instead of exactly 1?

Because he can choose not to select any pizza to apply sauce?

F2 is so hard, i haven't learnt fft yet, let alone fwt:)). How can i get documents about fft and fwt , i want to learn these algorithms to solve F2:)

i can't passed F2 because of TLE on test 6,where can i imporve in this code. code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 5,MOD = 1e9+7,M=1<<10;
int h[N], e[N << 1], ne[N << 1],idx;
int a[N],b[10];
vector<int>trs;
set<int>sb;
vector<int>kn;
vector<int>fz;
int n, m, k;
int H[M][M];
LL invm;
unordered_map<int, vector<int>>jv,jl;
int popCount(int x) {
	int res = 0;
	while (x) {
		res++;
		x -= (x & -x);
	}
	return res;
}
void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
	e[idx] = a, ne[idx] = h[b], h[b] = idx++;
}
LL qmi(LL a, int k) {
	LL res = 1;
	while (k) {
		if (k & 1) {
			res = res * a % MOD;
		}
		a = a * a % MOD;
		k >>= 1;
	}
	return res;
}
void fwht(vector<int>&a, bool inv = 0) {
	for (int hf = 1; hf * 2 <= m; hf <<= 1) {
		for (int qd = 0; qd < m; qd += hf * 2) {
			for (int j = 0; j < hf; ++j) {
				LL u = a[j + qd], v = a[qd + hf + j];
				a[j + qd] = (u + v)%MOD;
				a[qd + hf + j] = (u &mdash; v)%MOD;
			}
		}
	}

	if (inv) {
		for (int i = 0; i < m; ++i)a[i] =(LL)a[i]*invm%MOD;
	}
}
void dfs1(int xz, int pre) {
	trs[xz] = a[xz];
	for (int i = h[xz]; ~i,2026-03-12; i = ne[i]) {
		int j = e[i];
		if (j == pre)continue;
		dfs1(j, xz);
		trs[xz] ^= trs[j];
	}
}
vector<int> dfs2(int xz, int pre) {
	vector<int>dp = vector<int>(m, 1);
	for (int i = h[xz]; ~i,2026-03-12; i = ne[i]) {
		int j = e[i];
		if (j == pre)continue;
		vector<int>ls = dfs2(j, xz);
		for (int i = 0; i < m; ++i)dp[i] = ((LL)dp[i] * ls[i]) % MOD;
	}
	if (pre != -1) {
		if (jl.count(trs[xz])) {
			int wz = jv[trs[xz]][0];
			vector<int>q(m);
			for (int i = 0; i < m; ++i)q[i] = (dp[i] * fz[i]) % MOD;
			LL ls = 0;

			
			for (int i = 0; i < m; ++i) {
				ls = (ls + q[i] * jl[trs[xz]][i]) % MOD;
			}

			ls = (LL)ls * invm % MOD;
			for (int i = 0; i < m; ++i)dp[i] = (dp[i]+ls * H[wz][i])%MOD;
		}
	}
	return dp;
}
void solve()
{
	cin >> n >> k;
	memset(h, -1, (1+n)*4);
	idx = 0;
	for (int i = 0; i < n &mdash; 1; ++i) {
		int a, b;
		scanf("%d%d", &a, &b);
		add(a, b);
	}
	for (int i = 1; i <= n; ++i)scanf("%d", &a[i]);
	sb = set<int>();
	for (int i = 0; i < k; ++i) {
		scanf("%d", &b[i]);
		sb.insert(b[i]);
	}
	m = 1 << k;
	invm = qmi(m, MOD &mdash; 2);
	fz = vector<int>(m);
	for (int i = 0; i < k; ++i)fz[1 << i] = 1;
	fwht(fz);
	kn = vector<int>(m);
	
	for (int i = 0; i < m; ++i) {
		for (int j = 0; j < k; ++j)if (i & (1 << j))kn[i] ^= b[j];
	}
	jv.clear();
	for (int i = 0; i < m; ++i) {
		if (!jv.count(kn[i]))jv[kn[i]] = vector<int>();
		jv[kn[i]].push_back(i);
	}
	jl.clear();
	for (auto it : jv) {
		jl[it.first] = vector<int>(m);
		for (int r : it.second) {
			for (int i = 0; i < m; ++i) {
				jl[it.first][i] += H[r][i];
			}
		}
	}
	trs = vector<int>(n + 1);
	dfs1(1, -1);
	if (!jl.count(trs[1])) {
		cout << 0 << endl;
		return;
	}
	vector<int>dp = dfs2(1, -1);
	LL res = 0;
	fwht(dp, 1);
	for (int i = 0; i < m; ++i) {
		if (sb.count(trs[1] ^ kn[i]))
			res = (res + dp[i]) % MOD;
	}
	cout << res << endl;
}
int main()
{
	int t;
	cin >> t;
	for (int i = 0; i < M; ++i) {
		for (int j = 0; j < M; ++j) {
			H[i][j] = qmi(-1, popCount(i & j));
		}
	}
	while (t--)
	{
		solve();
	}
}

Can Someone pls explain what is wrong in this code for Problem E 368187983

Further explaination for the part "the second recomputation step, where we wanted to compute the value $$$dp[v][x]$$$ at certain points $$$x$$$ and add it to $$$dp[v][0]$$$ " in F2:

• let $$$a$$$ be $$$dp[v]$$$ and $$$f$$$ be $$$hadamard(a)$$$ in the tutorial, we do not maintain $$$a$$$ directly but maintain $$$f$$$ to reflected $$$a$$$.

• And by definition:

  • [I.] $$$f_i=\sum_j (a_j \cdot (-1)^{popcount(i\ AND\ j)})$$$
  • [II.] (by FWT) $$$a_j=\frac{1}{B} \cdot \sum_i (f_i \cdot (-1)^{popcount(i\ AND\ j)})$$$

We want to modify $$$f$$$ to reflected the operation:

• $$$a_{tar} \leftarrow a_{tar}+dv$$$
• $$$dv=\sum_{d} a_{tar \oplus d}$$$