1650A - Deletions of Two Adjacent Letters
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); i++)
int main() {
int t;
cin >> t;
forn(tt, t) {
string s, t;
cin >> s >> t;
bool yes = false;
forn(i, s.length())
if (s[i] == t[0] && i % 2 == 0)
yes = true;
cout << (yes ? "YES" : "NO") << endl;
}
}
Idea: Vladosiya
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
//#define int long long
#define mp make_pair
#define x first
#define y second
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#pragma GCC optimize("fast-math")
typedef long double ld;
typedef long long ll;
using namespace std;
mt19937 rnd(143);
const ll inf = 1e9;
const ll M = 1e9;
const ld pi = atan2(0, -1);
const ld eps = 1e-4;
void solve() {
int l, r, x;
cin >> l >> r >> x;
int ans = r / x + r % x;
int m = r / x * x - 1;
if(m >= l)ans = max(ans, m / x + m % x);
cout << ans;
}
bool multi = true;
signed main() {
//freopen("in.txt", "r", stdin);
//freopen("in.txt", "w", stdout);
int t = 1;
if (multi) {
cin >> t;
}
for (; t != 0; --t) {
solve();
cout << "\n";
}
return 0;
}
1650C - Weight of the System of Nested Segments
Idea: myav
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define forn(i, n) for (int i = 0; i < int(n); i++)
struct point{
int weight, position, id;
};
void solve(){
int n, m;
cin >> n >> m;
vector<point>points(m);
forn(i, m) {
cin >> points[i].position >> points[i].weight;
points[i].id = i + 1;
}
sort(points.begin(), points.end(), [] (point a, point b){
return a.weight < b.weight;
});
int sum = 0;
forn(i, m){
if(i < 2 * n) sum += points[i].weight;
else points.pop_back();
}
sort(points.begin(), points.end(), [] (point a, point b){
return a.position < b.position;
});
cout << sum << endl;
forn(i, n){
cout << points[i].id << ' ' << points[2 * n - i - 1].id << endl;
}
}
int main() {
int t;
cin >> t;
while(t--){
solve();
}
return 0;
}
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i, n) for (int i = 0; i < int(n); i++)
void solve() {
int n;
cin >> n;
int a[n];
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
int ans[n];
for (int i = n; i > 0; --i) {
int ind = 0;
for (int j = 0; j < i; ++j) {
ind = a[j] == i ? j : ind;
}
int b[i];
for (int j = 0; j < i; ++j) {
b[(i - 1 - ind + j) % i] = a[j];
}
for (int j = 0; j < i; ++j) {
a[j] = b[j];
}
ans[i - 1] = i != 1 ? (ind + 1) % i : 0;
}
for (int i = 0; i < n; ++i) {
cout << ans[i] << ' ';
}
cout << '\n';
}
int main() {
int tests;
cin >> tests;
forn(tt, tests) {
solve();
}
}
Idea: senjougaharin
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
#define int long long
#define mp make_pair
#define x first
#define y second
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
typedef long double ld;
typedef long long ll;
using namespace std;
mt19937 rnd(143);
const ll inf = 1e9;
const ll M = 998'244'353;
const ld pi = atan2(0, -1);
const ld eps = 1e-4;
int n, d;
int cnt(vector<int> &schedule){
int mx = 0, mn = inf;
for(int i = 1; i < n; ++i){
mx = max(mx, schedule[i] - schedule[i - 1] - 1);
mn = min(mn, schedule[i] - schedule[i - 1] - 1);
}
return min(mn, max(d - schedule.back() - 1, (mx - 1) / 2));
}
void solve(int test_case) {
cin >> n >> d;
vector<int> a(n + 1);
int mn = d, min_pos = 0;
for(int i = 1; i <= n; ++i){
cin >> a[i];
if(a[i] - a[i - 1] - 1 < mn){
mn = a[i] - a[i - 1] - 1;
min_pos = i;
}
}
vector<int> schedule;
for(int i = 0; i <= n; ++i){
if(i != min_pos){
schedule.push_back(a[i]);
}
}
int ans = cnt(schedule);
if(min_pos > 1){
schedule[min_pos - 1] = a[min_pos];
}
ans = max(ans, cnt(schedule));
cout << ans;
}
bool multi = true;
signed main() {
//freopen("in.txt", "r", stdin);
//freopen("in.txt", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
if (multi) {
cin >> t;
}
for (int i = 1; i <= t; ++i) {
solve(i);
cout << "\n";
}
return 0;
}
1650F - Vitaly and Advanced Useless Algorithms
Idea: Aris
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
template<class T> bool ckmin(T &a, T b) {return a > b ? a=b, true : false;}
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define sz(v) (int)v.size()
#define all(v) v.begin(),v.end()
struct option {
int t, p, id;
option(int _t,int _p, int _id) : t(_t), p(_p), id(_id) {
}
};
const int INF = INT_MAX >> 1;
vector<int> get_ans(vector<option> &v) {
int n = sz(v);
vector<vector<int>> dp(101, vector<int>(n+1, INF));
dp[0][0] = 0;
for (int k = 1; k <= n; k++) {
auto [t,p,id] = v[k-1];
dp[0][k] = 0;
for (int i = 100; i > 0; i--) {
int prev = max(0,i - p);
dp[i][k] = dp[i][k-1];
ckmin(dp[i][k], dp[prev][k-1] + t);
}
}
vector<int> ans;
int t = dp[100][n];
if (t == INF) return {-1};
for (int i = 100, k = n; k >= 1; k--) {
if (dp[i][k] == dp[i][k-1]) {
continue;
}
ans.emplace_back(v[k-1].id);
i = max(0, i - v[k-1].p);
}
reverse(all(ans));
ans.emplace_back(t);
return ans;
}
void solve(bool flag=true) {
int n,m; cin >> n >> m;
vector<int> a(n);
forn(i, n) {
cin >> a[i];
}
for (int i = n-1; i > 0; i--) {
a[i] -= a[i-1];
}
vector<vector<option>> v(n);
forn(j, m) {
int e,t,p; cin >> e >> t >> p, e--;
v[e].emplace_back(t, p, j+1);
}
vector<int> ans;
forn(i, n) {
vector<int> cur = get_ans(v[i]);
if (sz(cur) == 1 && cur[0] == -1) {
cout << "-1\n";
return;
}
int t = cur.back();
if (t > a[i]) {
cout << "-1\n";
return;
}
cur.pop_back();
if (i+1 < n) a[i+1] += a[i] - t;
ans.insert(ans.end(), all(cur));
}
cout << sz(ans) << '\n';
for (auto e:ans) cout << e << ' ';
cout << '\n';
}
int main() {
int t;
cin >> t;
forn(tt, t) {
solve();
}
}
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define sz(v) (int)v.size()
#define eb emplace_back
#define mt make_tuple
const int INF = INT_MAX >> 1;
const int mod = 1e9 + 7;
void csum(int &a,int b) {
a = (a + b) % mod;
}
int s, t;
vector<int> us;
vector<int> dist;
vector<int> dp[2];
int bfs(vector<vector<int>> &g) {
queue<tuple<int,int,int>> q;
q.push(mt(s, 0, 0)); //[v, dist, count]
int ans = 0, mnd = INF;
us[s] = 1;
dp[0][s] = 1;
dist[s] = 0;
while(!q.empty()) {
auto [v,d, x] = q.front(); q.pop();
// cerr << v << ' ' << d << ' ' << dp[x][v] << endl;
if (v == t) {
if (mnd == INF) {
mnd = d;
}
csum(ans, dp[x][v]);
}
if (d == mnd + 1) continue;
for (int to : g[v]) if(d <= dist[to]) {
dist[to] = min(dist[to], d+1);
csum(dp[d - dist[to] + 1][to], dp[x][v]);
// cerr << "TO: " << to << ' ' << dist[to] << ' ' << d << endl;
if(us[to] == 0 || (us[to] == 1 && dist[to] == d)) q.push(mt(to, d+1, us[to]++));
}
}
return ans;
}
void solve() {
int n,m; cin >> n >> m;
cin >> s >> t;
us.resize(n+1);
dp[0].resize(n+1);
dp[1].resize(n+1);
dist.resize(n+1);
forn(i, n+1) {
us[i] = dp[0][i] = dp[1][i] = 0;
dist[i] = INF;
}
vector<vector<int>> g(n+1);
forn(i, m) {
int a,b; cin >> a >> b;
g[a].eb(b);
g[b].eb(a);
}
cout << bfs(g) << '\n';
}
int main() {
int t;
cin >> t;
forn(tt, t) {
solve();
}
}
Thank you codeforces for this contest!
my solution for problem D using deque: https://codeforces.me/contest/1650/submission/148940490 I think it's easier, if you know data structure.
Yeah+
please explain your solution
First, The problem is he performed n operations sequentially. At the i-th operation, Petya chose the first i elements of the array and cyclically shifted them to the right number of times.
we have the final array ! and before operations we know that the array is sorted
so how can we do this operations reversely to sort the array ? _we will start from n instead of 1 _and shift left instead of shift right
first we want to make the last number in the array equal n , how many times of shift left we can do to make that ? just loop make shiftes untill it happen and then now we will search for n-1 to put it in position n-1 in the array so to make the same thing easier we will remove n from the array, we won't need it again.
Dude you are amazing!
It's a her btw.
dude is a universal term
so straight men sleep with dudes?
Thank you Girl !!
Thank you!
You're welcome :)
I love you!
hh
E has an answer binary search.
Can you please explain your approach ?
Thanking you in advance
If you are/were getting a WA/RE verdict on problems from this contest, you can get a small counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table to increase/decrease the constraints.
If you are not able to find a counter example even after changing the parameters, reply to this thread, mentioning the contest_id, problem_index and submission_id.
Thanks, Was really helpful
Ok
Ok
You don't have to Build SegTree for this problem bro! It can be solved very easy))
Resolved
in the following statement
numbers from r−rmoda to r that have an incomplete quotient when divided by a equal to ⌊r/a⌋
1) can someone expain me the meaning of the incomplete quotient(does it mean that it will give remainder?)
2) How did we arrive at this conclusion?
Can anyone plese explain this.
I find the editorial difficult to understand. Here is my way of explaining a solution to problem B:
Imagine a 5x7 monthly calendar where the rows represent work week and the columns represent Sunday, Monday, ... to Saturday. Suppose the upper left hand corner of the has the day start with 0. So, the first row are days 0 ~ 6, second row are days 7 ~ 13, and so on.
Day / 7represents the work week, the row on the calendar.Day % 7represents the week day (Sunday=0, ..., Saturday=6), the column on the calendar. Suppose the question is to ask you which day from L (eg 20) to R (eg 29) has the Manhattan distance largest from the origin of the calendar.My approach is to check if the L and R are on the same row. If so, then R is the answer. Otherwise, I tried to move R to the closest Saturday on the previous row.
Hope you get what I mean.
We want to prove that for every number $$$x$$$ in range $$$[r - r \ mod \ a; r] \ x \ mod \ a \le r \ mod \ a$$$; $$$r - r \ mod \ a$$$ is divided by $$$a$$$, because $$$r = a \cdot r \ div \ a \ + r \ mod \ a$$$, it means $$$r - r \ mod \ a = a \cdot r \ div \ a$$$, and $$$a$$$ multiply something always is divided by $$$a$$$. OK, we know that $$$r - r \ mod \ a$$$ is divided by $$$a$$$ and every number in range $$$[r - r \ mod \ a + 1; r]$$$ is not divided by $$$a$$$. That means every $$$x$$$ from range $$$[r - r \mod \ a + 1; r]$$$ has incomplete quotient $$$\lfloor\frac{r}{a}\rfloor$$$. For example, $$$r = 11$$$, $$$a = 4$$$. $$$11 - 11 \ mod \ 4$$$ = $$$8$$$. $$$8$$$ is divided by $$$4$$$ and every num in range $$$[8 + 1; 11]$$$ is not divided by $$$4$$$. $$$\frac{8}{4} = 2$$$, $$$\frac{9}{4} = 2,25$$$, $$$\lfloor(2,25)\rfloor = 2$$$. Maximum in range $$$[8 + 1; 11]$$$ is $$$11$$$, and for maximum value we still get result $$$\lfloor \frac{r}{a} \rfloor = 2$$$ ; $$$\frac{11}{4} = 2,75$$$, $$$\lfloor(2,75)\rfloor = 2$$$.
We want to prove that for every number x in range [r−r mod a;r] x mod a≤r mod a is it because of this fact:- fact that [x/a] is maximum at x=r so if xmoda<=rmoda ,we can put x=r and make both [x/a] and xmoda maximum simultaneously
Yes, but if $$$x = r - r \ mod \ a - 1$$$ we get maximum $$$r \ mod \ a$$$, so we just need to check $$$x = r - r \mod \ a - 1$$$ and $$$x = r$$$.
the more number of times i read the expainations, the more queries i am having( maybe because i am new to advance number theory concepts or it is the wording of the editorial)
1)how did you arrive at the conclusion that every number in range [r−rmoda + 1;r] is not divided by a.
i can observe it but i am not able to prove it mathematically
2) what do we exactly mean by incomplete quotient
3)why does the editoral say the statement (and are guaranteed to have a value fa less than fa(r)) if we find a x such that x%a > r%a, can't we get a fax>far ( i know that is what we are trying to prove but i want to know if i am interpreting this editorial statement correctly .
Let's have an example: $$$a=7$$$. $$$21$$$ is divided by $$$7$$$, next number that can be divided is $$$21+7=28$$$. Every number in range $$$[21 + 1; 28 - 1]$$$ is not divided by $$$7$$$. So, if number $$$x$$$ divided by $$$a$$$ then $$$x + a$$$ also divided by $$$a$$$ and every number in range $$$[x + 1, x + a - 1]$$$ is not divided by $$$a$$$. $$$r - r \ mod \ a$$$ is divided by $$$a$$$, every number in range $$$[r - r \ mod \ a + 1; r - r \ mod \ a + a - 1]$$$ is not divided by $$$a$$$, we sure that $$$r < r - r \ mod \ a + a$$$, because number $$$a - r \ mod \ a > 0$$$, $$$r \ mod \ a < a$$$.
2) $$$a \ div \ b$$$ is incomplete quotient or $$$\lfloor\frac{a}{b} \rfloor$$$.
finally a div3 contest after 2 month break^^
Why havn't the rating changed yet?
Why are the ratings not updated yet?
Hello there, and thanks for the enjoyable problems.
I liked the last two problems since they can have much to teach for people who are new to DP and graph algorithms.
Problem F was a combination of two merely classic ideas that are good to know for beginners, and the last problem introduces a useful property of the BFS algorithm and the BFS tree.
Thanks to both authors for their cool problems, and I would suggest everyone to upsolve these two problems since they may help you in the future :)
Problem statement could be more clearer as I wasted a lot of time in the 3rd question to understand just what I need to print.
Can anyone explain G, I'm having a little trouble in understanding editorial.
Can the problem D be solved in O(n) time complexity?
I wasted whole time trying that, would be helpful if some did solve it using O(n)
Why I used memory search on G and got a TLE :(
In problem E is it possible to reschedule one of exams to day one?
yes but that would never help bc the time between the start of the session and the first exam is counted in the answer.
where can i found similar problems to G-Counting shortcuts ? i suck at dp on trees/graphs :(
Could somebody, please, explain how do we use dp in G-problem?
You store the number of ways to reach a node from source by following a path of min distance and (min distance + 1). Like whenever you're reaching a node from some other node, just ask if the depth of the curr node is equal to min depth or (min depth + 1), based on the ans you get, update your dp values.
In problem E , I just used a multiset which stores the difference between every two consecutive exams dates and update it for each element (try to put it in the best place) I think its easier. here it is 148865257
yea my sol was very similar haha, multiset is a lot more intuitive isnt it :p
Problem 1650G - Counting Shortcuts can be solved in another way. Calculate for each vertex: distance and number of shortest paths from $$$s$$$ and $$$t$$$ (with 2 bfs). Then we can iterate over all edges $$$\left(u,v\right)$$$. Firstly, vertices $$$u$$$ and $$$v$$$ should be included in same level (same distance from $$$s$$$). Secondly, $$$\text{dist}(s,u)+\text{dist}(v,t)=\text{dist}(s,t)$$$. If both conditions are held, then we can build path $$$s \rightarrow ... \rightarrow u \rightarrow v \rightarrow ... \rightarrow t$$$ with length equal to $$$\text{dist}(s,t)+1$$$. We need to add $$$\text{cntShortestWays}(s,u) \cdot \text{cntShortestWays}(t,v)$$$ to answer. Solution: 150206150
can you explain why vertices u and v should be included in same level?
It prevents us from counting a path multiple times, because any path of length (minimum path length + 1) will have exactly one edge in which two points are at the same level of distance from s.