We (the setters) hope you liked the problems. Here is the editorial:
Tutorial is loading...
C++ solution
#include <iostream>
#define endl '\n'
using namespace std;
void solve()
{
int n;
cin >> n;
string s(200, 'a');
cout << s << endl;
for (int i = 0; i < n; ++i)
{
int u;
cin >> u;
s[u] = s[u] == 'a' ? 'b' : 'a';
cout << s << endl;
}
}
int main()
{
int t;
cin >> t;
for (int i = 0; i < t; ++i)
{
solve();
}
return 0;
}
Python solution
import sys
input = sys.stdin.readline
def main():
t = int(input())
for _ in range(t):
n = int(input())
a = list(map(int, input().split()))
mx = max(a)
ans = [ 'a' * (mx + 1) ] * (n + 1)
for i, x in enumerate(a):
who = 'a' if ans[i][x] == 'b' else 'b'
ans[i + 1] = ans[i][:x] + who + ans[i][x + 1:]
print('\n'.join(ans))
main()
Problem idea: dcordb
Solution idea: dcordb and Devil
Tutorial is loading...
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0);
int test;
cin >> test;
while (test--)
{
int n, k, l;
cin >> n >> k >> l;
vector<int> d(n+2, -k);
for (int i = 1; i <= n; ++i)
cin >> d[i];
set<tuple<int, int, bool>> mark;
function<bool(int, int, bool)> go = [&](int pos, int tide, bool down)
{
if (pos > n) return true;
if (mark.find({ pos, tide, down }) != mark.end())
return false;
mark.insert({ pos, tide, down });
tide += down ? -1 : +1;
if (tide == 0) down = false;
if (tide == k) down = true;
if (d[pos] + tide <= l && go(pos, tide, down))
return true;
if (d[pos + 1] + tide <= l && go(pos + 1, tide, down))
return true;
return false;
};
if (go(0, 0, false)) cout << "Yes\n";
else cout << "No\n";
}
return 0;
}
Problem idea: Devil
Solution idea: Devil
Tutorial is loading...
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0);
int test;
cin >> test;
while (test--)
{
int n, k, l;
cin >> n >> k >> l;
vector<int> d(n+1), safe = { 0 };
for (int i = 1; i <= n; ++i)
{
cin >> d[i];
if (d[i] + k <= l)
safe.push_back(i);
}
safe.push_back(n+1);
bool ok = true;
for (size_t i = 1; i < safe.size() && ok; ++i)
{
int tide = k; bool down = true;
for (int j = safe[i-1] + 1; j < safe[i]; ++j)
{
tide += down ? -1 : +1;
if (down) tide -= max(0, d[j] + tide - l);
if (tide < 0 || d[j] + tide > l) { ok = false; break; }
if (tide == 0) down = false;
}
}
if (ok) cout << "Yes\n";
else cout << "No\n";
}
return 0;
}
Problem idea: Devil
Solution idea: Devil
Tutorial is loading...
C++ solution
#include <bits/stdc++.h>
using namespace std;
const int Alp = 20;
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0);
int test;
cin >> test;
while (test--)
{
int n;
string a, b;
cin >> n >> a >> b;
bool bad = false;
vector<vector<int>> adj(Alp);
for (int i = 0; i < n; ++i)
if (a[i] != b[i])
{
if (a[i] > b[i])
{
bad = true;
cout << "-1\n";
break;
}
adj[a[i]-'a'].push_back(b[i]-'a');
adj[b[i]-'a'].push_back(a[i]-'a');
}
if (bad) continue;
vector<bool> mark(Alp);
function<void(int)> dfs = [&](int u)
{
mark[u] = true;
for (auto v : adj[u])
if (!mark[v])
dfs(v);
};
int ans = Alp;
for (int i = 0; i < Alp; ++i)
if (!mark[i])
dfs(i), --ans;
cout << ans << "\n";
}
return 0;
}
Problem idea: Devil
Solution idea: mnaeraxr and Devil
Tutorial is loading...
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0);
int test;
cin >> test;
while (test--)
{
int n;
cin >> n;
int x = 0;
vector<int> a(n);
for (auto &i : a)
{
cin >> i;
x ^= i;
}
if (x == 0)
{
cout << "DRAW\n";
continue;
}
for (int k = 30; k >= 0; --k)
if (x >> k & 1)
{
vector<int> f(2);
for (auto &i : a) ++f[i >> k & 1];
if (f[1] % 4 == 3 && f[0] % 2 == 0)
cout << "LOSE\n";
else
cout << "WIN\n";
break;
}
}
return 0;
}
Python solution
import sys
input = sys.stdin.readline
d = { 1: 'WIN', 0: 'LOSE', -1: 'DRAW' }
def main():
t = int(input())
for _ in range(t):
n = int(input())
a = map(int, input().split())
f = [0] * 30
for x in a:
for b in range(30):
if x >> b & 1:
f[b] += 1
ans = -1
for x in reversed(range(30)):
if f[x] % 2 == 1:
ans = 0 if f[x] % 4 == 3 and (n - f[x]) % 2 == 0 else 1
break
print(d[ans])
main()
Problem idea: Devil
Solution idea: Devil and dcordb
Tutorial is loading...
C++ solution
#include <bits/stdc++.h>
using namespace std;
const int Alp = 20;
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0);
int test;
cin >> test;
while (test--)
{
int len;
string a, b;
cin >> len >> a >> b;
vector<int> adj(Alp);
vector<vector<int>> G(Alp);
for (int i = 0; i < len; ++i)
if (a[i] != b[i])
{
adj[a[i]-'a'] |= 1 << (b[i]-'a');
G[a[i]-'a'].push_back(b[i]-'a');
G[b[i]-'a'].push_back(a[i]-'a');
}
vector<bool> mark(Alp);
function<void(int)> dfs = [&](int u)
{
mark[u] = true;
for (auto v : G[u])
if (!mark[v])
dfs(v);
};
int comp = 0;
for (int i = 0; i < Alp; ++i)
if (!mark[i])
dfs(i), ++comp;
int ans = 0;
vector<bool> dp(1<<Alp);
dp[0] = true;
for (int mask = 0; mask < 1<<Alp; ++mask)
if (dp[mask])
{
ans = max(ans, __builtin_popcount(mask));
for (int u = 0; u < Alp; ++u)
if ((~mask >> u & 1) && (adj[u] & mask) == 0)
dp[mask | 1 << u] = true;
}
cout << 2*Alp - comp - ans << "\n";
}
return 0;
}
Problem idea: Devil
Solution idea: mnaeraxr
Tutorial is loading...
C++ solution
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<vector<int>> mat(n, vector<int>(m));
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
cin >> mat[i][j];
vector<int> h(n * m + 1);
vector<int> v(n * m + 1);
for (int i = 0; i < n; ++i)
{
int a = 0;
for (int j = 0; j < m; ++j)
a = max(a, mat[i][j]);
h[a] = 1;
}
for (int i = 0; i < m; ++i)
{
int a = 0;
for (int j = 0; j < n; ++j)
a = max(a, mat[j][i]);
v[a] = 1;
}
vector<vector<int>> fin(n, vector<int>(m));
queue<pair<int, int>> q;
int x = -1, y = -1;
for (int u = n * m; u >= 1; --u)
{
x += h[u];
y += v[u];
if (h[u] || v[u])
{
fin[x][y] = u;
}
else
{
int qx, qy;
tie(qx, qy) = q.front();
q.pop();
fin[qx][qy] = u;
}
if (h[u])
for (int i = y - 1; i >= 0; --i)
q.push({x, i});
if (v[u])
for (int i = x - 1; i >= 0; --i)
q.push({i, y});
}
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
cout << fin[i][j] << " \n"[j + 1 == m];
return 0;
}
Problem idea: gilcu3
Solution idea: gilcu3 and mnaeraxr
Tutorial is loading...
C++ solution
#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
int main()
{
ios::sync_with_stdio(false), cin.tie(0);
string s; cin >> s;
int n = s.length();
vector<int> dist(n);
for (int i = 0; i < n; ++i)
if (s[i] == '0') dist[i] = (i ? dist[i-1] : 0) + 1;
vector<int> dp(n + 2), nxt(n+2, n);
auto get = [&](int i) { return nxt[i] < n ? dp[nxt[i]] : 0; };
for (int i = n-1; i >= 0; --i)
{
dp[i] = ((dist[i] <= dist.back()) + get(0) + get(dist[i] + 1)) % mod;
nxt[dist[i]] = i;
}
int ans = n;
if (nxt[0] < n)
ans = ((long long)get(0) * (nxt[0] + 1)) % mod;
cout << ans << "\n";
return 0;
}
Problem idea: Devil
Solution idea: Devil and antontrygubO_o
Tutorial is loading...
C++ solution
#include <bits/stdc++.h>
using namespace std;
template<typename C, typename R = C>
struct dinic
{
typedef C flow_type;
typedef R result_type;
static_assert(std::is_arithmetic<flow_type>::value, "flow_type must be arithmetic");
static_assert(std::is_arithmetic<result_type>::value, "result_type must be arithmetic");
static const flow_type oo = std::numeric_limits<flow_type>::max();
struct edge
{
//int src; // not needed, can be deleted to save memory
int dst;
int rev;
flow_type cap, flowp;
edge(int src, int dst, int rev, flow_type cap, int flowp) :
/*src(src),*/ dst(dst), rev(rev), cap(cap), flowp(flowp) {}
};
dinic(int n) : adj(n), que(n), level(n), edge_pos(n), flow_id(0) {}
int add_edge(int src, int dst, flow_type cap, flow_type rcap = 0)
{
adj[src].emplace_back(src, dst, (int) adj[dst].size(), cap, flow_id++);
if (src == dst) adj[src].back().rev++;
adj[dst].emplace_back(dst, src, (int) adj[src].size() - 1, rcap, flow_id++);
return (int) adj[src].size() - 1 - (src == dst);
}
inline bool side_of_S(int u) { return level[u] == -1; }
result_type max_flow(int source, int sink, vector<flow_type> &flow_e)
{
result_type flow = 0;
while (true)
{
int front = 0, back = 0;
std::fill(level.begin(), level.end(), -1);
for (level[que[back++] = sink] = 0; front < back && level[source] == -1; ++front)
{
int u = que[front];
for (const edge &e : adj[u])
if (level[e.dst] == -1 && flow_e[rev(e).flowp] < rev(e).cap)
level[que[back++] = e.dst] = 1 + level[u];
}
if (level[source] == -1)
break;
std::fill(edge_pos.begin(), edge_pos.end(), 0);
std::function<flow_type(int, flow_type)> find_path = [&](int from, flow_type res)
{
if (from == sink)
return res;
for (int &ept = edge_pos[from]; ept < (int) adj[from].size(); ++ept)
{
edge &e = adj[from][ept];
if (flow_e[e.flowp] == e.cap || level[e.dst] + 1 != level[from]) continue;
flow_type push = find_path(e.dst, std::min(res, e.cap - flow_e[e.flowp]));
if (push > 0)
{
flow_e[e.flowp] += push;
flow_e[rev(e).flowp] -= push;
if (flow_e[e.flowp] == e.cap)
++ept;
return push;
}
}
return static_cast<flow_type>(0);
};
for (flow_type f; (f = find_path(source, oo)) > 0;)
flow += f;
}
return flow;
}
result_type max_flow2(int source, int sink, vector<flow_type> &flow_e)
{
result_type flow = 0;
std::function<flow_type(int, flow_type)> find_path = [&](int from, flow_type res)
{
level[from] = 1;
if (from == sink)
return res;
for (int &ept = edge_pos[from]; ept < (int) adj[from].size(); ++ept)
{
edge &e = adj[from][ept];
if (level[e.dst] == 1 || flow_e[e.flowp] == e.cap) continue;
flow_type push = find_path(e.dst, std::min(res, e.cap - flow_e[e.flowp]));
if (push > 0)
{
flow_e[e.flowp] += push;
flow_e[rev(e).flowp] -= push;
if (flow_e[e.flowp] == e.cap)
++ept;
return push;
}
}
return static_cast<flow_type>(0);
};
for (bool ok = true; ok; )
{
int it = 0;
std::fill(edge_pos.begin(), edge_pos.end(), 0);
for (flow_type f; ; ++it)
{
std::fill(level.begin(), level.end(), -1);
f = find_path(source, oo);
if (f == 0)
{
if (it == 0) ok = false;
break;
}
flow += f;
}
}
return flow;
}
int flow_id;
private:
std::vector<std::vector<edge>> adj;
std::vector<int> que;
std::vector<int> level;
std::vector<int> edge_pos;
inline edge& rev(const edge &e) { return adj[e.dst][e.rev]; }
};
const int inf = 25;
struct edge
{
int u, v, w;
};
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
void relabel(int n, vector<edge> &e, int k)
{
shuffle(e.begin() + k, e.end(), rng);
vector<vector<pair<int, int>>> adj(n);
for (auto &i : e)
adj[i.u].push_back({ i.v, &i-&e[0] });
vector<edge> ne = e;
vector<int> id(n, -1);
id[0] = 0;
id[n-1] = n-1;
int sz = 1, esz = k;
function<void(int)> dfs = [&](int u)
{
for (auto &v : adj[u])
{
if (v.second >= k)
{
ne[esz++] = e[v.second];
v.second = -1;
}
if (id[v.first] == -1)
{
id[v.first] = sz++;
dfs(v.first);
}
}
};
dfs(0);
for (auto &u : adj)
for (auto v : u)
if (v.second >= k)
ne[esz++] = e[v.second];
for (int i = 0; i < n; ++i)
if (id[i] == -1)
id[i] = sz++;
e = ne;
for (auto &i : e)
{
i.u = id[i.u];
i.v = id[i.v];
}
}
struct masks
{
int x, cost;
vector<int> flow_e;
bool operator<(const masks &o) const
{
return cost < o.cost;
}
};
typedef std::chrono::_V2::system_clock::time_point timepoint;
timepoint get_time()
{
return std::chrono::high_resolution_clock::now();
}
int get_elapsed(timepoint t)
{
return std::chrono::duration_cast<std::chrono::milliseconds>(get_time() - t).count();
}
int main()
{
ios_base::sync_with_stdio(0), cin.tie(0);
int n, m, k, q;
cin >> n >> m >> k >> q;
vector<edge> e(m);
for (auto &i : e) cin >> i.u >> i.v >> i.w, --i.u, --i.v;
vector<int> mask(1 << k, -1);
relabel(n, e, k);
dinic<int> d(n);
for (int i = 0; i < m; ++i)
d.add_edge(e[i].u, e[i].v, ((i < k) ? inf : e[i].w));
vector<int> flow_e(d.flow_id);
for (int i = 0; i < k; ++i)
flow_e[2*i] = inf;
mask[0] = d.max_flow(0, n-1, flow_e);
priority_queue<masks> pq;
pq.push({ 0, 0, flow_e });
while (!pq.empty())
{
int x = pq.top().x;
flow_e = pq.top().flow_e;
pq.pop();
for (int j = 0; j < k; ++j)
if ((~x >> j & 1) && mask[x | 1 << j] == -1)
{
auto n_flow_e = flow_e;
n_flow_e[2 * j] = 0;
auto t = get_time();
mask[x | 1 << j] = mask[x] + d.max_flow2(0, n-1, n_flow_e);
pq.push({ x | 1 << j, get_elapsed(t), n_flow_e });
}
}
vector<int> cut(1 << k), bit(1 << k);
for (int i = 1; i < 1 << k; ++i)
bit[i] = i & -i;
const int U = (1 << k) - 1;
while (q--)
{
for (int i = 0; i < k; ++i)
cin >> cut[1 << i];
int ans = mask[U];
for (int i = 1; i < 1<<k; ++i)
{
cut[i] = cut[i ^ bit[i]] + cut[bit[i]];
ans = min(ans, cut[i] + mask[U ^ i]);
}
cout << ans << "\n";
}
return 0;
}
Problem idea: mnaeraxr
Where are the time complexities?
I usually find understanding a solution easier when the time complexity is indicated with the solution.
Amazing contest, nonetheless.
Video Editorial of B1 and B2: Koa and the Beach
Nice explanation, good to see the use of whiteboard which is rare nowadays.
Lost the entire interest after seeing problem statement of B1 :(
That's why people moved to C
C and D protected my life
seriously dude, you didn't even participate.
It's Beyond Science
I think you got it.
Maybe he/she uses a fake account lol
I don't get the point of making many accounts. why would you make an alt account just to post bullshit?
seriously dude, he didn't even tell you.
In Div1D, the time complexity is $$$O(nm)$$$, so the limits could have been higher as I think of it.
Was it intentional (so that one would think of it more as a $$$O(n^3)$$$, flow-like problem, for example)? Or possibly a change of mind -- maybe wrote a cubic solution, found the square one after?
If you push the limits to as high as possible that will fit within TL, you may be unnecessarily giving away info to the contestants. In this case making it so that $$$O(nm)$$$ is the only complexity that fits within TL tells you that the algorithm must be of that complexity. Imo it makes sense to leave it this small so it remains ambiguous (and still doesn't let any inefficient solutions pass).
Long statements + weak pretests
Problem setter thinks he is very smart but he is a kid, don't know who allowed him to set problems.
The contest was good and I liked it even tho I couldnt solve any problem, I enjoyed the 2 hours. Speak for yourself.
It's not about solving problems, just look at the description & difficulty of the problems and points assigned to that problems, Totally unfair. C-1750, B-500/700.
Devil I think you made undirected graph in solution of div2C :)
graph will be undirected only , since we need to find size of the connected component , thus we need to visit all the nodes (to mark them and thus to find size of the connected component) . It's "connected" not "strongly connected" in editorial .
lost interest in this round due to B problem statement
Graph solution for problem div2 C (div1 A) is beautiful . Can some tell other approach without using graphs.
If any character in $$$A$$$ is greater than $$$B$$$ at a particular index then it is not possible to transform $$$A$$$ to $$$B$$$.
$$$Rule$$$ : Do not touch the indices in which $$$A$$$ and $$$B$$$ match.
And now follow the following process
First we look at the indices with contain $$$"a"$$$ in the string $$$A$$$ and look at the same indices in $$$B$$$ and let minimum among those indices in $$$B$$$ be $$$X$$$. Now replace characters in $$$A$$$ in those indices to $$$X$$$. Now one operation is performed. Similarly repeat the process to $$$"b"$$$, $$$"c"$$$ $$$.....$$$ $$$"t"$$$
Yes,I used set to solve that problem --> Link
It is obvious that, if the first string has a character with higher value than the second string in at least one position, there is no solution.
Now for the non trivial case: If we need to transform at least one instance of character x into a higher character y, then there is no harm in transforming ALL instances of x into y (it is still going to be one move), as long as we consider the potential y characters in increasing order (otherwise we might leap over relevant characters and increase some instances of x too much). While there potentially is a benefit, i.e. reduction of the number of necessary moves in cases like the following example: for strings aab and bcc we need to transform a -> b, a -> c, b -> c, and when transforming both a's to b then both b's to c, we achieve the desired result without the need to spend an extra move for a -> c transformation. The potential x characters should be considered in increasing order too, to avoid making a move before it gains full potential accumulated from potentially transforming lower characters into x first.
Fill a matrix M with 20 rows and 20 columns as follows M[x][y] = true, if at least on instance of the x-th character ultimately needs to be transformed into the y-th character, false otherwise. Only the half of the matrix strictly above the diagonal is of interest, because if M[x][y] = true for some x, y where x > y, then we are back at the trivial case, and if x = y, there is no transformation required.
Now iterate over potential x-th characters in increasing order, for each iterate over potential y-th characters, where y > x. For the first encountered M[x][y] = true entry (if any), count plus one move, and iterate over the rest of the entries in the same row, i.e. over z-th characters for z > y. For each entry M[x][z] = true, make M[y][z] true, as this is simulating transforming all instances of the x-th characters into the y-th, while keeping track into what characters they need to be transformed ultimately.
P.S. Really, this approach is not that far away from the graph solutions, since the matrix can be seen as an adjacency matrix of the graph. It is a matter of interpretation and I did not have a graph in mind when coming up with the solution.
C++ std::priority_queue is also a nice way to solve this problem
dcordb can you please you spoiler to display editorial (blogs), it will be more convenient like previous editorials.
Solution of div1C only gives the answer but doesn't really explain how one might come up with that in the first place, so I'll try.
First observation is having lots of letters in the first string is bad for us, so we want to join letters as much as possible. That is, suppose the solution does operations A->B, followed by A->C. We could have changed all As to Bs in the first operation to do A->B, B->C instead. B->A followed by C->A can also be replaced by B->C, C->A.
From this, we might intuit that the solution consists of one very long chain in which we have a "snowball" collecting all original letters into the same letter.
If the graph has no cycles, then such a snowball can simply follow the topological sort of the DAG (this is div1A). If there are cycles, then some vertices will be visited more than once. If you know that a vertex is going to be visited more than once anyway, you might as well put it as the first and last vertices in the order, since this guarantees that vertex can reach/is reachable by all others.
What about the vertices you only visit once? Clearly there cannot be any cycles between them, so they are a DAG (and as we know any DAG can be solved with the topological sort). So the solution looks like: visit some set of vertices S, do topological sort on the rest, visit S again. To minimize the number of operations we want the DAG to be the maximum possible.
Really, thanks.
Question : C2 Koa and the Beach
Can someone explain why the below test case below should have "NO" as a answer:
20 26 32
31 27 14 7 2 23 22 21 19 27 31 12 23 31 0 11 28 20 31 30
I don't like editorial of 1384B2 - Koa and the Beach (Hard Version) So I'll write my own. I think it should be easier.
Let s(p, t) is answer on question "is there way to reach position p at cycle of tide t?". I'll make numbering of tide cycle in following way [k, k-1, k-2..., 1, 0, 1, 2 ... k-1]. It will be much easier to understand later.
So, now obviously, if 0 is island, then s(0, t) is true for any t. Next, suppose some s(p, t) is true, then if we get this existing way to reach p at cycle time t and just standby there, eventually we can either drown or stay infinitely. Obviously, if we drown then it is because tide increased. This means that for all i up to some point x value of s(p, i) is also true, unless you can stand there forever. So either whole segment from i to x is true, or all s(p, t) is true for this p. Position p where you can stand forever lets call safe position similarly with editorial.
Now important part: we can drown only when tide increase, highest allowed tide is easy calculated. And that's why cycle of tide I defined in the way above, with increasing in the end. Because higher allowed tide — longer we can stay. And, this also means that cycle time with "bad" level of tide is in prefix and suffix of cycle. This all means that for any position p there is first (lowest) t for which s(p, t) is true. And, in this notation all possible cycle time for position p gives range from first time to the time when highest possible tide is reached during rise of tide. Thus, to solve the task we only need to find for each position p first t when s(p, t) is true.
Now, consider three cases:
So, for each position we just update earliest t, and total time complexity is O(n). 87931302
Video Editorial of B1 and B2: Koa and the Beach
I liked the way you explained it. Nice and clear. But I don't like the fact that this problem was kept at B.
could you explain why test case 3: 4 3 4 0 2 4 3 has a solution(i.e Yes)?
On position 0 we can stay forever — it's island, so we should move on fall, so we move at t (cycle time) at 0 and arrive at t = 1 on position 1 because there will be 0+2 height which is less than 4. Also, at position 1 we can stay forever, so we should move at fall again. So, we will wait until t = 0 again and move at t = 0 and if we move then on next position we will have 2+2 which is alright, but we can't stay here forever because 2+3 > 4. This means that we now on falling tide and unsafe position. We need to move next as soon as possible. If we move now to position 2 we will have 4 + 1 height and drown, so we should wait once and after move we will have 4 + 0 height which is alright. Now, at position 2 we are in unsafe position and tide is rising, so we should move now (without any "if", because situation may only become worse). Now we move to position 4 and have height 3 + 1 which is alright. Similarly, on position 4 we are in unsafe position and tide is rising so we should move now, and successfully reach end. Each of this actions give earliest t for each positions, so earliest t array is:
0, 1, 3, 4
, and corresponding tide:3, 2, 0, 1
.Next time please try to make smaller readable problems. Appreciated your efforts.
The largest directed acyclic graph can be computed using dynamic programming in n*2^n.
I remember a nice CF blog on this, could anyone point it out.
DP solution to B1:87940952. dp[i][j]--> Can we be at location i at time j? So, if any of dp[n][j] is true, we can reach the island.
i might be late, but can you just tell me how did you calculate the upper bound of second state of dp? i mean the time factor...
EDIT: Got it!
My Code is Exactly like Editorial's.
Can anyone Please tell me why is gives wrong for this simple case, ALTHOUGH it's giving correct output in my local Compiler.
Tese Case: 1
3
ddd
ddd
My Local Output: 0
Cf Compiler: 1
You don't clear your global arrays after printing -1.
Oh Crap!
I've been stuck here like since forever. Thanks !
I found the following trick to solve Div2 B with simple implementation. The idea is like sliding window and updating the initial interval of $$$(-k, k)$$$ that corresponds to decreasing tide $$$(-k, 0)$$$ and increasing tide $$$(0, k)$$$. This way of set up simplified the implementation so much, but unfortunately, I came up with this at the end of the contest. Here's my solution
Kudos to testers and those who arranged the problems in order of difficulty.
Solution videos for people who prefer to have things explained visually are available here.
Can B1 use array to memory state?
It's ok!
How is my idea for Div1A different from the editorial?
test yếu anh ơi
In Div2C.
For the testcase 1 4 aacb bcdd
The topological order is acbd But we can't select the each pair of consecutive nodes because c-->b is not possible.
Am i missing something?
I think it's abcd.
aacb -> bbcb -> bccc -> bcdd
I don't know but gave you +1 for ma boi killua
Although the quality of problems is quite good, but the score distribute is not reasonable. Div2 B that cost me 1 hour time only values 500+750 score. Div2 C is quite easy, but values 1750. I solved 5 problems but get a lower rank than someone solved 4 problems because of this score distribute. Sad~
In the code of div1 E, the DP transition is
I understand
get(0)
andget(dist[i]+1)
are the two cases in the editorial, but what does(dist[i] <= dist.back())
mean ?Oh, I see. It seems that
(dist[i] <= dist.back())
means let $$$w$$$ just end there !Yes it does that, it simply checks if string $$$s$$$ can end at $$$i$$$. For future references here is same solution that handles that part more clearly:
Here I removed zeroes at the end of $$$s$$$ (and multiply by this, plus $$$1$$$ to ans), and replaced that transition with an easier one to understand (it. checks if $$$s$$$ can end at $$$i$$$ with a $$$1$$$).
Why w end there must meet this condition?
I think i understood it, your solution is more clear.
I find that if s="0", the solution will RE because it visited
nxt[dist[0]+1]
(dist[0]+1=2) and the size of nxt is $$$2$$$ !Yes sorry, it will RE, it was an error modifying it to post it here, but model solution is correct.
In Div1E/Div2C, what is the motivation for: "and the answer is $$$2⋅n−|LDAG|−1$$$"?
ffao explained it
That's bad when people have to look for explanations for editorials in random comments in random places of the blogs.
Why the simple greedy solution isn't mentioned in editorial for Div2C?
If you are keeping python as a submission language then please do some homework and check the comparative time it's gonna take in python or else change codeforces to cppforces.
Codeforces is already cppforces. Plenty of problems can't be solved using Python.
Just tell me why can't be solved. Are there any logic that python doesn't support or recursion call stack that cannot be increased. It's all about time. You just have to increase the time limit for python in order to make python compatible for solving the same logic.
You want to have all the benefits python offers and no drawbacks. Obviously this won't do. Python is slower and that's the price you pay for its flexibility and coding speed
Also, learn to use pypy. I see that you used vanilla python, that's rarely a good idea in cp. Pypy is hardly ever not enough for the first d2 problems if you have a correct algorithm
That's just the way things are currently, where C++ has a big advantage over other languages. I'm not saying that it's right or wrong, but until this changes you'll probably be better off switching to C++.
Case: x%4 == 3 if y%2=1 the first player takes one 1 and the game now is exactly the previous case with the first player as the second player. I think the author means the first player takes first 0 and then the game is exactly the previous case . Previous Case: x%4 == 3 && y%2 == 0 Or Maybe i am too naive to understand the Author's logic :)
Thanks, it's fixed now :)
Can anyone explain how we can solve Div2C using DSU?
IMO in Div.2 only problem C and maybe D had somewhat of a proper score allotted to it. Rest all should have had a higher score allotted to them. Especially B2.
For String Transformation 1, I am really struggling to understand the answer after the 2nd sentence. I would like to understand this graph solution, could anyone please explain it in more detail?
This is how I solved Div2B
let h be an array where
h[i] = l - d[i]
Then divide h into segments [L, R] where
h[L] >= k
h[R] >= k
h[i] < k (L < i < R)
For each segment check if exist 2 indices i and j such that
i + h[i] < j - h[j]
then there is no solution. Otherwise, a solution existsShould it be:
Yes, it should be.
Fixed, thanks.
For DIV2C/DIV1 A
For this sample input
1
7 dgdfjjk
lhejkkl
We can transform in just 5 steps,but author's solution is showing 6.
Operations 3-e
2-h
4-j
1,5,6 — k
1,7 — l
am I missing something?
1, 5, 6 — k is not correct. 1 is d while 5 and 6 are j.
Thanks,it seems I didn't read the problem statement properly
Can someone please explain me the graph solution of problem 3. I am not able to understand it from the editorial.
div 2 C seems to be a standard ques!! if yes then can you plz tell me more about this type of question!
Maybe you'll find it useful https://codeforces.net/blog/entry/80593?#comment-668966 By the way, can you please tell how the number of transformations required for abcb to tsrs is 3 (as there are 3 connected components?)
a to t in 1 move , b,b to s,s in 1 move and c to r in one move so total 3 moves requires
i have 2 solutions for this problem
1 (https://codeforces.net/contest/1384/submission/88019936) is what i did during contest and its kind of general solution i guess and
the other one(https://codeforces.net/contest/1384/submission/88049338) is very interesting solution
For C1 my approach seems to be different from what the comments are mentioning. (*I also don't seem to have a proper proof for it but it seems to work intuitively and would be nice if someone wants to look into this*)
I took characters of string B and sorted them in the increasing order. (Let's call the smallest value of such a sorted sequence as SML)
My claim is that if we try to change the characters of string A whose character in the corresponding same position in B is same as SML or once such character is found then every occurence of the same character in A will be changed to SML and the number of such distinct characters which were changed to SML will be added to our final answer.
Now first turn is over SML will pick the next smallest element and will redo the above again.
Finally all characters in A will be changed to the ones in B and the answer will be minimum.
I used set of pairs to implement it.
If there are any counters to the above explanation they are most welcome. (Since I am not sure why my approach actually works besides few samples I checked with pen and paper)
https://codeforces.net/contest/1384/submission/88045399
In Div.1F, the time limit seems so tight after some very strong hack testcases were added, and it's so difficult to pass them.
By the way, can anyone tell me how to get max flows quickly.
I have some questions on 1383B - GameGame : why we dont have to consider higher bits when we're processing the first bit that the number of ones is odd? (or : why we can turn these numbers into an array of $$$x$$$ ones and $$$y$$$ zeros? should we consider the influences of higher bits (though their number of ones is even) ?)
i'll appreciate it if you can explain these questions to me :)
If number of ones is even for any higher bits. Then irrespective of distribution, both players will have either odd or both players will have even number of bits . So both will end up having same value(because of same parity) for that bit. This is the explanation I gave to Myself .
many thanks!
If the number of $$$1$$$ is even for a bit, then the final result could be only:
which will always make a tie on that bit. The order doesn't matter.
It could be confusing, so you can have a simulation.
thx!
In div 1 E editorial, I don't understand this part:
"if the $$$(j+1)$$$-th character in $$$w$$$ is 0, and we have $$$k$$$ zeros after the last 1 in $$$w$$$ find the next block of $$$k+1$$$ zeros in $$$s$$$, (ie first $$$i'>i$$$ such that for each ($$$0\le k'<k$$$) $$$s_{i'-k'}=0$$$)"
Why do we look for a block of $$$k+1$$$ zeros if we only need $$$k$$$ zeros? Also, the part in the parenthesis contradicts this because there $$$0\le k'<k$$$ is an interval with only $$$k$$$ numbers in it. However, the model implementation uses
get(dist[i]+1)
which is also $$$k+1$$$. So which one is it and why?Oh that was a typo, as it says in editorial and as you can see in sample solution, if you have a block of $$$k$$$ zeros, and you want another $$$0$$$, you should search for first block of at least $$$k+1$$$ zeros.
For example: $$$s = ...100\underline{0}100000$$$ you are on the underline (suppose $$$w = ...1000$$$) and you want another zero, for this you can merge $$$0001$$$ with some previous $$$1$$$ (remember we ensured that one always exists) and search for next block of at least $$$4$$$ zeros (the merge would look like $$$...10001|0000...$$$). In this way you would have $$$w = ...10000$$$.
Thanks, I understand the greedy part now but am now having trouble understanding the DP. The editorial says
"Let $$$dp(i)$$$ be the number of strings that we can obtain using the last $$$n-i$$$ characters from $$$s$$$"
However, running the model code tells me the dp states used in it are not exactly the same. It gives the following values for these suffixes:
Note that the actual number of things you can construct from
011100
is 18, not 9. It should be double the number of things you can construct from11100
because you can choose whether or not to put the0
at the beginning. Could you explain what the dp states in the solution actually represent? Thanks!Yes, the dp is well defined in each one, remember that at the end we use $$$dp(i)$$$ where $$$i$$$ is the position of the first one.
If it helps, try thinking about it in this other way (this is how I first solved):
Let $$$dp(i, c)$$$ be the number of strings we can obtain from last $$$n - i$$$ characters of $$$s$$$ such that they start with exactly $$$c$$$ ($$$c \ge 0$$$) zeros. The transitions are the ones in editorial.
Then you can notice that you don't need second state if at the transition you force to add $$$k$$$ ($$$k \ge 0$$$) zeros and then a $$$1$$$.
Oh and about dp giving $$$9$$$, well remember you had a zero before first $$$1$$$, so you should multiply by a $$$2$$$ (ie. ans is $$$dp(2) \cdot 2$$$).
I have a feeling that we might misunderstand that text for
dp[i]
. A better example of explaining the mismatch would be:Notice
i=5, s[i]=0
, according to the text, it is the number of string we could make using lastn-i=10-5=5
characters. This number should be 8 instead of 6 (following the def. ofdp
)I think a better way to explain
dp[i]
is the following:dp[i]
is the number of strings that you make where you must keep all preceding consecutive 0s whens[i] = 0
, otherwise (ifs[i]=1
), it's the number of string that you can make to so that you keep thiss[i] = 1
.This explanation is kind of echoing with the greedy method in the tutorial.
In the example above,
dp[5]
is the number of extensions where you must keeps[4]
ands[5]
and you try to extend this with a 1 or a 0 (corresponding to theget(0)
and theget(dist[i]+1)
component). More specifically, whens[i]
is not followed by a 0 (like in the case fors[5]
), you have to seek for the consecutive 0 block that is large enough. And finally, you can extend it with nothing if the ending0
block is large enough or you are extending a1
. That's thedist[i] <= dist.back()
component.This is what dcordb was talking about for the leading 0s I believe.
I hope the tutorial is technically clearer for the ignorant like me :P. But I think the problem and the solution are both quite good and I very much appreciate the efforts of the problem setter.
In the solution for b1 what does this code correspond to? function<bool(int, int, bool)> go I mean, I understand the meaning but I haven't seen this kind of syntax till now.......
It is the return type of a lambda expression.
ok thanks!
It's a lambda function in C++. Read about them Here.
Will do thanks!
Despite what the other commenters say it's actually not a lambda! It's a
std::function
.A
std::function
does type erasure magic and you can assign lambdas, function pointers, and callable structs (anything that is callable) to it. This type erasure comes at a cost.To actually have a lambda function you need to assign it to an auto variable. The type of the lambda is generated at compile time and you can't know it/type it yourself.
Edit: For clarity. The right hand side of the assignment is a lambda function. But it gets converted to a
std::function
in the assignment.All right...
Problem B1 : How the depth increased by time t = (t % 2k) ?? If so then the depth can be increased more than k which is not possible according to the statement. Help please...
its more like depth increases by A[t], where t = (t%2k), take for example k = 3 array A = [0,1,2,3,2,1] so at time t = 0, depth increases by A[t%2k] = A[0]. similary at t = 4, depth increases by A[4%6] = A[4] = 2.
include<bits/stdc++.h>
using namespace std;
typedef long long ll ;
set<tuple<ll, ll, bool>> mark ;
bool dfs(ll n, ll pos, ll &tide, bool &down , vector &d , ll k , ll l) {
}
int main(){ ll t ; cin>>t ; while(t--){
}
I am struggling why my code is showing wrong ans
next time post submission link and what task
my dp solution for B1 using 2 states — https://codeforces.net/contest/1384/submission/88165283
I want to verify time complexity — I think it should be n * k as for every index k times are possible i.e. earliest you could reach is i + 1 and latest you could reach is i + k
1383E - Strange Operation I think my understanding of DP is very good. But even I had trouble with editorial even thought I solved it in the first place! So, for those who want to learn all that magic few people understand, I'll try to explain it as much as I can.
For completeness, I'll repeat some of things from editorial. First thing we need to know is: maximum of bits is equivalent to bitwise OR. And result of any sequence of merging two bits is equivalent to: pick set of segments, replace them by their bitwise OR.
Now, suppose we have feeling that this task should be DP, then what our thoughts? Well, main thought: what is state? State should be all possible way to do something. And here is a trouble: how can we make sure that all those ways are different? The state itself should guarantee that. And mind is blowing when you think that this one can be vanished or keeped, similarly zero can remain or keeped. And here where I stuck. Then, I had idea to have dp based on fixed one, but it doesn't help, because even if I knew how many ones I have before, I had no idea how to make sure all sequences are different.
Honestly, here I stuck, but I had feeling that I should somehow know that my sequences are different for sure. But I had no idea. So I read beginning of editorial. Very beginning. To get a hint. And this hint was enough. Hint was a bit other, but here is hint I propose for all of you who read this: for any string we can make, we should be able to construct it, so find out how to check is it possible to construct given string.
Task from now is: find out algorithm for checking: can we make from sequence $$$s$$$ sequence $$$t$$$ . That's it. And solution is easy: for each part of $$$t$$$ we will pick first place where we can make it in $$$s$$$. So, we will start from empty sequence, and append bits to it. This leads to two cases: if next bit we need is 1 then we just find next unused 1 in $$$s$$$. If next bit is 0 then we need to find first place with enough number of zeroes we want, because in $$$t$$$ we can only shrink number of zeroes. There is one corner case: we can't skip anything if we don't have ones yet, but we can deal with it separately.
Now, crucial observation: sequence of steps of this greedy algorithm is deterministic, so any different input t for fixed s gives certain sequence of steps. I didn't say unique. It's true but it's much harder statement than I want to prove first. First, we will change greedy slightly for easier analysis.
Let's change greedy in following way: for next bit 0 instead of looking for group of enough size we will look for first zero instead. And if you can't get next zero without remove of previous one — we just forbid this action. It's a bit vague words so I'll provide example:
Here we can't make second 0 because we need to somehow jump to next group of zeroes. So, my initial solution had this as a bug in idea, but it is good way to explain I think. Why? Well now we have addition of 0 and 1 single bit by bit and we able to tell can we make $$$t$$$ by steps of this greedy algorithm. You can think of it as if we count all different sequences of bits which can be made by this greedy algorithm. We will solve this first, because it's easier and it will give idea how to solve initial task.
Now, if we look carefully on how this greedy algorithm works we will see that depending on next bit (zero or one) we make different jumps in $$$s$$$. Thus, we can draw arrows from each cell: one arrow where we land if next digit is 0, and one arrow where we land if digit is 1. Some of cells don't have jump by zero (because we already have 0 and we can't remove 0 and arrow by zero means we want zero, but next symbol in $$$s$$$ is not 0 so we should remove trailing zeroes and make new group but we decided to forbid it, because it's simpler version) This is graph of transitions. And crucial thing is: in this graph each edge from vertex is jump by different next bit. This means that any unique path corresponds to unique bit string. The number of different paths in graph like that is easy to calculate, because this graph is top sorted. So
I don't know if anyone else use similar terminology. push is when you add influence into next position, and pull is when you grab around values. Backward and forward makes sense only if you have ordering like in our case.
Now two things not covered yet: we haven't talk about ending. We can end at any 1 (by bitwise OR of everything else in the end). And we can end at zero if it's in the end. Also, we need to take into account reaching first 1. So total number of unique sequences of bits of this greedy algorithm is: number of ways to get first 1 multiplied by number of unique paths to ones or trailing zeroes.
At last, back to original problem. Note: I don't want to explain my solution in details. It's not important. My idea to fix this was using greedy algorithm we had before modification was made. Instead of picking first zero I just need to make all possible ways of jumps by number of zeroes. It's up to $$$|t|$$$ number of arrows from each cell. Each arrow is where I would land if I need exactly certain number of zeroes. To deal with it I postpone jumps into next groups of zeroes. Actually it was postpone addition of values of dp instead of jumps itself. And to avoid big amount of postponed addition I used stack and it did work. By the way it was forward push dp, and it was only over 1 bits. 88154272
Now, instead of my idea, we will do a bit different thing. Now we can see how each sequence of bits without skip of groups of zeroes is possible to make. All we need is somehow if we don't have enough zeroes, somehow we want be able to go to the next group of zeroes. And here comes the trick! If we stand in third zero in group, like this:
then there is only one way to reach third zero in group: to start from first one and make step by zero arrow twice. Why? Well, because all arrows by 1 is pointing into 1. It means, that by index of zero in group we know exact number of trailing zeroes we have! And, it means, if we stand in last zero in group and want one more zero, then we need group with at least one more zero. And after addition of this additional zero we also know how many zeroes we will have, so we know to which zero we need to make arrow by zero. This zero where we will make arrow — will have number of zeroes strictly determined by position in its group. So everything match. Index of zero is at the same moment: part of state and how many trailing zeroes we already have. Basically each position define last used bit for merge and number of trailing zeroes at once. And that is core of the solution. All what is left is to take care of zeroes in front of string and in end of string.
Now, regarding the code in editorial. It is just backward pull dp (in my terminology) over graph I just described. $$$dist$$$ is number of zeroes before (index of zero in group, 0 if it's bit 1). $$$nxt$$$ is position of next zero at certain distance (with certain index of zero).
I might be too late to the party, but I am presenting my own solution for 1E anyway.
Let's solve the problem where the first and last character are both
1
, because the beginning and ending zeros can be counted and multiplied into the final answer trivially.Between any two consecutive
1
's, let's count the number of0
's, and store it in an arraya
. So we can "compress" our string into $$$\texttt{1 } a_1 \texttt{ 1 } a_2 \texttt{ 1 ... 1 } a_k \texttt{ 1}$$$, where $$$a_i$$$ is the occurrence of0
's between the $$$i^{th}$$$1
character and the $$$(i + 1)^{th}$$$1
character. The problem can be then transformed into: for each element $$$a_i$$$, replace it with a value from $$$0$$$ to $$$a_i$$$, or remove the element from the array completely. Count the number of possible arrays that can be made this way.I denote $$$dp_i$$$ to be the number of different arrays that end in the value $$$i$$$, and denote $$$tot$$$ to be the total number of different arrays. Clearly $$$tot$$$ would be our answer, and $$$tot = (\sum{dp_i}) + 1$$$. Let's maintain this $$$dp$$$ and $$$tot$$$.
Iterate over $$$a$$$. When we loop over $$$a_i$$$, clearly only $$$dp_j$$$ where $$$0 \leq j \leq a_i$$$ change, so let's see how they change. We have two cases of what to do with $$$a_i$$$:
Therefore, $$$dp_j = dp_j + tot - dp_j = tot$$$. In other words, when we loop over $$$a_i$$$, we assign $$$dp_j = tot$$$ for all $$$0 \leq j \leq a_i$$$, then update our $$$tot$$$. The complexity would still be $$$O(|s|)$$$.
However, I think this solution is much more interesting because this can solve the problem if you are given the string in a compressed manner. When a block of $$$0$$$'s comes, update the $$$dp$$$ like mentioned. When a block of $$$1$$$'s comes, calculate what $$$dp_0$$$ would be after processing all the $$$1$$$'s. We can use a stack to implement this in $$$O(|compress(s)|)$$$.
Div 2 D/Div 1 B was beautiful, thanks
on the problem string transformation 1, I think the test is really week. My solution is o(n^2+nlogn) but still accepted.
What's with all those hacks in div1F?