Idea: denk
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
signed main() {
cin.tie(nullptr);
cout.tie(nullptr);
ios::sync_with_stdio(false);
int t;
cin >> t;
for(int _ = 0; _ < t; ++_){
int n, ans = 0;
cin >> n;
string s;
cin >> s;
for (int i = 1; i < n; i++) {
ans += (s[i] == '@');
if (s[i] == '*' && s[i - 1] == '*')
break;
}
cout << ans << "\n";
}
return 0;
}
Idea: Vladosiya
Tutorial
Tutorial is loading...
Solution
def solve():
n = int(input())
a = [int(x) for x in input().split()]
cur = 0
for e in a:
cur += e - cur % e
print(cur)
for _ in range(1, int(input()) + 1):
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++)
int main() {
int t;
cin >> t;
forn(tt, t) {
int n, m;
cin >> n >> m;
vector<int> a(n);
forn(i, n)
cin >> a[i];
string s;
cin >> s;
int l = 0;
int r = n - 1;
forn(i, n - 1)
if (s[i] == 'L')
l++;
else
r--;
assert(l == r);
vector<int> b(n);
b[n - 1] = a[l] % m;
for (int i = n - 2; i >= 0; i--) {
if (s[i] == 'L')
b[i] = (b[i + 1] * a[--l]) % m;
else
b[i] = (b[i + 1] * a[++r]) % m;
}
assert(l == 0);
assert(r == n - 1);
forn(i, n)
cout << b[i] << " ";
cout << endl;
}
}
Idea: goncharovmike
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
#define long long long int
#define DEBUG
using namespace std;
// @author: pashka
int main() {
ios::sync_with_stdio(false);
int t;
cin >> t;
for (int tt = 0; tt < t; tt++) {
int n;
cin >> n;
string suites = "CDHS";
string ts;
cin >> ts;
int trump = suites.find(ts[0]);
vector<int> bs[4];
for (int i = 0; i < 2 * n; i++) {
string s;
cin >> s;
bs[suites.find(s[1])].push_back(s[0] - '2');
}
vector<string> res;
vector<string> left;
for (int i = 0; i < 4; i++) {
sort(bs[i].begin(), bs[i].end());
if (i == trump) continue;
if (bs[i].size() % 2 == 1) {
int x = bs[i].back();
left.push_back(string() + char('2' + x) + suites[i]);
bs[i].pop_back();
}
for (int j = 0; j < (int) bs[i].size(); j++) {
int x = bs[i][j];
res.push_back(string() + char('2' + x) + suites[i]);
}
}
if (left.size() > bs[trump].size()) {
cout << "IMPOSSIBLE\n";
} else {
for (string s : left) {
res.push_back(s);
int x = bs[trump].back();
bs[trump].pop_back();
res.push_back(string() + char('2' + x) + suites[trump]);
}
for (int j = 0; j < (int) bs[trump].size(); j++) {
int x = bs[trump][j];
res.push_back(string() + char('2' + x) + suites[trump]);
}
for (int i = 0; i < 2 * n; i += 2) {
cout << res[i] << " " << res[i + 1] << "\n";
}
}
}
}
Idea: step_by_step
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
#define long long long int
#define DEBUG
using namespace std;
// @author: pashka
int main() {
ios::sync_with_stdio(false);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
string s;
cin >> s;
reverse(s.begin(), s.end());
vector<int> a(n + 1);
for (int i = n - 1; i >= 0; i--) {
a[i] = a[i + 1] + (s[i] - '0');
}
string res;
int c = 0;
for (int i = 0; i < n; i++) {
c += a[i];
res += (char)(c % 10 + '0');
c /= 10;
}
res += (char)(c + '0');
while (res.back() == '0') {
res.pop_back();
}
reverse(res.begin(), res.end());
cout << res << "\n";
}
return 0;
}
Idea: denk
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
//#define int long long
#define pb emplace_back
#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(time(nullptr));
const ll inf = 1e18;
const ll M = 998244353;
const ld pi = atan2(0, -1);
const ld eps = 1e-6;
void solve(int tc){
int n, m;
cin >> n >> m;
vector<pair<int, int>> a(m);
vector<int> op(n + 1);
vector<vector<int>> del(n + 1);
for(auto &e: a) {
cin >> e.x >> e.y;
op[e.x]++;
del[e.y].emplace_back(e.x);
}
multiset<int> cur;
vector<int> dp(n + 1);
for(int i = 1; i <= n; ++i){
dp[i] = dp[i - 1];
for(int j = 0; j < op[i]; ++j){
cur.insert(i);
}
if(!cur.empty()){
dp[i] = max(dp[i], int(dp[*cur.begin() - 1] + cur.size()));
}
for(int e: del[i]){
cur.erase(cur.find(e));
}
}
cout << dp[n];
}
bool multi = true;
signed main() {
int t = 1;
if (multi)cin >> t;
for (int i = 1; i <= t; ++i) {
solve(i);
cout << "\n";
}
return 0;
}
Idea: denk
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
#define long long long int
#define DEBUG
using namespace std;
// @author: pashka
struct triple {
long d, x, y;
};
triple eucl(long a, long b) {
if (b == 0) {
return {a, 1, 0};
}
long k = a / b;
auto [d, x, y] = eucl(b, a - k * b);
return {d, y, x - k * y};
}
struct test {
void solve() {
int n, m, H;
cin >> n >> m >> H;
vector<long> l(n);
for (int i = 0; i < n; i++) cin >> l[i];
vector<long> s(n);
for (int i = 0; i < n; i++) cin >> s[i];
vector<vector<int>> g(n);
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
x--;
y--;
g[x].push_back(y);
g[y].push_back(x);
}
const long INF = 1e18;
vector<long> d(n, INF);
d[0] = 0;
set<pair<long, int>> q;
q.insert({d[0], 0});
while (!q.empty()) {
auto p = *q.begin();
q.erase(p);
int v = p.second;
long t = d[v];
for (int u: g[v]) {
long a = (l[v] + (t % H) * s[v]) - (l[u] + (t % H) * s[u]);
a %= H;
if (a < 0) a += H;
long b = s[u] - s[v];
b %= H;
if (b < 0) b += H;
// a - bx = yH
auto [dd, x, y] = eucl(b, H);
// xb + yH = dd
if (a % dd != 0) continue;
x *= a / dd;
x %= (H / dd);
if (x < 0) x += H / dd;
long dt = x;
if (d[v] + dt + 1 < d[u]) {
q.erase({d[u], u});
d[u] = d[v] + dt + 1;
q.insert({d[u], u});
}
}
}
long res = d[n - 1];
if (res == INF) res = -1;
cout << res << "\n";
}
};
int main() {
ios::sync_with_stdio(false);
int n;
cin >> n;
for (int i = 0; i < n; i++) {
test().solve();
}
return 0;
}
Tutorial after 3 days. Why?
hii can anyone help me with my solution[submission:247597946] for which I am getting tle for test case 2. My Idea :- I have used cumulative sum to get the number of cats at any position i and prevnum array to point to the index (x) if i use the index (i) to feed my cats , than simply use dp to calculate dp[n] .Plss help me to get past TLE.!!
I got it, it got accepted :-)
:)
In F, we consider all values from 1 to N. If we only checked points that are either start of end of an interval, then it gives WA. Why could that be?
See the case below. It is optimal to pick the middle of the
3..5segment.check start and (end + 1) of every interval instead as the state changes at (end + 1) for an interval and not at end
Here's a derivation to the solution to E.
Let the initial string/number $$$a_na_{n-1}...a_1$$$.
A change of:-
$$$n$$$ digits occurs $$$a_n$$$ times.
$$$n-1$$$ digits occurs $$$9*a_n + a_{n-1}$$$ times.
$$$n-2$$$ digits occurs $$$9*(a_na_{n-1})+a_{n-2}$$$ times.
Thus, the final answer is:-
$$$= n*a_n+(n-1)*(9*a_n + a_{n-1})+(n-2)*(9*a_na_{n-1}+a_{n-2})+...$$$
$$$= n*a_n+(n-1)*(a_na_{n-1} - a_n)+(n-2)*(a_na_{n-1}a_{n-2}-a_na_{n-1})+...$$$
$$$= n*a_n-(n-1)*a_n+(n-1)*a_na_{n-1}-(n-2)*a_na_{n-1}+(n-2)*a_na_{n-1}a_{n-2}-...$$$
$$$= a_n+a_na_{n-1}+a_na_{n-1}a_{n-2}+...+a_na_{n-1}...a_1$$$
Thanks for very fast editorial
Really "fast"
For F, what if the range of intervals was [1, 1e9]. how can we solve this question then?
we could use co-ordinate compression, the number of unique co-ordinates wont exceed 2n
In problem G,my code got a "Wrong Answer" on test 2. Can anyone give me a hack? Many thanks.
https://mirror.codeforces.com/contest/1932/submission/247682595
I had the same issue but then I added 1 to the new step count since its given that moving to another platform counts as a step.
I have understood it.Thank you.
Very good contest, I hope CodeForces can provide us with more and better games!
I like how they put a "2012" reference in the last test case of problem B.
Here's my solution using Segment Tree for Problem F. https://mirror.codeforces.com/contest/1932/submission/247752578
i think F has linear time solution https://mirror.codeforces.com/contest/1932/submission/247761658
Same version of solution, but a little commented :D, if anyone wants explanation https://mirror.codeforces.com/contest/1932/submission/264556949
Alternative (linear) solution for F:
Rephrase the problem as "you are given $$$n$$$ segments, choose any number of points so that no segment covers more than $$$1$$$ of them, and the number of segments that cover exactly $$$1$$$ point is the maximum possible".
Do it with a dynamic programming of the form $$$dp_i$$$ — the maximum answer if we considered the points $$$[0, i-1$$$], and all segments containing the point $$$i$$$ are uncovered (i. e. we can use the point $$$i$$$ and all subsequent points).
There are basically two transitions:
Solution code
https://mirror.codeforces.com/contest/1932/submission/248011446
i guess i have implemented the same thing, but i have used recursion(stack_overflow), but i am getting runtime error. Any help will be appreciated. Thanks
nvm, i fixed it https://mirror.codeforces.com/contest/1932/submission/248012825
Hey! I think I have implemented the same logic in my code but idk why it's giving WA. Here's my submission:
249587298
nvm I got the mistake.. was a silly one :')
which Online Judge you're using to practice problems ?
Hi,
Can anyone please help me with debugging this submission for Problem G. https://mirror.codeforces.com/contest/1932/submission/247832499, i am WA at testcase 30. For the same logic but small change in variable assumption it is getting accepted https://mirror.codeforces.com/contest/1932/submission/247832770.
The difference is submission 247832499 has dp[i] = steps at which value of connected platforms will become equal i.e. l+s*dp[i] will match with previous platform where dp[i] will be minimum.
While submission 247832770 has dp[i] = 1 + steps at which value of connected platforms become equal i.e. l+s*(dp[i]-1) will match with previous platform where dp[i] will be minimum. Both codes are mostly same just dp[i] has shifted with value 1.
Sorry for bad formatting of the comment!!
nvm got the issue. My bad!!
Correction in third last line, in editorial of G..
k′=b′−1a′modH --> k′=b′−1a′modH′
Can someone help me with C? My code's working, but I keep getting time limit error. The code is written in Python. My submission is: 248030291
Can anyone tell me what category of problems does E lie in? And where can I find similar problems?
these type of problems are implementations
.
Even though Python can handle large integers (note that every $$$a_i$$$ can be as large as $$$10^4$$$), operations on them are slow. When following the solution provided by the editorial, i.e. handling commands in reverse order, then you can keep applying
mod mwhich is much faster (as the product stays under $$$m$$$).In problem G, why do we take x modulo (H / dd) ?
Using 'auto [dd,x,y] = eucl(b,H)', we got one possible solution to the equation — 'xb+yH=dd' (here (dd is the gcd). Now, we multiply 'a/dd' to the above equation to get — '(x*a/dd)*b + (y*a/dd)*H = a'. Now we have one solution {x0,y0} — {(x*a/dd),(y*a/dd)} to the equation but we want the one having smallest positive x0 value. general solution for the above equation would be — {x,y} = {x0 + k*(H/dd) , y0 — k*(b/dd) }. so the samlest possible 'x' would be 'x%(H/dd)' . check out this for more clarification — https://cp-algorithms.com/algebra/linear-diophantine-equation.html
For B
I tried binary search to find the smallest number greater than previous year and divisible by current ai, but it gave wa on test 3. Can someone help me find the error?