Author: UncleGrandpa. Prepared by UncleGrandpa
Author: I_love_tigersugar ft. MikeMirzayanov. Prepared by UncleGrandpa
Modelize the problem
We modelize the problem as graph, where each fridge is a vertex and each chain is an edge between two vertexes. The problem is now equivalent to: Given a graph with $$$n$$$ vertexes, each vertex has a value $$$a_i \ge 0$$$. We have to add $$$m$$$ edges to the graph such that each vertex is connected to at least two different vertexes and the total cost of edges added is minimum. The cost of an edge is the sum of value of its two end-points.
Observe some basic properties of graph
Now, each edge added will increase the sum of degree of all vertexes by 2. So adding m edges will make the sum of degree equal to $$$2 \times m$$$. Since each vertexes must be connected to at least $$$2$$$ other vertexes, the minimum sum of degree is $$$2 \times n$$$.
- Case 1: $$$2\times m < 2\times n \Leftrightarrow m<n$$$
In this case, it is obvious that the answer is $$$-1$$$.
- Case 2: $$$2\times m = 2\times n \Leftrightarrow m=n$$$
In this case, it is easy to see that the degree of each vertex will be exactly 2. As a result, no matter what edges we add, the result is still $$$2\times (a_1+a_2+...+a_n)$$$. But please take note that if $$$n=2$$$, then the answer will be $$$-1$$$ since for each vertex we have at most $$$1$$$ different vertex to connect to.
- Case 3(Of the original, pre-modified version of the problem): $$$2\times m > 2\times n \Leftrightarrow m>n$$$
Please read this excellent answer by Um_nik. All credit goes to him for the excellent proof.
Author: MikeMirzayanov. Prepared by UncleGrandpa
Author: I_love_tigersugar. Prepared by I_love_tigersugar
#include<bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i++)
#define FORE(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define ALL(v) (v).begin(), (v).end()
#define IS_INF(x) (std::isinf(x))
#define IS_NAN(x) (std::isnan(x))
#define fi first
#define se second
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define div ___div
#define next ___next
#define prev ___prev
#define left ___left
#define right ___right
#define __builtin_popcount __builtin_popcountll
using namespace std;
template<class X, class Y>
bool minimize(X &x, const Y &y) {
X eps = 1e-9;
if (x > y + eps) {
x = y;
return true;
} else return false;
}
template<class X, class Y>
bool maximize(X &x, const Y &y) {
X eps = 1e-9;
if (x + eps < y) {
x = y;
return true;
} else return false;
}
template<class T>
T Abs(const T &x) {
return (x < 0 ? -x : x);
}
/* Author: Van Hanh Pham */
/** END OF TEMPLATE - ACTUAL SOLUTION COMES HERE **/
const string SYMBOLS = "QWERTYUIOPASDFGHJKLZXCVBNMqwertyuiopasdfghjklzxcvbnm1234567890";
#define MAX 111
char board[MAX][MAX], res[MAX][MAX];
int numRow, numCol, numChicken;
void process(void) {
memset(board, 0, sizeof board);
memset(res, 0, sizeof res);
scanf("%d%d%d", &numRow, &numCol, &numChicken);
FOR(i, 1, numRow) scanf("%s", board[i] + 1);
bool leftToRight = true;
vector<pair<int, int>> cells;
FOR(i, 1, numRow) {
if (leftToRight) {
FOR(j, 1, numCol) cells.push_back(make_pair(i, j));
} else {
FORD(j, numCol, 1) cells.push_back(make_pair(i, j));
}
leftToRight ^= 1;
}
int totRice = 0;
FOR(i, 1, numRow) FOR(j, 1, numCol) if (board[i][j] == 'R') totRice++;
int avg = totRice / numChicken;
int diff = totRice % numChicken == 0 ? 0 : 1;
REP(i, numChicken) {
int cntRice = 0;
while (true) {
int x = cells.back().fi, y = cells.back().se;
cells.pop_back();
res[x][y] = SYMBOLS[i];
if (board[x][y] == 'R') {
totRice--;
cntRice++;
}
if (cntRice < avg) continue;
if (avg * (numChicken - i - 1) <= totRice && totRice <= (avg + diff) * (numChicken - i - 1)) break;
}
}
while (!cells.empty()) {
int x = cells.back().fi, y = cells.back().se;
cells.pop_back();
res[x][y] = SYMBOLS[numChicken - 1];
}
FOR(i, 1, numRow) {
FOR(j, 1, numCol) printf("%c", res[i][j]); printf("\n");
}
}
int main(void) {
int t; scanf("%d", &t);
REP(love, t) process();
return 0;
}
/*** LOOK AT MY CODE. MY CODE IS AMAZING :D ***/
1254B1 - Send Boxes to Alice (Easy Version)
Author: MofK. Prepared by UncleGrandpa
The problem asked you to move chocolate pieces between adjacent boxes so that the number of chocolate pieces in all boxes is divisible by $$$k$$$ ($$$k>1$$$).
How to solve the problem for a specific $$$k$$$
Now, it's clear that we will divide the array into segments, such that the sum of each segment is divisible by $$$k$$$, and move all chocolate pieces in that segment to a common box. Here we take notice of 2 things:
First, in each segment, let $$$A$$$ be the array of all position with 1, then the position that we move all the 1 to is the median of that array $$$A$$$ (easy to prove).
Second, the sum of each segment should be all equal to $$$k$$$. It's easy to see that if there exists some segment of sum $$$x*k$$$, then separating them into $$$x$$$ segments of sum $$$k$$$ will improve the result.
With that two observations, we can iterate from 1 to n, push each position with value 1 into a temp array, and whenever the size of array become k, we add to our result the sum of $$$|a_i-median|$$$ and clear the array.
Knowing how to solve for a specific $$$k$$$, how to solve the problem?
It is clear that $$$k$$$ must be a divisor of the total number of chocolate pieces. So we iterate through all possible $$$k$$$ and minimize our answer with the number of steps to make all numbers divisible by k. A number $$$\le 10^5$$$ has at most 128 divisors, and each calculation take $$$O(n)$$$ so the solution should pass easily.
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000006;
int n;
int a[maxn];
vector <int> v;
long long cost(int p) {
long long ret = 0;
for (int i = 0; i < v.size(); i += p) {
int median = v[(i + i + p - 1) / 2];
for (int j = i; j < i + p; ++j)
ret += abs(v[j] - median);
}
return ret;
}
int main(void) {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
if (a[i] == 1) v.push_back(i);
}
if (v.size() == 1) {
cout << -1 << endl;
return 0;
}
long long ans = 1e18;
int tmp = v.size(), p = 2;
while (p * p <= tmp) {
if (tmp % p == 0) {
ans = min(ans, cost(p));
while (tmp % p == 0)
tmp /= p;
}
++p;
}
if (tmp > 1)
ans = min(ans, cost(tmp));
cout << ans << endl;
return 0;
}
1254B2 - Send Boxes to Alice (Hard Version)
Author: MofK. Prepared by MofK and UncleGrandpa
The problem E2 is different from the problem E1 in some ways. Now all $$$A_i$$$ is at most $$$10^6$$$, and so is the number $$$n$$$. That makes our solution on E1 simply not usable in this problem.
A cute observation:
Let $$$S_i$$$ be the sum of $$$a_1 + a_2 + ... + a_i$$$. Now we see that:
if we move a chocolate piece from box $$$i$$$ to box $$$i+1$$$, it is equivalent to decrease $$$S_i$$$ by 1.
if we move a chocolate piece from box $$$i+1$$$ to box $$$i$$$, it is equivalent to increase $$$S_i$$$ by 1.
Wow, now each moving steps only affect one number. Next, we can see that if every $$$a_i$$$ is divisible by k, then so is every $$$S_i$$$. Thus, our problem is now transformed to: Given an array $$$S$$$. At each turn, you can choose one $$$S_i$$$ and increase (or decrease) it by one (except for $$$S_n$$$). Find the minimum number of steps to make all $$$S_i$$$ divisible by $$$k$$$.
How to solve the problem for a specific $$$k$$$
An intuitive approach is to try to increase (or decrease) each $$$S_i$$$ to the nearest multiple of $$$k$$$. If such a configuration can be achieved then it will obviously be the best answer. The only concern is that: is there any scenario when there exists some $$$i$$$ such that $$$S_i > S_{i+1}$$$, which is indeed a violation? Fortunately, the answer is no. We can enforce the solution to iterate each $$$S_i$$$ from $$$1$$$ to $$$n-1$$$ and always choose to decrease if there is a tie. This way, the sequence $$$S$$$ will remain non-decreasing throughout the process.
So, the solution is as follows. Just iterate from $$$1$$$ to $$$n-1$$$ and for each $$$i$$$, add to our result $$$min(S_i\%k,k-S_i\%k)$$$.
Knowing how to solve for a specific $$$k$$$, how to solve the problem?
Again, like E1, it is clear that $$$k$$$ must be a divisor of the total number of chocolate pieces. But now the total number of chocolate pieces is at most $$$10^{12}$$$, which an iteration through all divisors will not be fast enough to fit in 1 second. (In fact, we did make just one single test case to block this solution. Nevertheless, on random testcases it runs super fast).
But if you have solved the problem to this phase already, you can easily realize that we only need to consider prime $$$k$$$, because if $$$k$$$ is composite then picking any prime divisors of it will lead to either a better result or an equal result.
That's it, there will be at most 12 distinct prime divisors. Each calculation takes $$$O(n)$$$. So the solution will also pass easily.
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000006;
int n;
long long a[maxn];
long long s[maxn];
long long cost(long long mod) {
long long ret = 0;
for (int i = 1; i <= n; ++i)
ret += min(s[i] % mod, mod - s[i] % mod);
return ret;
}
int main(void) {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
s[i] = s[i-1] + a[i];
}
if (s[n] == 1) {
cout << -1 << endl;
return 0;
}
long long ans = 1e18;
long long tmp = s[n], p = 2;
while (p * p <= tmp) {
if (tmp % p == 0) {
ans = min(ans, cost(p));
while (tmp % p == 0)
tmp /= p;
}
++p;
}
if (tmp > 1)
ans = min(ans, cost(tmp));
cout << ans << endl;
return 0;
}
Author: ngkan. Prepared by ngkan
#include <bits/stdc++.h>
using namespace std;
int n;
void check_if_zero(long long x){
if (x == 0) exit(0);
}
long long get_area(int a,int b,int c){
long long result;
cout << 1 << ' ' << a << ' ' << b << ' ' << c << endl;
cin >> result;
check_if_zero(result);
assert(result > 0);
return result;
}
int get_sign(int o,int a,int b){
int result;
cout << 2 << ' ' << o << ' ' << a << ' ' << b << endl;
cin >> result;
check_if_zero(result);
assert(abs(result) == 1);
return result;
}
vector <int> lef, rig;
void divide(){
for(int i=3;i<=n;i++){
int sign = get_sign(1, 2, i);
if (sign == 1)
lef.push_back(i);
else
rig.push_back(i);
}
}
long long area12[1005];
void _do(vector<int> &lst){
if (lst.size() <= 1)
return;
long long best = 0;
for(auto v: lst){
area12[v] = get_area(1, 2, v);
if (area12[v] > area12[best])
best = v;
}
vector <int> l, r;
for(auto v: lst){
if (v == best)
continue;
if (get_sign(1, best, v) == 1)
l.push_back(v);
else
r.push_back(v);
}
sort(l.begin(), l.end(), [&](int x,int y){
return area12[x] > area12[y];
});
sort(r.begin(), r.end(), [&](int x,int y){
return area12[x] < area12[y];
});
lst.clear();
for(auto v: r) lst.push_back(v);
lst.push_back(best);
for(auto v: l) lst.push_back(v);
}
void answer(){
cout << 0 << ' ' << 1 << ' ';
for(auto v: rig) cout << v << ' ';
cout << 2 << ' ';
for(auto v: lef) cout << v << ' ';
cout << endl;
}
int main(){
cin >> n;
assert(n >= 3);
divide(); // n-2 queries
_do(lef);
_do(rig); // 2*(n-2) - 1 or 2*(n-2) - 2 queries
answer();
}
Author: I_love_tigersugar Prepared by I_love_tigersugar
#include <bits/stdc++.h>
using namespace std;
const int maxn = 150005;
const int mod = 998244353;
const int heavy = 300;
int n, m, q;
vector <int> adj[maxn];
int dad[maxn];
int sz[maxn];
vector <int> pos[maxn];
int tour[2*maxn];
vector <int> heavy_vector;
int weight[2*maxn];
int pw(int x, int y) {
int r = 1;
while (y) {
if (y & 1) r = 1LL * r * x % mod;
x = 1LL * x * x % mod;
y >>= 1;
}
return r;
}
void dfs(int u) {
tour[++m] = u;
pos[u].push_back(m);
sz[u] = 1;
for (auto v: adj[u]) {
if (v == dad[u]) continue;
dad[v] = u;
dfs(v);
sz[u] += sz[v];
tour[++m] = u;
pos[u].push_back(m);
}
}
int fwt[2*maxn];
void upd(int l, int r, int d) {
for (int p = l; p <= m; p += p & -p) fwt[p] = (fwt[p] + d) % mod;
++r;
for (int p = r; p <= m; p += p & -p) fwt[p] = (fwt[p] + mod - d) % mod;
}
int get(int p) {
int ret = 0;
for (; p; p -= p & -p) ret = (ret + fwt[p]) % mod;
return ret;
}
int main(void) {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cin >> n >> q;
int inv_n = pw(n, mod - 2);
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(1);
for (int i = 1; i <= n; ++i) if (adj[i].size() >= heavy)
heavy_vector.push_back(i);
while (q--) {
int type, v;
cin >> type >> v;
if (type == 1) {
int d;
cin >> d;
weight[v] = (weight[v] + d) % mod;
if (adj[v].size() < heavy) {
for (auto u: adj[v]) if (u != dad[v])
upd(pos[u][0], pos[u].back(), 1LL * d * (n - sz[u]) % mod * inv_n % mod);
if (v == 1) continue;
upd(1, pos[v][0] - 1, 1LL * d * sz[v] % mod * inv_n % mod);
upd(pos[v].back() + 1, m, 1LL * d * sz[v] % mod * inv_n % mod);
}
}
else {
int ans = (weight[v] + get(pos[v][0])) % mod;
for (auto u: heavy_vector) {
if (u == v) continue;
auto it = lower_bound(pos[u].begin(), pos[u].end(), pos[v][0]);
if (it == pos[u].begin() || it == pos[u].end())
ans = (ans + 1LL * weight[u] * sz[u] % mod * inv_n) % mod;
else {
int p = tour[*(--it) + 1];
ans = (ans + 1LL * weight[u] * (n - sz[p]) % mod * inv_n) % mod;
}
}
cout << ans << '\n';
}
}
return 0;
}
Author: MofK Prepared by: MofK
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int maxn = 500005;
int n;
vector <int> adj[maxn];
int a[maxn];
int dad[maxn];
int h[maxn];
vector <pair <int, int> > conditions[maxn];
int nxt[maxn], prv[maxn], seen[maxn];
void no(int ncase) {
cerr << ncase << endl;
cout << 0 << endl;
exit(0);
}
void dfs(int u) {
for (auto v: adj[u]) if (v != dad[u]) {
dad[v] = u;
h[v] = h[u] + 1;
dfs(v);
}
}
int cnt; ///total distance, must not be more than 2n-2
void go(int u, int v) {
if (u == v) no(0);
vector <int> from_u, to_v;
///naive LCA works here as long as we exit upon finding a conflict
from_u.push_back(n + 1); ///first edge (fake)
to_v.push_back(n + 2); ///last edge (fake)
while (h[u] > h[v]) {
from_u.push_back(u);
u = dad[u];
}
while (h[v] > h[u]) {
to_v.push_back(v);
v = dad[v];
}
while (u != v) {
from_u.push_back(u);
u = dad[u];
to_v.push_back(v);
v = dad[v];
}
from_u.push_back(u);
from_u.insert(from_u.end(), to_v.rbegin(), to_v.rend());
for (int i = 1; i + 1 < from_u.size(); ++i)
conditions[from_u[i]].push_back({from_u[i-1], from_u[i+1]});
cnt += from_u.size() - 3;
if (cnt > 2 * n - 2) no(0); ///important break
}
int main(void) {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cin >> n;
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for (int i = 1; i <= n; ++i) {
adj[i].push_back(n + 1); ///first edge (fake)
adj[i].push_back(n + 2); ///last edge (fake)
}
for (int i = 1; i <= n; ++i) cin >> a[i];
if (n == 1) {
cout << 1 << endl;
exit(0);
}
dfs(1);
for (int i = 1; i <= n; ++i) if (a[i] != 0) go(i, a[i]);
///answer 0 if:
///1. there are 2 or more incoming/outgoing
///conditions to/from an edge, or
///2. there is a cycle, or
///3. first (n+1) is connected to last (n+2),
///but does not contain all other edges.
int ans = 1;
for (int i = 1; i <= n; ++i) {
///check case 1
for (auto edge: conditions[i]) {
int u = edge.first, v = edge.second;
if (nxt[u] && nxt[u] != v) no(1);
if (prv[v] && prv[v] != u) no(1);
nxt[u] = v;
prv[v] = u;
}
///check case 2
for (auto u: adj[i]) if (!seen[u]) {
seen[u] = 1;
int cur = nxt[u];
while (cur) {
if (cur == u) no(2);
if (seen[cur]) break;
seen[cur] = 1;
cur = nxt[cur];
}
}
///check case 3
if (nxt[n+1]) {
int cur = n + 1, all = 1;
while (cur) {
if (cur == n + 2) break;
++all;
cur = nxt[cur];
}
if (cur == n + 2 && all < adj[i].size()) no(3);
}
///all good - for now
int free = 0;
for (auto u: adj[i]) if (u <= n && !prv[u]) ///fake edges doesn't count
++free;
if (prv[n+2]) --free; ///connected to last edge => not free
for (int j = 1; j <= free; ++j) ans = 1ll * ans * j % mod;
///reset
for (auto u: adj[i]) nxt[u] = prv[u] = seen[u] = 0;
}
///no conflicts
cout << ans << endl;
return 0;
}
Auto comment: topic has been updated by I_love_tigersugar (previous revision, new revision, compare).
when 601 round will be rated
Why my submissions are skipped? :/
Same code was submitted by other handle.
How can I know who did it?
cf will send an email did you use Ideone ?
orz
For Problem D I just sorted the adjacency list by size of the subtree (then flatten it with euler tour). That way even if nodes are heavy I can update all the subtrees in $$$sqrt(N)log(N)$$$ since it will have at most $$$sqrt(N)$$$ different value in sizes and I can update several subtrees of the same size in one single range update (because they are in one complete range in the euler tour) and you want to add the same value $$$\frac{1}{n}d(n-sz)$$$ to all of them.
Hacked. Each update for a subtree size should call only 1 Fenwick Tree update instead of 2. Or you can do this.
I did the same thing and was getting TLE, but then I realized that I can optimize the worst case if I batch update queries for the same node, so if there is 1 node that has sqrt(2*n) different values, worst case will be Q/2 modifies which should reduce the constant by 2 and make it work. It now passes.
https://mirror.codeforces.com/contest/1254/submission/65470890
I use similar idea about different subtree size. But I also divede the queries into sqrt(Q) parts then get a O(NsqrtN) off-line algorithm: We use an array to modify the updates and calculate the presum after each part. Then for each query with type 2, we just need to calculate the updates from the queries with type 1 in the same part. For all Nsqrt(N) such pairs of queries, we sort them by dfs order using bucket sorting. Then we insert the pairs into corresponding vertex's vector, then for each vertex we calculation the values of all the queries corresponding to it one by one with the vector containing its subtrees with different size and their dfs orders, just like a merge sorting.
Code:65993177
I_love_tigersugar
For editorial of Div2E2/Div1B2, shouldn't it be
min(Si%k, k - Si%k)
insteadmin(Si%k, (k-Si)%k)
?And btw, anyone has the link for the markups used for blogs/comments on CodeForces?
It was fixed, thank you!
does the idea of grouping k chocolates into their coordinates meridian work? I did it on contest, but got wa on pretests of E1 (but not on pretests of E2) and not sure if it is a bug or wrong solution.
I think it will work, but then the hard part here is you don't know the number of candies in each part to determine the median.
I did it in the contest (65365892). Basically, you just divide all candies into groups of $$$K$$$ and move each group into its median box. Just need to be careful because the number of candies at a time can exceed $$$K$$$.
So E1 editorial solution can be done for E2 also with some modifications (or a lot of modifications :D). Am I right?
How can we prove that median will give optimal answer
Notice that we can map the given rectangle to an array. In other words, there exists a path in the rectangle that goes through every cell exactly once.
can someone explain this partSorry for the word choice. I have rewritten the tutorial for easier reading.
Thanks ,I get it now
I don't understand why the round was rated for me. On what basis did you decide that the mistake in problem B did not affect me ? This mistake completely ruined my contest. I wasted 100 min in B. And when I up-solved C and D I could solve them quickly. this could have been a very good contest for me but now I lost 50 points. and yet you refuse to make round unrated
did you submit the form?
I am exactly in his position. Wasted a lot of time for b. I filled the form,but with no effect.
Me too.
How I did D:
Call a vertex heavy if it has more than $$$T$$$ neighbours.
For updates at $$$u$$$, first update the complement of the subtree rooted at $$$u$$$. Then, if $$$u$$$ is heavy, just keep track of the update at $$$u$$$. Otherwise, update the subtrees rooted at the children of $$$u$$$. This is $$$O(T\log(N))$$$.
For queries at $$$u$$$, first query the value at $$$u$$$. Then, jump upwards to the next heavy vertex until we reach the root, and update the answer with the values at these heavy vertices. This is $$$O(\log(N)+N/T)$$$.
Setting $$$T=\sqrt{N/\log(N)}\approx93$$$ gives $$$O\left(Q\sqrt{N\log(N)}\right)$$$ total. Runs in under half a second on system tests but I found an input that makes it run in 2.6 seconds.
(seems like a less intelligent version of this $$$O(N\log(N))$$$ solution: https://mirror.codeforces.com/blog/entry/71534?#comment-559222)
An alternative solution for D. Tree Queries.
It's obvious that for each "modify" operation we can spend $$$O(degree_x \log n)$$$ time naively updating the answer using BIT in the tree-dfs order. And now we can get some improvements. For each node we initially choose one of its sons of the largest size. For a "modify" we only update its father's "subtree" and the heaviest son's subtree. And for each query, we not only calculate the answer in the BIT, but also jump up to the query node's ancestors that haven't updated the query node yet and calculate the extra answer.
It can be shown that there are at most $$$O(\log n)$$$ such ancestors to deal with. So the total complexity is $$$O((n+q) \log n)$$$, with quite a small constant.
Code: 65403262
Beautiful solution!
My solution to Tree Queries:
For a set of updates, we can easily calculate their contributions to each node in $$$O(n)$$$ time -- for each node $$$u$$$ we get the sum of $$$d$$$ of all operations that $$$v=u$$$, then iterate all neighbours of $$$u$$$. Since we do not need to support online query, the updates can be done with difference in linear complexity.
Also it's easy to tell an update's contribution to a specific node $$$u$$$: we just need to get the size of the subtree of $$$u$$$ when we root at $$$v$$$. This can be done in $$$O(n\log n) - O(1)$$$ complexity.
We calculate the contribution to each node every $$$\sqrt n$$$ operations, and when query on a node we consider the latest $$$\sqrt n$$$ updates' contribution to it. This works in $$$O(n\log n+n\sqrt n)$$$ time.
Can someone explain in Div2E2, how can we assume that if we are taking k-S[i]%k from i+1 th element then it will not become negative ( does it have enough candy to give). The author has said something related to this doubt as 'S[i]>S[i+1]'. Can someone give an intuitive proof of th this. Thanks in advance.
lucifer_1502 Did you get it? If yes, then can you please explain? I've spent 4hrs on this problem, but couldn't come to a conclusion.
In div2 E1 or (div1 B1) how to prove that maximum number of divisors of a number less than 10^5 is 240 (It is given in editorial but no proof has been provided) .Thanks !
Hi. To prove that, you can either factorise all intergers from $$$1$$$ to $$$10^5$$$ to count the number of divisors it has, or just google search for the list of highly composite numbers. For estimation purposes, the number of divisors a number $$$n$$$ has is about $$$O(n^{1/3})$$$
In problem B1, it suffices to iterate through only the prime divisors (taking as k) of the total number of chocolates.
Absolutely
Can anyone explain this for me :"A number ≤10^5 has at most 240 divisors". I tried to create number that can have most divisors but all I found was 128 divisors (120120). Thanks in advance.
So that's why they said "at most" XD... Moreover 120120 is greater than 10^5 XD...
I checked... it's actually 83160 with 128 factors.
okay, got it, thanks!
Sorry, it is in 83160 with 128 divisors. I mistook this problem for the original problem(which has a constraint of 1e6)
thanks, but I still wonder how to get maximum number of divisors for number with value that does not exceed some specified boundary.
Please see my comment above. There also exists a way of backtracking. You just need to backtrack for a sequence of $$$k_1, k_2,...k_n$$$ such that $$$(k_1+1)*(k_2+1)*...*(k_n+1)$$$ is maximum, $$${p_1}^{k_1}*{p_2}^{k_2}*...*{p_n}^{k_n}$$$ $$$\le N$$$ and $$$k_1 \ge k_2 \ge k_3 ... \ge k_n$$$ But on practical I think referring to the highly-composite number list is a more convenient way
thanks, I will note it for later use.
@prof.PVH
pls explain this..
STATEMENT : "Now it is clear that we will divide the array into segments, such that sum of each segment is divisible by K, and move all the chocolates pieces in that segment into one common box."
lets say my input array is : [ 6 7 9 7 6 7 7 ]
now the sum of the array is 49 ...
and optimal divisor(k) for this array would be 7 ...
Why do I need to move all the candies into common box ?
we can see that we need to pass one candy from index '2' to index '0' and one candy from index '2' to index '4'... and that would 4 seconds...
and we are not moving all the candies to any common box..
so can please explain that statement
That statement is about the easy version, where each element is 0 or 1.
snacache
I realised that I after posting the comment :p ... my bad, I opened both questions, and I thougth I was reading E1, but I was actually reading the E2 :p .
I still don't understand tutorial for feeding chicken? Does anyone have better explanation?
You can solve the 1xn problem assigning equal or almost equal quantities of rice fields to each chicken, for example, if there are 32 rice fields and 6 chickens, you go 6, 6, 5, 5, 5, 5, giving the non-rice fields in between the rice fields to the corresponding chicken.
Now "cut" and "stretch" the original rectangle into one long strip or array of 1x(r*c). You can do that in several ways, like zig-zag, spiral, etc, and solve like above.
There is a way that cost $$$O((n+q)\log n)$$$ for problem D.Here it is.
Problem E2 is very nice ! Thank you!
Div2 Task E2 is awesome.
fridge locker is completely a case of circular rotation
In problem E2, is there a proof (or at least help me understand) for this fortunately true statement : " The only concern is that: is there any scenario when there exists some i such that $$$S_i > S_{i+1}$$$, which is indeed a violation? Fortunately, the answer is no. ".? Thanks <3.
_LNHTD_ Did you get it? If yes, then can you please explain? I've spent 4hrs on this problem, but couldn't come to a conclusion.
Div2. E2/ Div1. B2:
"But if you have solved the problem to this phase already, you can easily realize that we only need to consider prime k, because if k is composite then picking any prime divisors of it will lead to either a better result or an equal result."
Why and how?
UPD: Understood. If all $$$a_i$$$ are to be made divisible by some composite say p*q (p and q are primes), then they are also made to be divisible by p and q, at (in the worst case) the same cost. So it is sufficient to only consider the primes (as they guarantee an equal, if not better, answer).
Can you please explain in
Div2E2
, how can we assume that if we are takingk-S[i]%k
fromi+1
th element then it will not become negative ( does it have enough candy to give). The author has said something related to this doubt as'S[i]>S[i+1]'
. Can you give an intuitive proof of this? Thanks in advance.I've already spent hours but couldn't get to any conclusion. the_hyp0cr1t3If $$$S_i \% k \le (k - S_i \% k)$$$, then it is optimal to move $$$S_i \% k$$$ chocolates from $$$S_i$$$ to $$$S_{i+1}$$$.
Otherwise $$$(k - S_i \% k) < S_i \% k$$$. It is optimal to move $$$(k - S_i \% k)$$$ chocolates from $$$S_{i+1}$$$ to $$$S_i$$$. We know that $$$S_{i+1} \geq S_i$$$, so there are at least $$$S_i \% k$$$ chocolates in $$$S_{i+1}$$$. And $$$(k - S_i \% k) < S_i \% k$$$. So there are always enough.
the_hyp0cr1t3 I tried to prove it this way, I do not understand where am I getting wrong
How does Si+1>=Si implies that there are at least Si%k chocolates in Si+1?
$$$S_i$$$ has at least $$$S_i \% k$$$ chocolates, so $$$S_{i+1}$$$ also has at least that many.
Si+1 is greater than Si%k but how can we prove that it is greater than Si+k-Si%k because will be taking chocolates out of ai+1 i.e. si+1-si?
In Div1 B1 why moving all the ones to $$$temp[(i+i+p-1)/2]$$$ is optimal than to moving ones to $$$(temp[i]+temp[i+p-1])/2$$$ ??
Hi, MofK, question regarding following statements:
The only concern is that: is there any scenario when there exists some i such that Si>Si+1, which is indeed a violation?
Since S[i]=sum(a[0]..a[i]), thus S[i+1]-S[i]=a[i+1]. If S[i]>S[i+1], then a[i+1]=S[i+1]-S[i]<0. To my understanding, all a[i], either before or after any operation, should be positive. If I were correct, then there should be no case that S[i]>S[i+1].
Anything I am missing here?
happy15 But how do we make sure that
ai+1
will remain positive after the most optimum choice of operation for that case whenSi%k>k/2
We can enforce the solution to iterate each Si from 1 to n−1 and always choose to decrease if there is a tie
In fact, even if we choose to increase for every tie, we can enforce a non-decreasing sequence. We just have to fix and follow it.
Can you please explain in
Div2E2
, how can we assume that if we are takingk-S[i]%k
fromi+1
th element then it will not become negative ( does it have enough candy to give). The author has said something related to this doubt as 'S[i]>S[i+1]
'. Can you give an intuitive proof of this? I've already spent hours but couldn't get to any conclusion. Thanks in advance. towristHave you understood it.. If yes , kindly explain it to me also.
I am getting
WA
ontest case 7
for the problem1254B1 - Send Boxes to Alice (Easy Version)
, the code seems to be logically correct to me, where am I getting wrong?: 86285300UPD: Fixed
If someone is trying to solve Div1-D by decomposing queries into square root blocks, but getting TLE because of the constant factor introduced by LCA for finding last node on path from $$$u$$$ to $$$v$$$ (given $$$v$$$ is ancestor of $$$u$$$). You can just manually check all adjacent nodes of $$$v$$$ to find the suitable one whenever $$$v$$$ has $$$\leq 5$$$ neighbours, and do normal binary lifting otherwise. Pretests might be slightly weak as this condition significantly reduces runtime.
Very useful bro!!
lol