Идея: BledDest
Разбор
Tutorial is loading...
Решение 1 (awoo)
for _ in range(int(input())):
n, m = map(int, input().split())
print(n // 2 + 1, m // 2 + 1)
Решение 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 - Восстановление массива
Идея: BledDest
Разбор
Tutorial is loading...
Решение (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:])
Идея: BledDest
Разбор
Tutorial is loading...
Решение 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);
}
}
Решение 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)
Идея: BledDest
Разбор
Tutorial is loading...
Решение (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;
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (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';
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (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;
}
Can someone suggest problems similar to Div2 C: Card Game, which requires DP, Combinatorics and some thinking. Thanks!
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.
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)
In D, why does this greedy solution starting from the root and cutting whenever the depth exceeds the candidate does not work? TIA
Consider the following input
Input:
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 :)
is there any way to prove that you get the smallest number of edges if you start from bottom instead of top?
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
Can i ask a question？ why in editorial the dp[0][0][2] is 1 ？
my exact same doubt.
Someone please help with my solution to problem E:
https://codeforces.net/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 ?
yep, that's a mistake in the editorial
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:
As I see, you don't use this links or
ncostarray does this job?Yeah,
ncostdoes 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.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 :/
See this case:
You can see that if you clean the cell in (1, 3) (1-indexed, (row, col)) you will avoid doing some forced cleaning twice near the end.
If you are doing DP, probably you just need to add one more transition to take care of this.
Thanks you! It gets AC after I add this transition!
Can't figure out my mistake in problem D.
https://codeforces.net/contest/1739/submission/176283387
Take a look at Ticket 16293 from CF Stress for a counter example.
Thanks!
why my code for problem D always gives WA ? any help please .
Take a look at Ticket 16324 from CF Stress for a counter example.
Thanks a lot. it helps me to get my code accepted now. the problem is to clear visit and level arrays after each step from the binary search.
can anyone help me in D ?? 219602371
Take a look at Ticket 17054 from CF Stress for a counter example.
My output is same as the expected output in the counter example. Can you help me find another counter example
It's not. Not atleast on my machine, hence the counter example. Please check for undefined behaviours in your code.
Is the submission giving 2 on your machine ?