Idea: Roms
Tutorial
Tutorial is loading...
Solution (Roms)
for t in range(int(input())):
print(input().strip('0').count('0'))
Idea: adedalic
Tutorial
Tutorial is loading...
Solution (adedalic)
fun main() {
val t = readLine()!!.toInt()
for (tc in 1..t) {
val (n, g, b) = readLine()!!.split(' ').map { it.toLong() }
val needG = (n + 1) / 2
var totalG = needG / g * (b + g)
totalG += if (needG % g == 0L) -b else needG % g
println(maxOf(n, totalG))
}
}
Idea: Roms
Tutorial
Tutorial is loading...
Solution (Ne0n25)
#include <bits/stdc++.h>
using namespace std;
#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()
#define forn(i, n) for (int i = 0; i < int(n); ++i)
void solve() {
string s;
cin >> s;
vector<bool> used(26);
used[s[0] - 'a'] = true;
string t(1, s[0]);
int pos = 0;
for (int i = 1; i < sz(s); i++) {
if (used[s[i] - 'a']) {
if (pos > 0 && t[pos - 1] == s[i]) {
pos--;
} else if (pos + 1 < sz(t) && t[pos + 1] == s[i]) {
pos++;
} else {
cout << "NO" << endl;
return;
}
} else {
if (pos == 0) {
t = s[i] + t;
} else if (pos == sz(t) - 1) {
t += s[i];
pos++;
} else {
cout << "NO" << endl;
return;
}
}
used[s[i] - 'a'] = true;
}
forn(i, 26) if (!used[i])
t += char(i + 'a');
cout << "YES" << endl << t << endl;
}
int main() {
int tc;
cin >> tc;
forn(i, tc) solve();
}
Idea: Roms
Tutorial
Tutorial is loading...
Solution (Roms)
from math import log2
for t in range(int(input())):
n, m = map(int, input().split())
c = [0] * 61
s = 0
for x in map(int, input().split()):
c[int(log2(x))] += 1
s += x
if s < n:
print(-1)
continue
i, res = 0, 0
while i < 60:
if (1<<i)&n != 0:
if c[i] > 0:
c[i] -= 1
else:
while i < 60 and c[i] == 0:
i += 1
res += 1
c[i] -= 1
continue
c[i + 1] += c[i] // 2
i += 1
print(res)
Idea: adedalic
Tutorial
Tutorial is loading...
Solution (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
#define x first
#define y second
typedef long long li;
typedef pair<int, int> pt;
const int INF = int(1e9);
const li INF64 = li(1e18);
string s, t;
inline bool read() {
if(!(cin >> s >> t))
return false;
for(auto &c : s)
c -= 'a';
for(auto &c : t)
c -= 'a';
return true;
}
vector< vector<int> > nxt;
bool calc(const string &a, const string &b) {
vector< vector<int> > dp(sz(a) + 1, vector<int>(sz(b) + 1, INF));
dp[0][0] = 0;
fore(i, 0, sz(a) + 1) fore(j, 0, sz(b) + 1) {
if(dp[i][j] > sz(s))
continue;
int len = dp[i][j];
if(i < sz(a) && nxt[len][a[i]] < INF) {
dp[i + 1][j] = min(dp[i + 1][j], nxt[len][a[i]] + 1);
}
if(j < sz(b) && nxt[len][b[j]] < INF) {
dp[i][j + 1] = min(dp[i][j + 1], nxt[len][b[j]] + 1);
}
}
return dp[sz(a)][sz(b)] < INF;
}
inline void solve() {
nxt.assign(sz(s) + 1, vector<int>(26, INF));
for(int i = sz(s) - 1; i >= 0; i--) {
nxt[i] = nxt[i + 1];
nxt[i][s[i]] = i;
}
for(int i = 0; i < sz(t); i++) {
if(calc(t.substr(0, i), t.substr(i, sz(t)))) {
cout << "YES" << endl;
return;
}
}
cout << "NO" << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cout << fixed << setprecision(15);
int tc; cin >> tc;
while(tc--) {
read();
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
Idea: Neon
Tutorial
Tutorial is loading...
Solution (Ne0n25)
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define sqr(a) ((a) * (a))
#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define fore(i, l, r) for (int i = int(l); i < int(r); ++i)
#define forr(i, r, l) for (int i = int(r) - 1; i >= int(l); --i)
typedef pair<int, int> pt;
const int M = 310;
const int N = 2000 * 1000 + 13;
int n, m, q;
int a[M][M];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};
bool in(int x, int y) {
return 0 <= x && x < n && 0 <= y && y < m;
}
int p[M * M], rk[M * M];
int getp(int v) {
return p[v] == v ? v : p[v] = getp(p[v]);
}
bool unite(int a, int b) {
a = getp(a); b = getp(b);
if (a == b) return false;
if (rk[a] < rk[b]) swap(a, b);
p[b] = a;
rk[a] += rk[b];
return true;
}
int dif[N];
vector<pt> add[N], del[N];
void recalc(const vector<pt>& ev, int coeff) {
forn(i, n) forn(j, m) a[i][j] = 0;
forn(i, n * m) p[i] = i, rk[i] = 1;
for (auto it : ev) {
int cur = 1;
int x = it.x / m, y = it.x % m;
a[x][y] = 1;
forn(k, 4) {
int nx = x + dx[k];
int ny = y + dy[k];
if (in(nx, ny) && a[nx][ny] == 1)
cur -= unite(nx * m + ny, x * m + y);
}
dif[it.y] += cur * coeff;
}
}
int main() {
scanf("%d%d%d", &n, &m, &q);
int clrs = 1;
forn(i, q) {
int x, y, c;
scanf("%d%d%d", &x, &y, &c);
--x; --y;
if (a[x][y] == c) continue;
clrs = c + 1;
add[c].pb(mp(x * m + y, i));
del[a[x][y]].pb(mp(x * m + y, i));
a[x][y] = c;
}
forn(x, n) forn(y, m)
del[a[x][y]].pb(mp(x * m + y, q));
forn(i, clrs) reverse(all(del[i]));
forn(i, clrs) recalc(add[i], +1);
forn(i, clrs) recalc(del[i], -1);
int cur = 1;
forn(i, q) {
cur += dif[i];
printf("%d\n", cur);
}
}
Idea: Neon
Tutorial
Tutorial is loading...
Solution (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int N = 150043;
typedef pair<long long, long long> func;
func T[4 * N];
bool usedT[4 * N];
void clear(int v, int l, int r)
{
if(!usedT[v]) return;
usedT[v] = false;
T[v] = make_pair(0ll, 0ll);
if(l < r - 1)
{
int m = (l + r) / 2;
clear(v * 2 + 1, l, m);
clear(v * 2 + 2, m, r);
}
}
long long eval(func f, int x)
{
return f.first * x + f.second;
}
long long get(int v, int l, int r, int x)
{
long long ans = eval(T[v], x);
if(l < r - 1)
{
int m = (l + r) / 2;
if(m > x)
ans = max(ans, get(v * 2 + 1, l, m, x));
else
ans = max(ans, get(v * 2 + 2, m, r, x));
}
return ans;
}
void upd(int v, int l, int r, func f)
{
usedT[v] = true;
int m = (l + r) / 2;
bool need_swap = eval(f, m) > eval(T[v], m);
if(need_swap)
swap(T[v], f);
if(l == r - 1)
return;
if(eval(f, l) > eval(T[v], l))
upd(v * 2 + 1, l, m, f);
else
upd(v * 2 + 2, m, r, f);
}
long long ans = 0;
void update_ans(vector<vector<func> > heads, vector<vector<func> > tails)
{
int n = heads.size();
for(int i = 0; i < n; i++)
{
for(auto x : heads[i])
ans = max(ans, get(0, 0, N, x.first) + x.second);
for(auto x : tails[i])
upd(0, 0, N, x);
}
clear(0, 0, N);
}
int a[N];
vector<int> g[N];
int n;
bool used[N];
int siz[N];
void dfs1(int x, int p = -1)
{
if(used[x]) return;
siz[x] = 1;
for(auto to : g[x])
{
if(!used[to] && to != p)
{
dfs1(to, x);
siz[x] += siz[to];
}
}
}
pair<int, int> c;
int S = 0;
void find_centroid(int x, int p = -1)
{
if(used[x]) return;
int mx = 0;
for(auto to : g[x])
{
if(!used[to] && to != p)
{
find_centroid(to, x);
mx = max(mx, siz[to]);
}
}
if(p != -1)
mx = max(mx, S - siz[x]);
c = min(c, make_pair(mx, x));
}
void dfs_heads(int v, int p, int cnt, long long cursum, long long curadd, vector<func>& sink)
{
if(used[v])
return;
cnt++;
curadd += a[v];
cursum += curadd;
sink.push_back(make_pair(cnt, cursum));
for(auto to : g[v])
if(to != p)
dfs_heads(to, v, cnt, cursum, curadd, sink);
}
void dfs_tails(int v, int p, int cnt, long long cursum, long long curadd, vector<func>& sink)
{
if(used[v])
return;
cnt++;
curadd += a[v];
cursum += a[v] * 1ll * cnt;
sink.push_back(make_pair(curadd, cursum));
for(auto to : g[v])
if(to != p)
dfs_tails(to, v, cnt, cursum, curadd, sink);
}
void centroid(int v)
{
if(used[v]) return;
dfs1(v);
S = siz[v];
c = make_pair(int(1e9), -1);
find_centroid(v);
int C = c.second;
used[C] = 1;
vector<vector<func> > heads, tails;
for(auto to : g[C])
if(!used[to])
{
heads.push_back(vector<func>());
dfs_heads(to, C, 1, a[C], a[C], heads.back());
tails.push_back(vector<func>());
dfs_tails(to, C, 0, 0, 0, tails.back());
}
heads.push_back(vector<func>({{1, a[C]}}));
tails.push_back(vector<func>({{0, 0}}));
update_ans(heads, tails);
reverse(heads.begin(), heads.end());
reverse(tails.begin(), tails.end());
update_ans(heads, tails);
for(auto to : g[C])
centroid(to);
}
int main()
{
scanf("%d", &n);
for(int i = 0; i < n - 1; i++)
{
int x, y;
scanf("%d %d", &x, &y);
--x;
--y;
g[x].push_back(y);
g[y].push_back(x);
}
for(int i = 0; i < n; i++)
scanf("%d", &a[i]);
centroid(0);
printf("%lld\n", ans);
}
Why this post doesn't have any comments?
can someone please explain a little bit about the proof of algorithm of problem F? Why considering all the delete queries in the last doesn't affect the final results?
because the delete queries are after the add queries.
when considering color $$$t$$$,all the add queries is the queries with $$$c_i=t$$$ ,then for sure,they are consquent,and so for sure all the delete queries are after the add queries
But this is true for a particular color right? Like for a color c what ideally should have been done is to perform add query and then immediately after that perform it's delete queries but in code above they are doing all add first and then all delete query.
No...for a certain color c and all the queries with ci=c,the queries are consquent,so they changed some of the cells into color c.There isn't any delete query between them.After that,some queries may change the color of some cells which were color c,these are the delete queries.
Like this example:
For color 1,the add queries are the 1st and the 2nd while the delete query is the 4th.
Sorry but I think I didn't convey my doubt properly. I am talking about this part of code ..
Here we are processing all the delete queries at the end (even after the add queries of same cell i.e. even after add query of (x, y) from c1 to c2).
In problem D
If in binary representation of n the i-th bit is equal to 1 and we have at most one box of size 2^i,
I think this should be at least?
yes it should be at least
can someone please explain me about problem B why TotalG = ceil(needG / g) * (g + b) , i don't understand that clearly =)) ????
every (g + b) days have exactly (g) days good, we call it a block. So if we need (needG) days good, we must have ceil(needG / g) blocks, thus TotalG = ceil(needG / g) * (g + b).
What is the time complexity for G? nlgnlgn?
Yes. You process each node O(lg n) times using centroid decomposition and each time you do it, you add 2 lines and you make 2 queries for the best path in O(lg n). Total is O(n lg^2 n).
Has anyone used adjacency list to solve C ? If so could you share your idea/implementation thanks
Here is my submission — 70873445
Just store the letter as an undirected graph and make sure that every vertex has degree 1 or 2.
Then loop through all the vertex and find the vertex which has degree 1 because that would be the start/end of the graph.
Now go for dfs, if you find a cycle in the graph, that means it's not possible, otherwise dfs will give you the starting letters of the keyboard.
Then just add the remaining alphabets back in the string.
your code is very messy didnt understand a thing ... or may be I m big big noob
The problem statement of F says $$$1 \le c_i \le max(1000,\lceil \frac{2⋅10^6}{nm} \rceil)$$$.
Should not that be $$$min$$$ instead of $$$max$$$?
[Deleted]
Can someone help me understand why my code for G is TLE on test 33? I've read the editorial and I think I am doing the same thing.
https://codeforces.net/contest/1303/submission/71252477
I had also struggled from test 33, and finally made it accepted.
I don't know what exactly is test 33, but this test generator code would be helpful. It takes about 20 sec on N=150000 on your code.
Use the output of the generator code as the input.
For me, it was a problem from cache. I had used so many random-accessing on arrays, and it became x8 faster when I fixed into a cache-friendly code.
Thanks I may have a chance to fix it now. All my own generated samples ran in <2 seconds
can someone explain the solution for problem b
i think it gives right answer for 5 1 5 but wrong for 10 1 10
doubt cleared!
Typo in D, case 2, "most" should be "least".
How to proof that D solution is optimal(finds min number of divides)?
we should consider the lowerest bit first , if we don't have the bit , than look for the nearest high bit and decompose it.
3 years ago :skull:
Hi awoo! Why the scheduled codeforces educational round 83 was deleted?
For problem G, how can we get all the "first parts" and "second parts" efficiently?
I think there is a mistake in the tests in the B problem. MY solution as well as the tutorial both fail at the same place in the second test. Here is my code: (https://codeforces.net/problemset/submission/1303/79669445)(https://codeforces.net/problemset/submission/1303/79668860). Could someone tell me if there is a mistake
When you calculate
minN = round(n / 2)
,n
is truncated beforeround
is called because it's an integer. Son
always rounds down instead of rounding up. You can fix this by doingminN = (n+1) / 2
instead.Also, it's a little arrogant to assume that the tests are wrong if your code doesn't get AC. Especially if nearly 6,000 others have solved without any issues. So test your code a little on some cases first, before assuming the writers messed up.
80808954 Which case am i missing? (Problem B)
you have to take the case when req is divisible by g than you dont need to add the last b days because you have already finished your work and dont and instead of subtracting g from req and than doing other operations better try to do it like this
ans -> the number of days that we need to calculate
You mean a case like this:
It outputs :
No just take the example of 16 3 8 as input Your code will give 16 as output But the correct answer will be 24
Oh ok.. Got it. Thanks
In problem F, can someone please explain the intuition behind deleting cells. How is it similar to adding in reverse order? awoo
in D how do we go about the optimality?
Alternate dp for E. Let $$$dp[len_{s}][len_{a}]$$$ be the max $$$len_{b}$$$ such that the prefix of $$$s$$$ of length $$$len_{s}$$$ contains non-intersecting subsequences of $$$a$$$ and $$$b$$$ of $$$len_{a}$$$ and $$$len_{b}$$$. Set it to -1 if the prefix does not contain a subsequence of length $$$len_{a}$$$. With this approach we don't have to calculate the array $$$nxt$$$ or make the observation in the editorial. Code 97250299
How is solution for D optimal?
Erasing Zeroes //my solution
include<stdio.h>
include<string.h>
main(){ int t; scanf("%d",&t); char str[101]; while(t--){ scanf("%s",&str); int poslast1,posfirst1,c=0; int l=strlen(str); for(int i=0;i<l;i++){ if(str[i]=='1') posfirst1=i; break; } for(int j=l-1;j>=0;j--){ if(str[j]=='1') poslast1=j; break; } for(int k=posfirst1;k<=poslast1;k++){ if(str[k]=='0') c++; } printf("%d\n",c); } return 0; }
//what's problem in this
In problem G, the value of a path between any two nodes can also be queried using binary lifting. (When you have to compute for upward path, just do it like normal binary lifting. When you have to compute for downward path, "invert" its coinciding upward path using trivial relation between prefix sum and suffix sum)
Implementation