Идея: adedalic
Разбор
Tutorial is loading...
Решение (adedalic)
fun main() {
repeat(readLine()!!.toInt()) {
val (n, k1, k2) = readLine()!!.split(' ').map { it.toInt() }
val (w, b) = readLine()!!.split(' ').map { it.toInt() }
if (k1 + k2 >= 2 * w && (n - k1) + (n - k2) >= 2 * b)
println("YES")
else
println("NO")
}
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (Neon)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
string s;
cin >> s;
int i = s.find("11");
int j = s.rfind("00");
cout << (i != -1 && j != -1 && i < j ? "NO" : "YES") << endl;
}
}
1499C - Минимальный путь на поле
Идея: adedalic
Разбор
Tutorial is loading...
Решение (adedalic)
fun main() {
repeat(readLine()!!.toInt()) {
val n = readLine()!!.toInt()
val c = readLine()!!.split(' ').map { it.toInt() }
val mn = intArrayOf(1e9.toInt(), 1e9.toInt())
val rem = longArrayOf(n.toLong(), n.toLong())
var sum = 0L
var ans = 1e18.toLong()
for (i in c.indices) {
mn[i % 2] = minOf(mn[i % 2], c[i])
rem[i % 2]--
sum += c[i]
if (i > 0) {
val cur = sum + rem[0] * mn[0] + rem[1] * mn[1]
ans = minOf(ans, cur)
}
}
println(ans)
}
}
Идея: Neon
Разбор
Tutorial is loading...
Решение (Neon)
#include <bits/stdc++.h>
using namespace std;
const int N = 2e7 + 13;
int main() {
vector<int> mind(N, -1), val(N);
mind[1] = 1;
for (int i = 2; i < N; ++i) if (mind[i] == -1)
for (int j = i; j < N; j += i) if (mind[j] == -1)
mind[j] = i;
for (int i = 2; i < N; ++i) {
int j = i / mind[i];
val[i] = val[j] + (mind[i] != mind[j]);
}
int t;
scanf("%d", &t);
while (t--) {
int c, d, x;
scanf("%d%d%d", &c, &d, &x);
int ans = 0;
for (int i = 1; i * i <= x; ++i) {
if (x % i != 0) continue;
int k1 = x / i + d;
if (k1 % c == 0) ans += 1 << val[k1 / c];
if (i * i == x) continue;
int k2 = i + d;
if (k2 % c == 0) ans += 1 << val[k2 / c];
}
printf("%d\n", ans);
}
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение 1 (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int MOD = 998244353;
int add(int a, int b){
a += b;
if (a >= MOD)
a -= MOD;
if (a < 0)
a += MOD;
return a;
}
int main() {
string s, t;
cin >> s >> t;
int n = s.size(), m = t.size();
vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(m + 1, vector<int>(2, 0)));
int ans = 0;
forn(i, n + 1) forn(j, m + 1){
if (i < n) dp[i + 1][j][0] = add(dp[i + 1][j][0], 1);
if (j < m) dp[i][j + 1][1] = add(dp[i][j + 1][1], 1);
if (0 < i && i < n && s[i - 1] != s[i]) dp[i + 1][j][0] = add(dp[i + 1][j][0], dp[i][j][0]);
if (0 < j && i < n && t[j - 1] != s[i]) dp[i + 1][j][0] = add(dp[i + 1][j][0], dp[i][j][1]);
if (0 < i && j < m && s[i - 1] != t[j]) dp[i][j + 1][1] = add(dp[i][j + 1][1], dp[i][j][0]);
if (0 < j && j < m && t[j - 1] != t[j]) dp[i][j + 1][1] = add(dp[i][j + 1][1], dp[i][j][1]);
ans = add(ans, dp[i][j][0]);
ans = add(ans, dp[i][j][1]);
}
forn(i, n){
int j = i;
while (j + 1 < n && s[j] != s[j + 1]) ++j;
int len = j - i + 1;
int val = (len * 1ll * (len + 1) / 2) % MOD * (m + 1) % MOD;
ans = add(ans, -val);
i = j;
}
forn(i, m){
int j = i;
while (j + 1 < m && t[j] != t[j + 1]) ++j;
int len = j - i + 1;
int val = (len * 1ll * (len + 1) / 2) % MOD * (n + 1) % MOD;
ans = add(ans, -val);
i = j;
}
printf("%d\n", ans);
return 0;
}
Решение 2 (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int MOD = 998244353;
int add(int a, int b){
a += b;
if (a >= MOD)
a -= MOD;
if (a < 0)
a += MOD;
return a;
}
int main() {
string s, t;
cin >> s >> t;
int n = s.size(), m = t.size();
vector<vector<vector<vector<int>>>> dp(n + 1, vector<vector<vector<int>>>(m + 1, vector<vector<int>>(2, vector<int>(4, 0))));
int ans = 0;
forn(i, n + 1) forn(j, m + 1){
if (i < n) dp[i + 1][j][0][1] = add(dp[i + 1][j][0][1], 1);
if (j < m) dp[i][j + 1][1][2] = add(dp[i][j + 1][1][2], 1);
forn(mask, 4){
if (0 < i && i < n && s[i - 1] != s[i]) dp[i + 1][j][0][mask | 1] = add(dp[i + 1][j][0][mask | 1], dp[i][j][0][mask]);
if (0 < j && i < n && t[j - 1] != s[i]) dp[i + 1][j][0][mask | 1] = add(dp[i + 1][j][0][mask | 1], dp[i][j][1][mask]);
if (0 < i && j < m && s[i - 1] != t[j]) dp[i][j + 1][1][mask | 2] = add(dp[i][j + 1][1][mask | 2], dp[i][j][0][mask]);
if (0 < j && j < m && t[j - 1] != t[j]) dp[i][j + 1][1][mask | 2] = add(dp[i][j + 1][1][mask | 2], dp[i][j][1][mask]);
}
ans = add(ans, dp[i][j][0][3]);
ans = add(ans, dp[i][j][1][3]);
}
printf("%d\n", ans);
return 0;
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int MOD = 998244353;
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 k;
vector<vector<int>> g;
vector<vector<int>> dp;
int dfs(int v, int p = -1){
dp[v][0] = 1;
int h = 0;
for (int u : g[v]) if (u != p){
int nh = dfs(u, v);
vector<int> tmp(max(h, nh + 1) + 1);
forn(i, h + 1) forn(j, nh + 1){
if (i + j + 1 <= k)
tmp[max(i, j + 1)] = add(tmp[max(i, j + 1)], mul(dp[v][i], dp[u][j]));
if (i <= k && j <= k)
tmp[i] = add(tmp[i], mul(dp[v][i], dp[u][j]));
}
h = max(h, nh + 1);
forn(i, h + 1){
dp[v][i] = tmp[i];
}
}
return h;
}
int main() {
int n;
scanf("%d%d", &n, &k);
g.resize(n);
dp.resize(n, vector<int>(n, 0));
forn(i, n - 1){
int v, u;
scanf("%d%d", &v, &u);
--v, --u;
g[v].push_back(u);
g[u].push_back(v);
}
dfs(0);
int ans = 0;
forn(i, k + 1) ans = add(ans, dp[0][i]);
printf("%d\n", ans);
return 0;
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
const int N = 1000043;
int add(int x, int y)
{
x += y;
while(x >= MOD) x -= MOD;
while(x < 0) x += MOD;
return x;
}
int sub(int x, int y)
{
return add(x, -y);
}
int mul(int x, int y)
{
return (x * 1ll * y) % MOD;
}
int binpow(int x, int y)
{
int z = 1;
while(y > 0)
{
if(y % 2 == 1)
z = mul(z, x);
x = mul(x, x);
y /= 2;
}
return z;
}
int global_hash = 0;
void reverse(deque<pair<int, int>>& d)
{
stack<pair<int, int>> s;
while(!d.empty())
{
s.push(d.back());
d.pop_back();
}
while(!s.empty())
{
d.push_front(s.top());
s.pop();
}
}
void safe_push_front(deque<pair<int, int>>& d, int c, int& res)
{
int z = d.front().first ^ 1;
res = add(res, mul(binpow(2, c), z));
d.push_front(make_pair(z, c));
}
void safe_push_back(deque<pair<int, int>>& d, int c, int& res)
{
int z = d.back().first ^ 1;
res = add(res, mul(binpow(2, c), z));
d.push_back(make_pair(z, c));
}
deque<pair<int, int>> ds[N];
struct path
{
int s;
int t;
int d;
int c;
path() {};
path(int s, int t, int d, int c) : s(s), t(t), d(d), c(c) {};
void push_front(int i)
{
safe_push_front(ds[d], i, c);
}
void push_back(int i)
{
safe_push_back(ds[d], i, c);
}
void pop_front()
{
ds[d].pop_front();
}
void pop_back()
{
ds[d].pop_back();
}
int front()
{
return ds[d].front().second;
}
int back()
{
return ds[d].back().second;
}
void reverse()
{
::reverse(ds[d]);
swap(s, t);
}
int size()
{
return ds[d].size();
}
};
path link_to_left(path x, path y)
{
path z = x;
while(y.size() > 0)
{
z.push_back(y.front());
y.pop_front();
}
z.t = y.t;
return z;
}
path link_to_right(path x, path y)
{
path z = y;
while(x.size() > 0)
{
z.push_front(x.back());
x.pop_back();
}
z.s = x.s;
return z;
}
int cur = 0;
path make(int x, int y, int i)
{
int cost = i;
ds[cur].push_back(make_pair(0, cost));
return path(x, y, cur++, 0);
}
set<int> paths;
vector<int> paths_v[N];
path ps[N];
path merge(path x, path y, int v)
{
if(x.size() > y.size())
swap(x, y);
if(y.s == v)
{
if(x.t != v)
x.reverse();
return link_to_right(x, y);
}
else
{
if(x.s != v)
x.reverse();
return link_to_left(y, x);
}
}
int cur2 = 0;
void modify(vector<int>& v, int x, int y)
{
for(int i = 0; i < v.size(); i++)
if(v[i] == x)
v[i] = y;
}
void reassign(path p, int x, int y)
{
modify(paths_v[p.s], x, y);
modify(paths_v[p.t], x, y);
}
void merge_paths(int x, int y, int v)
{
if(x == y)
{
}
else
{
global_hash = sub(global_hash, ps[x].c);
global_hash = sub(global_hash, ps[y].c);
ps[cur2++] = merge(ps[x], ps[y], v);
paths.erase(x);
paths.erase(y);
paths.insert(cur2 - 1);
reassign(ps[x], x, cur2 - 1);
reassign(ps[y], y, cur2 - 1);
global_hash = add(global_hash, ps[cur2 - 1].c);
}
}
void relax(int v)
{
while(paths_v[v].size() >= 2)
{
int x = paths_v[v].back();
paths_v[v].pop_back();
int y = paths_v[v].back();
paths_v[v].pop_back();
merge_paths(x, y, v);
}
}
void add_edge(int x, int y, int i)
{
//cerr << x << " " << y << " " << i << endl;
int c = cur2;
ps[cur2++] = make(x, y, i);
paths_v[x].push_back(c);
paths_v[y].push_back(c);
paths.insert(c);
relax(x);
relax(y);
}
void print_coloring()
{
vector<int> ans;
for(auto x : paths)
{
for(auto y : ds[ps[x].d])
{
if(y.first == 1)
ans.push_back(y.second);
}
}
printf("%d", int(ans.size()));
for(auto x : ans)
printf(" %d", x);
puts("");
fflush(stdout);
}
int e = 0;
void process_query()
{
int t;
scanf("%d", &t);
if(t == 1)
{
int x, y;
scanf("%d %d", &x, &y);
y += 200001;
add_edge(x, y, ++e);
printf("%d\n", global_hash);
fflush(stdout);
}
else
print_coloring();
}
void print_info()
{
cerr << "Paths\n";
for(auto x : paths)
cerr << x << " start: " << ps[x].s << " " << " end: " << ps[x].t << endl;
cerr << "Vertices\n";
for(int i = 0; i < N; i++)
if(!paths_v[i].empty())
{
cerr << i << ": ";
for(auto x : paths_v[i])
cerr << x << " ";
cerr << endl;
}
}
int main()
{
int n1, n2, m;
scanf("%d %d %d", &n1, &n2, &m);
for(int i = 0; i < m; i++)
{
int x, y;
scanf("%d %d", &x, &y);
y += 200001;
add_edge(x, y, ++e);
}
int q;
scanf("%d", &q);
for(int i = 0; i < q; i++)
{
//print_info();
process_query();
}
}
Atlast THE EDITORIAL
Why no best hackers :(
Nice hacking bro
In problem D, why there are 2^(the number of prime divisors of k) such pairs. Any proof for that please explain!
You have two options for each prime factor, either it is the part of x or it is the part of y. So the total number of pairs = 2^(number of prime divisors).
Consider each prime factor $$$ p $$$ of $$$ k $$$. Assume that the prime $$$ p $$$ appears $$$ x $$$ time(s) in the factorization of $$$ k $$$ ($$$ p^x | k, p^{x + 1} \not| k $$$), appears $$$ y $$$ time(s) in $$$ A $$$'s and $$$ z $$$ time(s) in $$$ B $$$'s.
Since $$$ \gcd(A, B) = 1 $$$, either $$$ y $$$ or $$$ z $$$ must be equal to $$$ 0 $$$ (otherwise $$$ p|A, p|B, p|\gcd(A, B) $$$). Also we have $$$ y + z = x $$$ for $$$ AB = k $$$.
So there are just $$$ 2 $$$ possibilities: $$$ y = 0, z = x $$$ or $$$ y = x, z = 0 $$$. Because $$$ p $$$ is one of the prime factors of $$$ k $$$, $$$ x > 0 $$$ holds. Therefore, the $$$ 2 $$$ situations are definitely different.
For each prime factor there are $$$ 2 $$$ possibilities to "assign" it to $$$ A $$$ or $$$ B $$$. Apparently the situation of one prime factor is independent of others. So simply multiply them all and the answer is $$$ 2^{\text{number of prime divisors of k}} $$$.
What's the matter of low prime, i am not getting it. Please explain it.
For each prime divisors, we can allocate to either A or B. So for every new prime divisor we have, we can multiply the ans by 2. Hence 2 to the power of the number of prime divisors.
Problem C was tricky
can you explain me C problem pls?
Yes please, the editorial for problem C was not very clear.
I didn't solve it too, that's why I am saying it was tricky)
i have solved using this approach... 1. we treat every index i in range [0,n) as the last segment and compute the total cost such that we reach [n,n] and we have used i segments to reach here, and take minimum of all total costs. 2. here, all even indices segments will be for y-axis or x-axis but not both similarly for odd indices segments. 3. now we calculate minimum value in even indices and minimum in odd indices till i. 4. lets say we travel y axis using even indices and x axis using odd indices. 5. To travel n in Y direction it will be ideal if we move by length 1 in all even indices segments and remaining length by minimum value even segment. As we are using all segments up to i, because our assumption is that i is our last segment. because any way we need to use all even segments for travelling y axis. 6. similarly for x axis 7. we take minimum of all values.
my code: https://codeforces.net/contest/1499/submission/110382254
You can refer to this video for detailed solution as well as explanation. Link to Explanation
The most important thing for problem $$$C$$$ is to realise that in any solution of length $$$k$$$ you are obliged to move at least $$$1$$$ in all the $$$k$$$ movements. Therefore, if you iterate over $$$k$$$ you know every single $$$c_i$$$ for $$$1 \leq i \leq k$$$ is added at least once to the cost. This means we can accumulate sum of $$$c_i$$$ up to current $$$k$$$, we will call this $$$accum_k$$$.
If $$$k$$$ is even we moved $$$cntUp = k/2$$$ times up and $$$cntRight = k/2$$$ times right. If $$$k$$$ is odd then it's floor($$$\frac{k}{2}$$$) $$$+ 1$$$ in one direction and floor($$$\frac{k}{2}$$$) in the other, just try both possibilities of assigning this to $$$cntUp$$$ and $$$cntRight$$$. Since we have already taken into account moving at least 1 every time, we just have to calculate the cost of moving $$$n - cntUp$$$ units up and $$$n - cntRight$$$ times right considering only $$$c_i$$$ with $$$1 \leq i \leq k$$$.
Actually, you can only use $$$c_i$$$ with odd $$$i$$$ for the direction you start with and only $$$c_i$$$ with even $$$i$$$ for the other direction. Also, you can easily see the optimal way to traverse the remaining units is to do so at the step with minimum $$$c_i$$$. This is why we compute a $$$minOdd$$$ and $$$minEven$$$ while we iterate over $$$k$$$.
So to get the optimal answer for a given $$$k$$$:
If $$$k$$$ is even $$$cntUp == cntRight$$$, so it doesn't matter if we start up or right and the answer is $$$accum_k + (n - cntUp)*minOdd + (n - cntRight)*minEven$$$
If $$$k$$$ is odd we try both possibilities of starting up or right, so we choose the minimum between $$$accum_k + (n - cntUp)*minOdd + (n - cntRight)*minEven$$$ where $$$cntUp =$$$ floor($$$\frac{k}{2}$$$) $$$+ 1$$$ and $$$cntRight =$$$ floor($$$\frac{k}{2}$$$) and $$$accum_k + (n - cntUp)*minEven + (n - cntRight)*minOdd$$$ with $$$cntUp$$$ and $$$cntRight$$$ from the previous case swapped.
We do this for every $$$k$$$, not forgetting to update $$$minEven$$$ and $$$minOdd$$$ in the corresponding iterations, and take the minimum from all possible $$$k$$$.
This is what my approach to problem C was: We are to go from origin(0,0) to a point (n,n),using no more than (n-1) turns. We can either go up or go right.It is important to realize that whichever direction we may start(up or right),it doesn't matter as in both the directions,we need to cover a distance equivalent to 'n' because going from (0,0) to (n,n) implies going 'n' units along x-axis and going 'n' units along y-axis. Now,we may realize that the "costs" given to us can be seen as 2different options,i.e. costs at even positions may be used to traverse along x-axis,and costs at odd positions maybe used to traverse along y-axis(you may even say that even positioned costs are used to traverse along y-axis and so on.As I said earlier,it doesn't matter whether you start from right or up as your first step)Just make sure that going right or up means that you can only use alternate "cost" values. Now,we may try a greedy approach by saying that let our answer be : n*(cost[0])+n*(cost[1]) And we may say that in the above expression,there are (n-1) steps that we may remove and take those steps with another cost value,if we get a better alternative in future. WHY?because in the worst case,we at least need to take '1' step for cost[0] and '1' step for cost[1],to even reach in a position to use value of cost[2]. Now,we traverse along the cost vector,and at every alternate position,we see that if the current cost is less than the cost that we used before,it means that we can take away the "removable steps" from the previous "higher" cost,and consider them from the current "lower" cost. Alternatively,if we find that the current cost is greater than the previous cost,we can just take one step and look for future values to see,if the final cost comes out to be less. Finally,we store all the cost values as we go along computing the cost,and in the end, print the minimum value of cost. Here's a link to my implementation of the above logic: https://codeforces.net/contest/1499/submission/110359103
https://codeforces.net/contest/1499/submission/122382473
This implementatiion is exactly on the same idea yet fails at a testcase and it is annoying as the idea is exactly the same. Can anyone suggest anything.
You are calculating the minimum costs for going along the x-axis and y-axis independently and in the end, adding them up as the final answer. However, it may happen that the minimum cost you get while traversing the x-axis doesn't allow you to traverse far enough along the y-axis , so that you may obtain the minimum cost along y-axis. Suppose you have 12 different costs(you will consider 6 costs for the horizontal direction and 6 costs for the vertical direction). Suppose you get the minimum cost for traversing along the x-axis as some sum of the first 3costs(out of the 6 you have) . And in the same manner , you get the minimum cost for traversing along the y-axis as the sum of all 6 costs. You are adding both of these to obtain the final answer . However , this contradicts your own approach as if you took only the first 3 costs along the x-axis , you would never be able to traverse along the "costs" vector to take the 6minimum costs for the y-axis.(and hence never achieve the minimum cost along the y-axis).
In problem F, we can merge subtrees in $$$O(k)$$$ time by computing prefix sums but the only problem is that we might need to calculate inverses which TLE'd for me :( then i just iterated upto max height which worked well (along with calculating inverses).
We can merge all subtrees of a node $$$u$$$ in $$$O(deg(u)\cdot k)$$$ with prefix sums, which leads to a $$$O(n\cdot k)$$$ solution, I did it without any divisions.
Can you explain how you merged the subtrees without calculating mod inverses?
Let's denote $$$dp_{u,x}$$$ as the number of ways to partition the subtree of $$$u$$$, having a diameter equal or smaller than $$$k$$$, and the longest path starting from $$$u$$$ having a length of exactly $$$x$$$, and $$$ac_{u,x}$$$ as the number of ways to partition the subtree of $$$u$$$, having a diameter equal or smaller than $$$k$$$, and the longest path starting from $$$u$$$ having a length of at most $$$x$$$.
Now the transitions:
Having at least one of $$$dp_{u,x}$$$ or $$$ac_{u,x}$$$ we can get the other easily, then the first case can be computed naively, and for the second one, it's possible to precompute for each prefix of childrens $$$\prod ac_{v,k-x-2}$$$, and also for each suffix, with this we can get all the things we need from some node $$$u$$$ in $$$O(deg_u*k)$$$
How did you get a way around with the inverses?
I suppose that is similar to the solution that I described above, but instead of precompute for each prefix and suffix of childrens $$$\prod{ac_{v,k-x-2}}$$$ maintaining the multiplication of that for all childrens, and dividing by the current one.
There are several cases where the logic provided for problem C fails. Like how can someone be so sure that choosing the minimum cost will give the right answer? It might happen that in order to reach the min cost, we might end up adding a lot of highly expensive cost when we could have just used a 2nd lowest or 3rd lowest cost to cover the entire up/right distance.
I really thought I needed to use dynamic programming here.
Trick is you iterate over number of turns you make, and when you fix number of turns , it is always optimal to use the minimum cost in given prefix.
please any one clarify Problem — B edutorial (method-1)
notice that, in the sorted string, there is a prefix of zeroes and a suffix of ones. It means that we can iterate on the prefix (from which we remove all ones), and remove all zeroes from the suffix we obtain. If we try to remove two adjacent characters, then we cannot use this prefix;
If I'm not mistaken, method 1 is $$$O(n^2)$$$ where n is the lenght of s.
If you iterate $$$i$$$ from $$$0$$$ to $$$n$$$, at iteration $$$i$$$ you consider first $$$i$$$ characters to be part of "the prefix" of the solution(where you can only have $$$0$$$'s or nothing) and all next characters to be part of "the suffix" of the solution(where you can only have $$$1$$$'s or nothing).
Now, you can remove the $$$1$$$'s from the prefix if and only if it doesn't contain the sequence $$$11$$$ and you can remove the $$$0$$$'s from the suffix if and only if it doesn't contain the sequence $$$00$$$. You just traverse them linearly to check this. If for some $$$i$$$ you meet both conditions, the answer is YES.
The optimized method comes from realising that if you have a $$$00$$$ sequence at most you can remove one of the zeroes. Therefore, you can't leave any $$$1$$$ before the last occurrence of $$$00$$$, and you can only remove all $$$1$$$'s that appear before if there isn't a $$$11$$$ sequence.
Can someone please tell the 56th query of 2nd test case in Problem C
it's n=4;c[] is [1,2,2,1] you can get it by letting your program simply output it i failed it here too
I guess in problem C the formula should have been sumOdd+minOdd⋅(n−cntOdd+1)+ sumEven+minEven⋅(n−cntEven+1) instead of sumOdd+minOdd⋅(n−cntOdd) + sumEven+minEven⋅(n−cntEven). Isn't it?
yeah, My formula comes similar to this. current_ans = odd_sum + odd_min*(n-odd_cnt) + even_sum + even_min*(n-even_cnt).
You can refer to this video for detailed explanation:- Link to Explanation
if you do it using your formula, minOdd and minEven would be counted twice since they are already being considered once in sumOdd and sumEven
Why is maximum of value of k=(x/g+d)/c = 2*10^7 in Problem C?
Let $$$x = 10^7$$$, $$$g = 1$$$, $$$d = 10^7$$$, $$$c = 1$$$. It is the bounding values for this task.
In F's solution code, d is not even calculated?
Whoops, turns out it works as is. Removed it, thanks.
why in problem D the numbers A and B must be mutually simple?
After you divide two numbers by their GCD, the resulting numbers are coprime. They don't share any common factor greater than 1.
I still do not understand, please explain in more detail, thanks)
If you could be more precise about it maybe we can be more helpful, but right now I can only rephrase the editorial. We are considering two numbers $$$a$$$ and $$$b$$$ and their $$$GCD$$$. If $$$gcd(a,b) = g$$$ by definition $$$g$$$ is the GREATEST number that divides $$$a$$$ and $$$b$$$.
So if we look at $$$A = \frac{a}{g}$$$ and $$$B = \frac{b}{g}$$$, there can't be any number $$$n > 1$$$ that divides both $$$A$$$ and $$$B$$$ because then $$$g*n$$$ would divide $$$a$$$ and $$$b$$$. Since $$$g*n > g$$$ it would have been false that $$$g$$$ is the $$$GCD$$$ of $$$a$$$ and $$$b$$$. This is the same as saying $$$gcd(A, B) = 1$$$, which also means they are coprime.
Thank you, now I understand everything
Why in problem C, we can suppose to make exactly k−1 turns?
Any explanation/solution for D(div 2) other than editorial?
Check this link
Please invest some time to make editorial good for everyone. Many newbies and pupils are not able to understand C.
Take a look at this explanation.
Let's try solving this problem: Given $$$c_1, c_2, c_3 \dots, c_k$$$, find $$$a_1, a_2, a_3, \dots, a_k \ \ (a_i > 0)$$$ such that $$$a_1 + a_2 + a_3 +\dots + a_k = n$$$ and the sum $$$c_1 \cdot a_1 + c_2\cdot a_2 + c_3\cdot a_3 + \dots + c_k\cdot a_k$$$ is minimum.
Let's analyze the case when $$$k = 2$$$; we have $$$c_1, c_2$$$. Obviously $$$a_2 = n - a_1$$$, and the cost would be $$$c_1\cdot a_1 + c_2 \cdot (n - a_1) = c_2\cdot n + a_1\cdot (c_1 - c_2)$$$. If we consider $$$c_1 \ge c_2$$$, then in order to minimize $$$c_2\cdot n + a_1\cdot (c_1 - c_2)$$$, $$$a_1$$$ has to minimum. Also, since $$$a_i > 0$$$, $$$a_1 = 1$$$.
Now, let's generalize that for arbirtrary $$$k \ge 2$$$. Let's build any assignment. Now, suppose there's a pair $$$a_i, a_j$$$ with $$$a_i + a_j = m$$$ ($$$m$$$ is just a constant), and without lossing generality, $$$c_i \ge c_j$$$; then from what we did above, it's optimal to choose $$$a_i = 1, a_j = m - 1$$$, this preserves $$$a_i + a_j = m$$$. We can do that as long as there're still two or more $$$a_i > 1$$$. This proves that for any $$$k \ge 2$$$, it's optimal to match the minimum $$$c_i$$$ with $$$a_i = n - k + 1$$$, and all the others with $$$a_i = 1$$$. Thus, summarizing, the cost would be $$$\left(\sum_{i = 1}^k c_i\right) + (n-k)\cdot \min{c_i, \ \forall i \in[1, k]}$$$
Now, how to solve the real problem? Consider every prefix $$$k\ (k > 1)$$$ of the sequence $$$c_1, c_2, \dots, c_n$$$, and let's get the optimal solution with that prefix; we stay with minium solution among all prefixes. For a fixed $$$k$$$, the odd indexes are independent of the even indexes (we can consider odd indexes for UP movements, and even indexes for RIGHT movements), so for a fixed $$$k$$$, we have the subsequence of even indexes until k: $$$e_1, e_2, e_3, \dots, e_r$$$ and the subsequence of odd indexes $$$o_1, o_2, o_3, \dots, o_s$$$, and basically we want to solve the above problem for each of these two sequences.
Now, since we go moving $$$k$$$ to the right, we need to keep track the sum of all $$$c_{2i}$$$ and the sum of all $$$c_{2i + 1}$$$, and also the minimum all $$$c_{2i}$$$ and the minimum of all $$$c_{2i + 1}$$$.
These things can be updated easily when we go increasing $$$k$$$.
Oh thanks for the effort! but I got it already
The editorial states that storing the min prime factor using sieve and calculating the ans in $$$\mathcal{O}\left(\sqrt{x} log x \right)$$$ is not fast enough , I did precisely that and it passed the test cases . $$$\newline$$$ Solution Link : https://codeforces.net/contest/1499/submission/110701050
I have a similar situation
Thanks for the editorial.. was waiting for it. I was asking for help for problem D from my friends, but no one was responding correctly , and that made me feel down... life is hard, when you are fart :(
Resolved
Can anyone explain in problem D, why the pairs generated of the form (Ag, Bg) would be unique and will not contain repetitive pairs? Can it not be possible that for 2 different g's, we get 2 different A's and B's such that A1g1 = A2g2 and B1g1 = B2g2 so that they are necessarily the same pair. I am having a hard time understanding this. Any help would be appreciated. Thank You.
Thank you for the editorial! The explanation for problem C is obvious.