Tutorial
Tutorial is loading...
Solution (PikMike)
n = int(input())
s = input()
for i in range(n - 1):
if (s[i] != s[i + 1]):
print("YES")
print(s[i], s[i + 1], sep="")
exit(0)
print("NO")
Tutorial
Tutorial is loading...
Solution (Ajosteen)
#include <bits/stdc++.h>
using namespace std;
const int N = int(2e5) + 9;
int n;
int a[N];
int b[N];
bool u[N];
int main() {
// freopen("input.txt", "r", stdin);
scanf("%d", &n);
for(int i = 0; i < n; ++i) {
scanf("%d", a + i);
}
for(int i = 0; i < n; ++i){
scanf("%d", b + i);
}
int pos = 0;
for(int i = 0; i < n; ++i){
int x = b[i];
if(u[x]){
printf("0 ");
continue;
}
int cnt = 0;
while(true){
++cnt;
u[a[pos]] = true;
if(a[pos] == x) break;
++pos;
}
++pos;
printf("%d ", cnt);
}
puts("");
return 0;
}
Tutorial
Tutorial is loading...
Solution (Ajosteen)
#include <bits/stdc++.h>
using namespace std;
const int N = int(1e5) + 9;
string s;
int n;
int x, y;
void upd(pair<int, int> &pos, char mv, int d){
if(mv == 'U')
pos.second += d;
if(mv == 'D')
pos.second -= d;
if(mv == 'L')
pos.first -= d;
if(mv == 'R')
pos.first += d;
}
bool can(pair<int, int> u, pair<int, int> v, int len){
int d = abs(u.first - v.first) + abs(u.second - v.second);
if(d % 2 != len % 2) return false;
return len >= d;
}
bool ok(int len){
pair<int, int> pos = make_pair(0, 0);
for(int i = len; i < n; ++i)
upd(pos, s[i], 1);
int l = 0, r = len;
while(true){
if(can(pos, make_pair(x, y), len))
return true;
if(r == n) break;
upd(pos, s[l++], 1);
upd(pos, s[r++], -1);
}
return false;
}
int main() {
//freopen("input.txt", "r", stdin);
cin >> n;
cin >> s;
cin >> x >> y;
if(!ok(n)){
puts("-1");
return 0;
}
int l = -1, r = n;
while(r - l > 1){
int mid = (l + r) / 2;
if(ok(mid)) r = mid;
else l = mid;
}
cout << r << endl;
return 0;
}
Tutorial
Tutorial is loading...
Solution (PikMike)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int N = 200 * 1000 + 13;
typedef long long li;
int n;
int a[N];
void get(li T, li& pr, li& cnt){
pr = 0, cnt = 0;
forn(i, n){
if (T >= a[i]){
T -= a[i];
pr += a[i];
++cnt;
}
}
}
int main() {
li T;
scanf("%d%lld", &n, &T);
forn(i, n)
scanf("%d", &a[i]);
int mn = *min_element(a, a + n);
li ans = 0;
while (T >= mn){
li pr, cnt;
get(T, pr, cnt);
ans += cnt * (T / pr);
T %= pr;
}
printf("%lld\n", ans);
return 0;
}
Tutorial
Tutorial is loading...
Solution (Vovuh)
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<long long, int> pt;
const int N = 20;
const int M = 1 << 10;
const int MOD = 998244353;
int k;
int pw10[N];
int bitCnt[M];
pt dp[N][M][2];
int add(int a, int b) {
a += b;
if (a >= MOD) a -= MOD;
if (a < 0) a += MOD;
return a;
}
int mul(int a, int b) {
return a * 1ll * b % MOD;
}
int calc(const string &s) {
for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
dp[i][j][0] = dp[i][j][1] = { 0ll, 0 };
}
}
int len = s.size();
dp[0][0][1] = { 1ll, 0 };
for (int i = 0; i < len; ++i) {
int cdig = s[i] - '0';
for (int mask = 0; mask < M; ++mask) {
if (dp[i][mask][0].x == 0 && dp[i][mask][1].x == 0) continue;
for (int dig = (i == 0); dig <= 9; ++dig) {
int nmask = mask | (1 << dig);
long long cnt = dp[i][mask][0].x;
int sum = add(dp[i][mask][0].y, mul(dig, mul(pw10[len - i - 1], cnt % MOD)));
dp[i + 1][nmask][0].x += cnt;
dp[i + 1][nmask][0].y = add(dp[i + 1][nmask][0].y, sum);
}
for (int dig = (i == 0); dig <= cdig; ++dig) {
int nmask = mask | (1 << dig);
long long cnt = dp[i][mask][1].x;
int sum = add(dp[i][mask][1].y, mul(dig, mul(pw10[len - i - 1], cnt % MOD)));
dp[i + 1][nmask][dig == cdig].x += cnt;
dp[i + 1][nmask][dig == cdig].y = add(dp[i + 1][nmask][dig == cdig].y, sum);
}
}
}
int ans = 0;
for (int mask = 0; mask < M; ++mask) {
if (bitCnt[mask] > k) continue;
ans = add(ans, dp[len][mask][0].y);
ans = add(ans, dp[len][mask][1].y);
}
return ans;
}
int calc(long long n) {
int len = to_string(n).size();
int ans = 0;
for (int l = 1; l < len; ++l) {
ans = add(ans, calc(string(l, '9')));
}
ans = add(ans, calc(to_string(n)));
return ans;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
pw10[0] = 1;
for (int i = 1; i < N; ++i) {
pw10[i] = mul(pw10[i - 1], 10);
}
for (int i = 0; i < M; ++i) {
bitCnt[i] = __builtin_popcount(i);
}
long long l, r;
cin >> l >> r >> k;
int ans = add(calc(r), -calc(l - 1));
cout << ans << endl;
return 0;
}
Tutorial
Tutorial is loading...
Solution (Vovuh)
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define size(a) int((a).size())
typedef pair<int, int> pt;
const int N = 200 * 1000 + 11;
int n;
vector<int> g[N];
int p[N];
int dist[N];
bool bad[N];
int value[N];
pt res[N];
vector<pt> best[N];
void dfs(int v, int par = -1, int d = 0) {
p[v] = par;
dist[v] = d;
for (auto to : g[v]) {
if (to == par) {
continue;
}
dfs(to, v, d + 1);
}
}
int getFarthest(int v) {
dfs(v);
int res = v;
for (int i = 0; i < n; ++i) {
if (bad[i]) {
continue;
}
if (dist[res] < dist[i]) {
res = i;
}
}
return res;
}
pt get(int v) {
return { dist[v], value[v] };
}
int getBetter(int v, int u) {
if (get(v) > get(u)) {
return v;
}
return u;
}
int getBest(int v, int par) {
int res = v;
for (auto to : g[v]) {
if (to == par || bad[to]) {
continue;
}
res = getBetter(res, getBest(to, v));
}
return res;
}
pt calc(int v) {
dfs(v);
vector<int> ch;
for (auto to : g[v]) {
if (!bad[to]) {
ch.push_back(to);
}
}
if (size(ch) == 1) {
return { v, ch[0] };
}
vector<int> pref(size(ch));
vector<int> suf(size(ch));
vector<int> best(size(ch));
for (int i = 0; i < size(ch); ++i) {
int to = ch[i];
best[i] = pref[i] = suf[i] = getBest(to, v);
}
for (int i = 1; i < size(ch); ++i) {
pref[i] = getBetter(pref[i], pref[i - 1]);
suf[size(ch) - i - 1] = getBetter(suf[size(ch) - i - 1], suf[size(ch) - i]);
}
pt ans = { -1, -1 };
pt res = { 0, 0 };
for (int i = 0; i < size(ch); ++i) {
int bst = -1;
if (i == 0) {
bst = suf[i + 1];
} else if (i + 1 == size(ch)) {
bst = pref[i - 1];
} else {
bst = getBetter(pref[i - 1], suf[i + 1]);
}
pt curRes = { dist[bst] + dist[best[i]], value[bst] + value[best[i]] };
if (res < curRes) {
res = curRes;
ans = { best[i], bst };
}
}
return ans;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
cin >> n;
for (int i = 0; i < n - 1; ++i) {
int x, y;
cin >> x >> y;
--x, --y;
g[x].push_back(y);
g[y].push_back(x);
}
int root = -1;
for (int i = 0; i < n; ++i) {
if (size(g[i]) > 2) {
root = i;
dfs(i);
break;
}
}
for (int i = 0; i < n; ++i) {
if (size(g[i]) != 1) {
continue;
}
int v = i;
while (size(g[v]) < 3) {
bad[v] = true;
v = p[v];
}
best[v].push_back({dist[i] - dist[v], i});
}
for (int i = 0; i < n; ++i) {
if (size(best[i]) >= 2) {
sort(best[i].rbegin(), best[i].rend());
value[i] = best[i][0].first + best[i][1].first;
res[i] = { best[i][0].second, best[i][1].second };
}
}
int u = getFarthest(root);
int v = getFarthest(u);
vector<int> path;
while (v != u) {
path.push_back(v);
v = p[v];
}
path.push_back(u);
pt ans = calc(path[size(path) / 2]);
printf("%d %d\n", res[ans.x].x + 1, res[ans.y].x + 1);
printf("%d %d\n", res[ans.x].y + 1, res[ans.y].y + 1);
return 0;
}
1073G - Yet Another LCP Problem
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;
template<class A, class B> ostream& operator <<(ostream &out, const pair<A, B> &p) {
return out << "(" << p.x << ", " << p.y << ")";
}
template<class A> ostream& operator <<(ostream &out, const vector<A> &v) {
out << "[";
fore(i, 0, sz(v)) {
if(i) out << ", ";
out << v[i];
}
return out << "]";
}
const int N = 200 * 1000 + 555;
const int LOGN = 18;
int n, q;
char s[N];
bool read() {
if(!(cin >> n >> q))
return false;
assert(scanf("%s", s) == 1);
return true;
}
int c[N], id[N], lcp[N];
int mn[LOGN][N];
int lg2[N];
void buildSuffArray() {
s[n++] = '$';
for(int l = 1; l < 2 * n; l <<= 1) {
vector< pair<pt, int> > d;
fore(i, 0, n)
d.emplace_back(l == 1 ? pt(s[i], 0) : pt(c[i], c[(i + (l >> 1)) % n]), i);
stable_sort(d.begin(), d.end());
c[d[0].y] = 0;
fore(i, 1, n)
c[d[i].y] = c[d[i - 1].y] + (d[i].x != d[i - 1].x);
if(c[d.back().y] == n - 1)
break;
}
fore(i, 0, n)
id[c[i]] = i;
int l = 0;
fore(i, 0, n) {
if(c[i] == n - 1)
continue;
l = max(0, l - 1);
int j = id[c[i] + 1];
while(i + l < n && j + l < n && s[i + l] == s[j + l])
l++;
lcp[c[i]] = l;
}
n--;
lg2[0] = lg2[1] = 0;
fore(i, 2, N) {
lg2[i] = lg2[i - 1];
if((1 << (lg2[i] + 1)) <= i)
lg2[i]++;
}
fore(i, 0, n)
mn[0][i] = lcp[i];
fore(pw, 1, LOGN) fore(i, 0, n) {
mn[pw][i] = mn[pw - 1][i];
if(i + (1 << (pw - 1)) < n)
mn[pw][i] = min(mn[pw][i], mn[pw - 1][i + (1 << (pw - 1))]);
}
}
int getMin(int l, int r) {
int ln = lg2[r - l];
return min(mn[ln][l], mn[ln][r - (1 << ln)]);
}
int getLCP(int i, int j) {
if(i == j) return n - i;
i = c[i], j = c[j];
return getMin(min(i, j), max(i, j));
}
bool cmp(const pt &a, const pt &b) {
if(a.x == b.x)
return a.y < b.y;
int l = getLCP(a.x, b.x);
return s[a.x + l] < s[b.x + l];
}
void solve() {
buildSuffArray();
fore(_, 0, q) {
int k, l;
assert(scanf("%d%d", &k, &l) == 2);
vector<int> a(k), b(l);
fore(i, 0, k)
assert(scanf("%d", &a[i]) == 1), a[i]--;
fore(j, 0, l)
assert(scanf("%d", &b[j]) == 1), b[j]--;
li ans = 0;
vector<pt> c;
for(auto v : a)
c.emplace_back(v, 1);
for(auto v : b)
c.emplace_back(v, 0);
sort(c.begin(), c.end(), cmp);
fore(k, 0, 2) {
li sum = 0;
map<int, int> cnt;
fore(i, 0, sz(c)) {
int id = c[i].x, tp = c[i].y;
if(tp == 0)
ans += sum;
else {
cnt[n - id]++;
sum += (n - id);
}
if(i + 1 < sz(c)) {
int len = getLCP(c[i].x, c[i + 1].x);
while(!cnt.empty()) {
auto it = --cnt.end();
if(it->x <= len)
break;
sum -= it->x * 1ll * it->y;
cnt[len] += it->y;
sum += it->y * 1ll * len;
cnt.erase(it);
}
}
}
reverse(c.begin(), c.end());
}
printf("%lld\n", ans);
}
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
cout << fixed << setprecision(15);
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
#endif
}
return 0;
}
for problem E, did you mean to write dig=1...9 (or 0...9)?
we cannot place a digit 10
I'm sorry, this is a mistake. Hope it fixed now!
The solution of problem F is: use greedy thoughts to find the longest path in the tree. So, we will look for the first point of the common part as root, then dfs () from that root to find the other end
"we will look for the first point of the common part as root", how to look for the first point of the common part as root? Which is the first point of the common part as root, is the center of the origin tree?
Why do we have to keep iterating until T becomes smaller than the minimum priced sweet in Problem D. What I am thinking is when we do T=T mod C , we will be having money only for a single round of circle. Please correct me If I am wrong. Thank you.
Your assumption in second line i.e. " When we do T=Tmodc.... ...single round of circle. " is wrong.
give it another thought. it's easy you will get it.
Your thinking is wrong. The following testcase can hack you:
After T%C, The number of round of circle is multiple, instead of single.
Won't C = 3 after the first circle and 999999998 % 3 = 2 which can be covered in another round of the circle?
Yes! I got the error. Thank you!
Can someone please explain the logic used in problem C?
Thanks.
In C we apply binary search on the length of string to find whether it is possible or not to reach the desired position from the position reached by applying all the operations measured in non effective range and changing the operations in substring of given length(lets say
len
) and we would do that for all substrings of lengthlen
.Eg: You have a string
RRRUUL
and you want to check if you could reach position (-4,2). So we apply binary search and lets saymid = 3
. Then you would check for indices0 to 2
to see if by changing the instructions in this range can I reach my desired position. Now you have to apply the rest of operations(which are not affected in the range selected, here positions3 to 5
in the string) anyhow, so to check the validity we make our initial position to be the one that is obtained by applying the operations in non effective range(hereUUL
position3 to 5
in original string). So now your initial position is(-1,2)
. Now from this position you check whether I can reach to(-4,2)
by changing the at most 3 instructions in given range(position0 to 2
in string). In this case you can(changeRRR
toLLL
) and so call to ok(3) would returntrue
. Like this the binary sear occurs and at the end you would have the minimum value of length.I hope this helps
Thanks a lot. Understood why we used binary search in this problem. :)
Happy to help ^^
awoo In C problem why is value of
l
initialized with-1
and not0
which is the minimum value if answer is possible(and it is, as we already checked it byok(n)
). Also how to determine the loop condition to ber - l > 1
and not the standardr > l
?There are two ways to write a binary search: on segment [l, r] or on interval [l, r) or (l, r]. This is the (l, r] case, so we should be sure that ok(l) = false and ok(r) = true. In case of invervals, (l, r] is a degenerate case .
Can someone explain me solution to problem E?
Not sure what the editorial does exactly, but one way to solve it with DP is two store two values.
DP1[pos][less?][mask] stores the amount of ways to make number from position pos, whether previous number makes subsequence numbers less than already, and mask to store which digits have been used from 0-9 DP2[pos][less?][mask] stores the sum of the numbers, same parameters of DP1
We can calculate DP1 somewhat straightforwardly, and for DP2 we use values of DP1 to calculate (for adding the number '5' onto for example, we might add 5 * DP1[pos][less?][mask] to out DP2 value)
I saw a solution with segment tree for problem D. Anyone to explain the method?
I have solved it using two segment trees so it may be similar solution. Both were for suming on interval and changing in 1 point. The first one was for suming cost of candies, the latter for suming candies. We are skipping whole circles as long as we can so ater that we will have some T < C. Then we can binary search how far can we go by checking sum of cost candies using segment tree. The we can add to result sum from the second tree on the same interval, change cost of candie to 0 and change value of candie to 0 (because we will never buy it again). Then we move our starting point just after the last fair we have binary searched for, remove fairs on which we will never buy candies, and repeat whole process again. In each loop we are decreaing number of fairs by at least 1 and cost of every loop is O(log^2 N) for segment tree and binary search so total complexity should be O(Nlog^2 N). In my solution it was handy to be only on fairs on which we can still buy candies so i kept set of indices of those.
Alright, I've just found a stunningly beautiful solution to E. No more ugly, confusing DP. Say hello to this beast:
https://codeforces.net/contest/1073/submission/45154557
It's so simple, it's perfect. All you do is loop over the bitmasks of sets of digits. Then, for each one, binary search on the largest string that's not greater than our boundaries. Then just subtract the total sum of all possible numbers generated by our digit set up to the right boundary from the total sum from the left boundary to find its contribution to the answer!
Of course, you have some handling with things like overcounting, leading zeroes, and such, but it turns out with this algorithm those are all gone with a wave of the hand.
BOOM! Now this is the kind of thing competitive programming is about.
UPD: I've been smiling so hard my face hurts
Please put this into Contest materials of the Round . Thanks.
What's the meaning of $$$dp[i][mask][0].x$$$ and $$$dp[i][mask][0].y$$$ in problem E?
I think it is easier to use two pointers instead of binary search in C. Also, it will give O(n) instead of O(n*log(n)) solution.
how to do it using that ?
Here is my solution using two pointers .
https://codeforces.net/contest/1073/submission/112896136
I solved G with divide and conquer in $$$O(n \log n + (\sum k_i + \sum l_i)\log n)$$$: 119421806.
The idea is to sort the points $$$a_i$$$ and $$$b_i$$$ by their position in the suffix array. We do divide and conquer on this sorted list. Without loss of generality, say we want the answer for all $$$a_i\le b_i$$$. To find the answer for all pairs with $$$a_i$$$ in the first half and $$$b_i$$$ in the second half, we can maintain two pointers going from the middle outwards. We always advance the pointer that gives the higher range minimum.