Educational Codeforces Round 136 Editorial

#	User	Rating
1	Benq	3783
2	jiangly	3666
3	tourist	3611
4	Um_nik	3536
5	inaFSTream	3477
6	fantasy	3468
7	maroonrk	3464
8	QAQAutoMaton	3428
9	ecnerwala	3427
10	Ormlis	3396

#	User	Contrib.
1	Um_nik	185
2	adamant	177
2	awoo	177
4	nor	169
5	maroonrk	165
6	-is-this-fft-	164
7	antontrygubO_o	155
8	ko_osaga	151
8	dario2994	151
10	SecondThread	149

Tutorial

Solution 1 (awoo)

for _ in range(int(input())):
	n, m = map(int, input().split())
	print(n // 2 + 1, m // 2 + 1)

Solution 2 (awoo)

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

int main() {
	int t;
	scanf("%d", &t);
	forn(_, t){
		int n, m;
		scanf("%d%d", &n, &m);
		int svx = 1, svy = 1;
		for (int x = 1; x <= n; ++x){
			for (int y = 1; y <= m; ++y){
				bool ok = true;
				for (int dx : {-2, -1, 1, 2}){
					for (int dy : {-2, -1, 1, 2}){
						if (abs(dx * dy) != 2) continue;
						if (1 <= x + dx && x + dx <= n && 1 <= y + dy && y + dy <= m)
							ok = false;
					}
				}
				if (ok){
					svx = x;
					svy = y;
				}
			}
		}
		printf("%d %d\n", svx, svy);
	}
}

1739B - Array Recovery

Idea: BledDest

Tutorial

Solution (Neon)

for _ in range(int(input())):
	n = int(input())
	ans = [0]
	for x in map(int, input().split()):
		if x != 0 and ans[-1] - x >= 0:
			print(-1)
			break
		else:
			ans.append(ans[-1] + x)
	else:
		print(*ans[1:])

1739C - Card Game

Idea: BledDest

Tutorial

Solution 1 (BledDest)

#include<bits/stdc++.h>

using namespace std;

long long dp[65][65][3];

void solve(int n)
{
    memset(dp, 0, sizeof dp);
    int k = n / 2;
    dp[0][0][2] = 1;
    for(int i = 0; i <= k; i++)
        for(int j = 0; j <= k; j++)
            for(int t = 0; t <= 2; t++)
            {
                int turn = (i + j) % 4;
                if (turn == 0 || turn == 3)
                {
                    if(i < k) dp[i + 1][j][t == 2 ? 0 : t] += dp[i][j][t];
                    if(j < k) dp[i][j + 1][t] += dp[i][j][t];
                }
                else
                {
                    if(i < k) dp[i + 1][j][t] += dp[i][j][t];
                    if(j < k) dp[i][j + 1][t == 2 ? 1 : t] += dp[i][j][t];
                }
            }
    for(int i = 0; i < 3; i++)
        cout << dp[k][k][i] % 998244353 << " ";
    cout << endl;
}

int main()
{
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
    {
        int n;
        cin >> n;
        solve(n);
    }
}

Solution 2 (BledDest)

def fact(n):
    return 1 if n == 0 else n * fact(n - 1)

def choose(n, k):
    return fact(n) // fact(k) // fact(n - k)

def calc(n):
    if n == 2:
        return [1, 0, 1]
    else:
        a = calc(n - 2)
        return [choose(n - 1, n // 2) + a[1], choose(n - 2, n // 2) + a[0], 1]

t = int(input())
for i in range(t):
    mod = 998244353
    n = int(input())
    a = calc(n)
    a = list(map(lambda x: x % mod, a))
    print(*a)

1739D - Reset K Edges

Idea: BledDest

Tutorial

Solution (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>> g;

vector<int> st;
vector<int> pd;

void init(int v, int d){
	st.push_back(v);
	if (int(st.size()) - d >= 0)
		pd[v] = st[st.size() - d];
	for (int u : g[v])
		init(u, d);
	st.pop_back();
}

vector<char> used;

void dfs(int v){
	used[v] = true;
	for (int u : g[v]) if (!used[u])
		dfs(u);
}

int get(int d){
	pd.assign(n, -1);
	init(0, d);
	
	vector<int> ord, h(n);
	queue<int> q;
	q.push(0);
	while (!q.empty()){
		int v = q.front();
		q.pop();
		ord.push_back(v);
		for (int u : g[v]){
			q.push(u);
			h[u] = h[v] + 1;
		}
	}
	reverse(ord.begin(), ord.end());
	
	used.assign(n, 0);
	int res = 0;
	for (int v : ord) if (!used[v] && h[v] > d){
		++res;
		dfs(pd[v]);
	}
	
	return res;
}

int main() {
	int t;
	scanf("%d", &t);
	while (t--){
		int k;
		scanf("%d%d", &n, &k);
		g.assign(n, vector<int>());
		for (int i = 1; i < n; ++i){
			int p;
			scanf("%d", &p);
			--p;
			g[p].push_back(i);
		}
		int l = 1, r = n - 1;
		int ans = n;
		while (l <= r){
			int m = (l + r) / 2;
			if (get(m) <= k){
				ans = m;
				r = m - 1;
			}
			else{
				l = m + 1;
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

1739E - Cleaning Robot

Idea: BledDest

Tutorial

Solution (awoo)

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for(int i = 0; i < int(n); i++) 

const int INF = 1e9;

int main(){
	int n;
	cin >> n;
	vector<string> s(2);
	forn(i, 2) cin >> s[i];
	vector<array<array<int, 2>, 2>> dp(n + 1);
	forn(i, n + 1) forn(j, 2) forn(k, 2) dp[i][j][k] = -INF;
	dp[0][0][s[1][0] == '1'] = s[1][0] == '1';
	dp[0][0][0] = 0;
	forn(i, n - 1) forn(j, 2){
		int nxtj = s[j][i + 1] == '1';
		int nxtj1 = s[j ^ 1][i + 1] == '1';
		dp[i + 1][j ^ 1][0] = max(dp[i + 1][j ^ 1][0], dp[i][j][1] + nxtj1);
		dp[i + 1][j][nxtj1] = max(dp[i + 1][j][nxtj1], dp[i][j][0] + nxtj1 + nxtj);
		dp[i + 1][j][0] = max(dp[i + 1][j][0], dp[i][j][0] + nxtj);
	}
	cout << max({dp[n - 1][0][0], dp[n - 1][0][1], dp[n - 1][1][0], dp[n - 1][1][1]}) << '\n';
}

1739F - Keyboard Design

Idea: BledDest

Tutorial

Solution (BledDest)

#include<bits/stdc++.h>

using namespace std;

const int N = 10043;
const int K = 12;

int tsz = 0;
int trie[N][K];
int aut[N][K];
int lnk[N];
int p[N];
int pchar[N];
int cost[N];
int ncost[N];

int newNode()
{
    lnk[tsz] = -1;
    ncost[tsz] = -1;
    cost[tsz] = 0;
    for(int i = 0; i < K; i++)
    {
        trie[tsz][i] = aut[tsz][i] = -1;
    }
    return tsz++;
}

int nxt(int x, int y)
{                                 
    if(trie[x][y] == -1) 
    {
        trie[x][y] = newNode();
        pchar[trie[x][y]] = y;
        p[trie[x][y]] = x;
    }
    return trie[x][y];
}

int go(int x, int y);

int get_lnk(int x)
{
    if(lnk[x] != -1) return lnk[x];
    int& d = lnk[x];
    if(x == 0 || p[x] == 0) return d = 0;
    return d = go(get_lnk(p[x]), pchar[x]);    
}

int go(int x, int y)
{
    if(aut[x][y] != -1) return aut[x][y];
    int& d = aut[x][y];
    if(trie[x][y] != -1) return d = trie[x][y];
    if(x == 0) return d = 0;
    return d = go(get_lnk(x), y);
}

void add(string s, int c)
{
    int cur = 0;
    for(auto x : s) cur = nxt(cur, x - 'a');
    cost[cur] += c;     
} 

int calc(int x)
{
    if(ncost[x] != -1) return ncost[x];
    ncost[x] = cost[x];
    int y = get_lnk(x);
    if(y != x) ncost[x] += calc(y);
    return ncost[x];
}

int main()
{
    int root = newNode();
    int n;
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        string s;
        int x;
        cin >> x >> s;
        map<char, set<char>> adj;
        for(int j = 0; j + 1 < s.size(); j++)
        {
            adj[s[j]].insert(s[j + 1]);
            adj[s[j + 1]].insert(s[j]);
        }
        bool bad = false;
        string res = "";
        char c;
        for(c = 'a'; c <= 'l'; c++)
        {
            if(!adj.count(c)) continue;
            if(adj[c].size() >= 3)
                bad = true;
            if(adj[c].size() == 1)
                break;
        }
        if(c == 'm' || bad) continue;
        res.push_back(c);
        while(adj[c].size() > 0)
        {
            char d = *adj[c].begin();
            adj[c].erase(d);
            adj[d].erase(c);
            c = d;
            res.push_back(c);  
        }
        bad |= adj.size() != res.size();
        map<char, int> pos;
        for(int i = 0; i < res.size(); i++)
            pos[res[i]] = i;
        for(int i = 0; i + 1 < s.size(); i++)
            bad |= abs(pos[s[i]] - pos[s[i + 1]]) > 1;
        if(bad) continue;
        add(res, x);
        reverse(res.begin(), res.end());
        add(res, x);
    }  
    int INF = 1e9;
    int K = 12;
    vector<vector<int>> dp(1 << K, vector<int>(tsz + 1, -INF));
    vector<vector<pair<int, int>>> pdp(1 << K, vector<pair<int, int>>(tsz + 1));
    dp[0][0] = 0;
    for(int i = 0; i < (1 << K); i++)
        for(int j = 0; j <= tsz; j++)
        {
            for(int z = 0; z < K; z++)
            {
                if(i & (1 << z)) continue;
                int nstate = go(j, z);
                int add = calc(nstate);
                int nmask = i | (1 << z);
                if(dp[nmask][nstate] < dp[i][j] + add)
                {
                    dp[nmask][nstate] = dp[i][j] + add;
                    pdp[nmask][nstate] = {z, j};
                }
            }
        }
    string ans = "";
    int curmask = (1 << K) - 1;
    int curstate = max_element(dp[curmask].begin(), dp[curmask].end()) - dp[curmask].begin();
    while(curmask != 0)
    {
        int cc = pdp[curmask][curstate].first;
        int ns = pdp[curmask][curstate].second;
        ans.push_back(char('a' + cc));
        curmask ^= (1 << cc);
        curstate = ns;
    }
    cout << ans << endl;
}

Comments (45)

Write comment?

Sa_GaR

8 months ago, # |

can anyone help me in D 174113824

→ Reply

Osman_Bey

8 months ago, # ^ |

I need help too; (●'◡'-)

variety-jones

Take a look at Ticket 16232 from CF Stress for a counter example.

OmShivamR24

4 months ago, # ^ |

Hello, Friend.

I am new to CodeForces. Could you share some pointers how and when CFStress may be useful during practise or contest?

During practice, whenever you get WA on large testcases, CF Stress can help you find the smallest testcase on which your Code fails, so that you can debug it yourself.

You can't use it during contests.

ganesh_6

Can someone suggest problems similar to Div2 C: Card Game, which requires DP, Combinatorics and some thinking. Thanks!

dutchmen

7 months ago, # ^ |

sum of product 2 ....codechef

Thanks will look into it

btw this question can be done in O(n) , with some combinatorics and some thinking..wont require dp..

nonrice

← Rev. 4 →

+10

For those who just want to see the recurrence used in solution for C:

$$$dp(n, p) = {n-1 \choose \frac{n}{2}}+ dp(n-2, p^{-1})$$$

Let $$$p$$$ represent some player, and $$$p^{-1}$$$ represent the opponent of that player.

Nanda

What is the analytical base case of this recurrence ?

RDFZzzx

If a Alice has got the biggest card, he will win.
Otherwise
- If the opponent will lose in the round with $$$n$$$ cards, the player will win in the round with $$$n + 2$$$ cards.
- Otherwise : he will lose.

JoshuaYang

6 months ago, # ^ |

W Observation. I did this

adityagamer

+28

When does the robot break? Let the robot currently be in the cell (j,i) (0-indexed) and the next column with a dirty cell be nxti (possibly, nxti=i). The robot breaks only if both (1−j,nxti) and (j,nxti) are dirty.

I think there is a typo. break condition should be (1-j,nxti) and (j,nxti + 1)

← Rev. 3 →

My solution to Prblem C in Div 2.

This is very interesting.

We can find that:

if Alice has the biggest number, he will win. Because he can use this card first.
Otherwise Boris has the biggest number, it's obvious that Boris will be "stronger" in the first turn, and he get first in the secound turn. So the number of ways that Alice wins is equal to the number of ways that Boris wins with $$$n - 2$$$ cards.

So we have $$$fst_i = \frac{C_{i}^{i/2}}{2} + lst_{i - 2}$$$.

There is another key to the task : the number of way to make a draw is equal to $$$1$$$. So $$$lst_i = C_{i}^{i/2} - fst_i - 1$$$.

My submission : 174191151

coww_

← Rev. 2 →

_ So the number of ways that Alice wins is equal to the number of ways that Boris wins with n−2 cards_ i dont understand this part, can you explain how you get to that observaton ?

Because in the first round, Boris is Stronger and plays cards first in the second round. (This is because Boris has got the biggest card). If Boris loses the round with $$$n - 2$$$ card, then Alise will win in the round with $$$n$$$ cards. For example.

Alice : $$$2, 3$$$

Boris : $$$1, 4$$$

Alice uses card $$$2$$$ and Boris uses card $$$4$$$, then Alice has card $$$3$$$ and Boris has card $$$1$$$. in this case ($$$2$$$ cards in total) Alice will win in the game ($$$4$$$ cards in total).

I think i slightly get your idea, but waittt isnt the example you gave should be a draw

leetcode07

In D, why does this greedy solution starting from the root and cutting whenever the depth exceeds the candidate does not work? TIA

Husanboy

Consider the following input

Input:

1
7 1
1 1 3 2 5 5

Output:

If you cut the tree whenever depth exceeds 2, you will require 2 operations, while the min. operations to make depth 2 is actually 1. Just make the tree and see why this happening :)

Thank you! I should have observed that removing a complete sub tree at (h-1) is better than removing each of its children at (h).

xox0

Why are the constraints so low for C?
I wrote a $$$O(n)$$$ solution which should easily work for $$$\Sigma n \geq 10^6$$$

The solution

PLAn22

3 months ago, # ^ |

Can i ask a question？ why in editorial the dp[0][0][2] is 1 ？

CodingCobra

Can anyone tell why this is giving WA? https://codeforces.com/contest/1739/submission/174471060

Take a look at Ticket 16237 from CF Stress for a counter example.

yash_15

Someone please help with my solution to problem E:

https://codeforces.com/contest/1739/submission/174503555

idea: dp[i][j][k] ; 0<=i<=1, 0<=j<=n-1, 0<=k<=2

dp[i][j][0] = num cells to clean manually in [0-1][j..n-1] rectangle if we are currently at clean (i,j)

dp[i][j][1] = num cells to clean manually in [0-1][j..n-1] rectangle if we are currently at clean (i,j), and cell (1-i,j) is already clean

dp[i][j][2] = num cells to clean manually in [0-1][j..n-1] rectangle if we are currently at clean (i,j), and cells (1-i,j) and (1-i,j+1) are already clean

I store the index of next clean cell in row i in k00,k01,k02; and of row 1-i in k10,k11,k12

Take a look at Ticket 16235 from CF Stress for a counter example.

Thank you so much! Can you please clarify on the point below as well though?

Your statement looks reasonable to me. Probably a typo in the editorial.

For problem E:

" When does the robot break? Let the robot currently be in the cell $$$(j,i)$$$ (0-indexed) and the next column with a dirty cell be $$$nxt_i$$$ (possibly, $$$nxt_i=i$$$). The robot breaks only if both $$$(1−j,nxt_i)$$$ and $$$(j,nxt_i)$$$ are dirty "

Shouldn't it break when $$$(1-j,nxt_i)$$$ and $$$(j,nxt_i+1 )$$$ are both dirty, and $$$( j,nxt_i )$$$ is clean ?

Sochu

yep, that's a mistake in the editorial

PaciukZvichainyi

BledDest!
Aho-Corasick is new algo for me and and read about this in cp-algorithms. They said if you need to find all strings from a given set in text, you need to use "exit links" to make code faster:

storing the nearest leaf vertex that is reachable using suffix links (this is sometimes called the exit link).
Link

As I see, you don't use this links or ncost array does this job?

BledDest

Yeah, ncost does the trick. Usually the exit links are helpful to traverse the whole path to the root along the suffix links without actually visiting non-terminal states of the Aho-Corasick (for example, this allows to find all occurrences of all strings we have to search for in $$$O(Ans)$$$); but in this problem, we are not interested in the actual occurrences themselves, only in their total cost, so precalculating it for each state is both easier and faster.

__Misuki

Can somebody explain problem E why it is not always optimal when the robot is at j-th row i-th column and $$$(1 - j, i)$$$ is dirty, $$$(j, i + 1)$$$ is clean, and we just always go to clean $$$(1 - j, i)$$$? I have been stuck by this for a long time but could not find any counter case :/