### vovuh's blog

By vovuh, history, 23 months ago,

1154A - Restoring Three Numbers

Idea: MikeMirzayanov

Tutorial
Solution
#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

vector<int> a(4);
for (int i = 0; i < 4; ++i) {
cin >> a[i];
}
sort(a.begin(), a.end());
cout << a[3] - a[0] << " " << a[3] - a[1] << " " << a[3] - a[2] << endl;

return 0;
}


1154B - Make Them Equal

Idea: MikeMirzayanov

Tutorial
Solution
#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
sort(a.begin(), a.end());
a.resize(unique(a.begin(), a.end()) - a.begin());
if (a.size() > 3) {
cout << -1 << endl;
} else {
if (a.size() == 1) {
cout << 0 << endl;
} else if (a.size() == 2) {
if ((a[1] - a[0]) % 2 == 0) {
cout << (a[1] - a[0]) / 2 << endl;
} else {
cout << a[1] - a[0] << endl;
}
} else {
if (a[1] - a[0] != a[2] - a[1]) {
cout << -1 << endl;
} else {
cout << a[1] - a[0] << endl;
}
}
}

return 0;
}


1154C - Gourmet Cat

Idea: le.mur

Tutorial
Solution
#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

vector<int> a(3);
cin >> a[0] >> a[1] >> a[2];

vector<int> idx({0, 1, 2, 0, 2, 1, 0});

int full = min({a[0] / 3, a[1] / 2, a[2] / 2});
a[0] -= full * 3;
a[1] -= full * 2;
a[2] -= full * 2;

int ans = 0;
for (int start = 0; start < 7; ++start) {
int day = start;
vector<int> b = a;
int cur = 0;
while (b[idx[day]] > 0) {
--b[idx[day]];
day = (day + 1) % 7;
++cur;
}
ans = max(ans, full * 7 + cur);
}

cout << ans << endl;

return 0;
}


1154D - Walking Robot

Idea: MikeMirzayanov

Tutorial
Solution
#include<bits/stdc++.h>

using namespace std;

int a, b, maxa;

void use_battery(int s)
{
if(s == 1) a = min(a + 1, maxa);
--b;
}

void use_accum()
{
--a;
}

int main()
{
int ans = 0;
int n;
cin >> n >> b >> a;
maxa = a;
vector<int> s(n);
for(int i = 0; i < n; i++) cin >> s[i];
for(int i = 0; i < n; i++)
{
if(a == 0 && b == 0)
break;
else if(a == 0)
use_battery(s[i]);
else if(b == 0)
use_accum();
else if(s[i] == 1 && a < maxa)
use_battery(s[i]);
else use_accum();
ans++;
}
cout << ans << endl;
}


1154E - Two Teams

Idea: MikeMirzayanov

Tutorial
Solution
#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

int n, k;
cin >> n >> k;
vector<pair<int, int>> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i].first;
a[i].second = i;
}

sort(a.rbegin(), a.rend());
queue<int> q;
for (int i = 0; i < n; ++i) {
q.push(a[i].second);
}

set<int> idx;
for (int i = 0; i < n; ++i) {
idx.insert(i);
}
string ans(n, '0');
int who = 0;
while (!idx.empty()) {
while (!idx.count(q.front())) {
q.pop();
}
int pos = q.front();
q.pop();

auto it = idx.find(pos);
for (int i = 0; i <= k; ++i) {
if (it == idx.begin()) break;
--it;
}
it = next(idx.find(pos));
for (int i = 0; i < k; ++i) {
if (it == idx.end()) break;
++it;
}
for (auto it : add) {
idx.erase(it);
ans[it] = '1' + who;
}
who ^= 1;
}

cout << ans << endl;

return 0;
}


1154F - Shovels Shop

Idea: MikeMirzayanov

Tutorial
Solution
#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;

int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

int n, m, k;
cin >> n >> m >> k;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}

sort(a.begin(), a.end());
a.resize(k);
reverse(a.begin(), a.end());

vector<int> offers(k + 1);
for (int i = 0; i < m; ++i) {
int x, y;
cin >> x >> y;
if (x <= k) {
offers[x] = max(offers[x], y);
}
}

vector<int> pref(k + 1);
for (int i = 0; i < k; ++i) {
pref[i + 1] = pref[i] + a[i];
}

vector<int> dp(k + 1, INF);
dp[0] = 0;
for (int i = 0; i < k; ++i) {
dp[i + 1] = min(dp[i + 1], dp[i] + a[i]);
for (int j = 1; j <= k; ++j) {
if (offers[j] == 0) continue;
if (i + j > k) break;
dp[i + j] = min(dp[i + j], dp[i] + pref[i + j - offers[j]] - pref[i]);
}
}

cout << dp[k] << endl;

return 0;
}


1154G - Minimum Possible LCM

Idea: MikeMirzayanov

Tutorial
Solution
#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;
const int N = 10 * 1000 * 1000 + 11;

int n;
vector<int> a;

int mind[N];

pair<int, int> mins[N];
vector<pair<int, int>> divs;

void build_sieve() {
vector<int> pr;
mind[0] = mind[1] = 1;
for (int i = 2; i < N; ++i) {
if (mind[i] == 0) {
pr.push_back(i);
mind[i] = i;
}
for (int j = 0; j < int(pr.size()) && pr[j] <= mind[i] && i * pr[j] < N; ++j) {
mind[i * pr[j]] = pr[j];
}
}
}

void add_to_mins(int curd, int idx) {
if(mins[curd].first == -1)
mins[curd].first = idx;
else if(mins[curd].second == -1)
mins[curd].second = idx;
}

void rec(int pos, int curd, int idx) {
if (pos == int(divs.size())) {
return;
}
int curm = 1;
for (int i = 0; i <= divs[pos].second; ++i) {
rec(pos + 1, curd * curm, idx);
curm *= divs[pos].first;
}
}

int value = a[idx];
divs.clear();
while (value > 1) {
int d = mind[value];
if (!divs.empty() && divs.back().first == d) {
++divs.back().second;
} else {
divs.push_back(make_pair(d, 1));
}
value /= d;
}
rec(0, 1, idx);
}

int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif

cin >> n;
a.resize(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
for(int i = 0; i < N; i++)
mins[i] = make_pair(-1, -1);
build_sieve();

vector<pair<int, int> > vals;
for(int i = 0; i < n; i++)
vals.push_back(make_pair(a[i], i));
sort(vals.begin(), vals.end());
for (int i = 0; i < n; ++i) {
if(i > 1 && vals[i].first == vals[i - 2].first) continue;
}

long long l = INF * 1ll * INF;
int ansi = -1, ansj = -1;
for (int i = 1; i < N; ++i) {
pair<int, int> idxs = mins[i];
if (idxs.second == -1) continue;
long long curl = a[idxs.first] * 1ll * a[idxs.second] / i;
if (l > curl) {
l = curl;
ansi = min(idxs.first, idxs.second);
ansj = max(idxs.first, idxs.second);
}
}

cout << ansi + 1 << " " << ansj + 1 << endl;

return 0;
}


• +38

 » 23 months ago, # | ← Rev. 2 →   +8 Could somebody explain the LCM question clearly ? I could not understand the editorial
 » 23 months ago, # |   0 **O(n)** solution for problem **E**: For every index i, we can maintain two links, one for its left, l[i], and another for its right, r[i], pointing to the first yet undecided student on either sides. When we assign a sub-array to a particular team, m, update only the right link of left of leftmost cell, and the left link of right of rightmost cell, provided these cells are not out of bound. In this manner, we iterate over every index at most two times. Link of Code
•  » » 23 months ago, # ^ |   +16 In your code, you're sorting the input array, so complexity is still O(nlogn).
•  » » » 23 months ago, # ^ |   0 Oh sorry, I missed that:)
•  » » » » 23 months ago, # ^ |   +9 You don't need a nlogn sort algorithm in your code. You can do linearly too
•  » » » » 15 months ago, # ^ |   0 you can use counting sort
 » 23 months ago, # |   +8 E can be solved using Linked List if O(n). you just need to implement the operations. since every student will be chosen exactly once so the time complexity is O(n). code: 52920413
•  » » 23 months ago, # ^ |   0 sorting?
•  » » » 23 months ago, # ^ | ← Rev. 2 →   0 If you use a non-comparing sort algorithm. It could be done in linear time.
•  » » » » 23 months ago, # ^ |   0 I don't know of any non-comparison sort algorithm that works in O(n)time. The best I know of is works in O($n\sqrt {log(log(n)}$). Can you tell one that works in linear time.
•  » » » » » 23 months ago, # ^ |   0 Counting sort
•  » » » » » » 23 months ago, # ^ |   0 OK, that would work in this case, as it also depends on the range of input, won't work for larger ranges.
•  » » » 23 months ago, # ^ |   0 if you read my submission you can see that I didn't sort anything!!!
•  » » » » 23 months ago, # ^ |   0 Can you explain your O(n) solution.
•  » » » » » 23 months ago, # ^ |   0 build a Linked List and every time you are removing a student remove him and his k left and his k right students from the Linked List.
•  » » » » » » 23 months ago, # ^ |   -6 But finding the max in remaining list will take O(n). so it will be O(n*n) solution.
•  » » » » » » » 23 months ago, # ^ |   +4 You don't need to find that and nor need to sort it. Since all students are between 1 to N and occur exactly once just create an array to point out their location in the linked list.Whenever you remove a student just clear this pointer.Keep a pointer to last maximum player used and decrement this until a player which exists in the linked list!
•  » » » » » » » 7 months ago, # ^ |   0 you can see my solution it o(n) and do not use the sorting 90431019
•  » » 23 months ago, # ^ |   +3 Honestly for the first time I saw the use of linked list making a solution optimal. Very good approach
 » 23 months ago, # |   +3 could you tell me about solution you mentioned in first line or provide a link (in problem G).
 » 23 months ago, # |   +2 Such a fine editorial !
 » 23 months ago, # |   +13 My approach to problem G : let G = gcd(A,B) so we can write A = GR B = GS Now, lcm(A,B) = AB/gcd(A,B) = AB/G = GRS We need to minimize GRS Here G is common factors between two numbers R is uncommon factors in number A S is uncommon factors in number BSo we iterate on G (which will be <= 10^7) and for each G we store smallest two multiples of G which are present in our array. Say those multiples are A,B. Now G(A/G)(B/G) (lets denote it with Z) is our best possible answer with G as gcd.We find minimum value of Z for all the possible values of G and print corresponding indices as required.NOTE The declaration of A = GR and B = GS requires R and S to be coprime (gcd(R,S) = 1). While finding Z for G , We may have gcd(A,B) > G but it will always be multiple of G (think why). Thus gcd(R,S) = k Now gcd(A,B) = kG. Even if answer Z stored for G will be G(A/G)(B/G) = Gk2RS ,when calculation answer Z for kG (G') as gcd we will get Z as G'(A/G')(B/G') = kGRS which is actual answer.Link to my solution!
•  » » 23 months ago, # ^ |   +3 Ca you exaplain your code little bit?? Thanks in advance.
•  » » » 23 months ago, # ^ |   +4 take a look at my code , I believe its the same idea for each x in range of 1e7 get the minimum two numbers ( a , b ) which are divisible by xthe answer will be ( a * b / x ) C++ Solution
•  » » » » 23 months ago, # ^ |   0 My code was a bit messy! Thanks RamiZk for providing an excellent implementation! vivek8420 you can have a look at his implementation it's super clean and easy to understand.
•  » » » » » 23 months ago, # ^ |   +3 My pleasure
•  » » » » 3 months ago, # ^ |   0 Thanks a lot for this nice implementation.
•  » » » » 2 weeks ago, # ^ |   0 i m hack your solution with test case: 2 7888889 7888890 easy
•  » » » » » 2 weeks ago, # ^ |   0 You realize that it's not a valid input , don't you ?
•  » » » » » » 13 days ago, # ^ |   0 not. everything is correct. n >= 2 && a[1] <= 1e7 && a[2] <= 1e7
•  » » » » » » 13 days ago, # ^ |   0 oh sorry. it turns out that your solution works correctly)
•  » » 23 months ago, # ^ |   0 What is the time complexity of your solution?
•  » » » 23 months ago, # ^ |   +3 O(Nlog(N))
•  » » 23 months ago, # ^ |   +3 Thanks for the explanation! It helped :)
•  » » » 23 months ago, # ^ |   0 Glad I could help! :)
•  » » 22 months ago, # ^ | ← Rev. 2 →   0 Really easy to understand :).Successfully implemented my submission based on your approach. As per your Note: So basically we are ignoring those G whose gcd(A, B) = kG, because, there will be a gauranteed G' which is gcd of same (A,B) but provides a better(minimum) LCM.Also, you don't need to check for if(m < a[i]) and if(m < b[i]), as this will never happen. (since m is directely proportional to j given a fixed i). i.e. (my soln)
•  » » » 22 months ago, # ^ |   +1 Yup you got it right!Yes I could have ignored that. Just a messy implementation on my part.Thanks for sharing your implementation! :)
 » 23 months ago, # |   0 in problem c: why we take the modules day:=(day+1)%7 ?
•  » » 23 months ago, # ^ |   0 To wrap around. Suppose start day is 5 and you want to iterate till 5 more days, doing day = day + 1 gives you 5, 6, 7, 8, 9(but you have only 7(0 to 6) days). When you do (day+1)%7, it wraps around after 6 like 5, 6, 0, 1, 2.
•  » » 23 months ago, # ^ |   0 That because we want the index of the current day If you just increase it, day will be bigger than the last index of the vector (last index =6) so you want the day to go to the first element after the last one, so you put day%7 Let's say that the day =6 and there is nothing after 6 and you want it to go back to first element, day=(6+1)%7 = 0, and you are again on the index 0 Actually you also can do it like this : If day == 7: day = 0 :))
 » 23 months ago, # |   0 the problem G. As far as I know, $\sum_{i \le x}d(i) = O(x \log x)$, where $d(i)$ is the number of divisors of n. So time complexity is equal $O(a \log a)$, maybe it is equal $O(n \log a + a)$. Can you point me other $O(a \log a)$ simple solution?
 » 23 months ago, # |   0 In problem D, in the second example 6 2 1 1 0 0 1 0 1How is the answer 3? It should be 5 right? Because we can use a battery in first segment so battery decreases by one and accumulator increases by one ==> b=1 , a=2. For the next 2 segments we use 2 accumulators ==> b=1,a=0. The for the fourth segment we use a battery ==> b=0,a=1.For the fifth we use the accumulator!Can anybody explain how the answer is 3?
•  » » 23 months ago, # ^ |   0 It is mentioned in the question that charge of accumulator cannot exceed it's maximum capacity. "If the current segment is exposed to sunlight and the robot goes through it using the battery, the charge of the accumulator increases by one (of course, its charge can't become higher than it's maximum capacity)." So when we make first move using battery the charge of accumulator wont increment to 2 as it is already at it's maximum capacity (1).
•  » » » 23 months ago, # ^ |   +3 I just figured it out and saw your comment. Thanks :)
 » 23 months ago, # |   0 Because it was said about optimization, I would like to give some. First, the provided code find all divisors any number $a$ in not $O(d(a))$, because to find one divisor required between $\Omega(k)$ and $O(d(n))$, where $k$ is the amount of unique prime divisors. it needs to be changed by itarative algorithm. Second it's necessary to sort the array a. I thinks both tips will reduce the running time.
 » 23 months ago, # |   +4 Solution of E NlogN: https://codeforces.com/contest/1154/submission/52892001 Create segment Tree with = on segment and take maximum on segment Also create segment tree with add on segment and sum on segment And segment tree for calc Ans, with = on segment, and take value in the point
•  » » 23 months ago, # ^ |   0 it's very hard way to solve this problem)) We can also solve it using set of pair (value, index) and two array left[n], right[n], which point for unchosen elemnts indexes of their left and right closest unchosen elements.
•  » » » 23 months ago, # ^ | ← Rev. 2 →   +2 I know this, but I write them, because this hard, special for this))
 » 23 months ago, # |   0 Thanks for hosting the nice round. I don't quite understand the iterator part of the problem E. If I didn't read it wrong, the iterator --it and ++it are supposed to refer to the original index of the students. If it is so, how do we deal with cases when the next students the couch has to choose is out of reach of k steps (i.e. some of them in between have be chosen in previous rounds)?
•  » » 23 months ago, # ^ | ← Rev. 2 →   +1 The students that already been chosen in between are getting removed from the set at the end of each turn. In the editorial, it is written that we iterate the "add" array (that holds all students that were picked in the current turn) and delete all students in the "add" array from the total students set. Thus, in the next turn, the "students in between" that have already been chosen aren't in the students set anymore.
 » 23 months ago, # |   +3 I have changed my opinion about Div3 contests. In this contest the last 3 problem was intresting ans usefull for some experts, imho
 » 23 months ago, # | ← Rev. 2 →   0 Can Anyone help me finding bug in my Recursive DP approach on problem F : https://codeforces.com/contest/1154/submission/52944910 Thanks in Advance..Update: Done !! Recursive DP solution: https://codeforces.com/contest/1154/submission/52951559
 » 23 months ago, # |   0 In problem F editorial can someone please explain this statement"If shovel A is for free, then we may "swap" shovels A and C, otherwise we may swap shovels A and B, and the answer won't become worse"
•  » » 23 months ago, # ^ |   0 Can't understand the same :(
•  » » » 23 months ago, # ^ |   0 I think two swap A and C would mean include C in previous offer instead of A and buy A in next offer. Similarly for A and B.
 » 23 months ago, # |   0 F can be solved in O(k^2). First, any deals requiring us buy more than k shovels can be immediately discarded since the problem tells us to buy exactly k shovels. We are left with a subset of deals that have us buy between 1 and k shovels. This means that if we have an array deals[] with each element i corresponding to us having to buy i number of shovels we can simply find the maximum free for every index of this array. therefore, we since this array is size k, instead of running through every single deal, we only have to run through these, giving the solution a time complexity of k^2
•  » » 23 months ago, # ^ |   0 Can you please elaborate your solution? I don't think only knowing the maximum amount of free shovels that can be bought will solve the problem.
•  » » » 23 months ago, # ^ |   +1 https://codeforces.com/blog/entry/66560?#comment-506047I tried to explain a similar solution to problem F here. Hope it helps!
•  » » » » 23 months ago, # ^ |   +3 Thanks a lot! It helped :)
 » 22 months ago, # |   0 Hi, In question D, the editorial says to use accumulator if we can't increase it and specifies if the optimal solution does this in reverse(using battery first at current time and accumulator ahead) then usage of battery does not grant us any additional charges and we can swap our decisions at this point, I am unable to wrap my head around this statement. Does this mean that had we used battery we would have battery capacity one less than now, and accumulator same, and if we don't use it then we have capacity on battery 1 more than it would have been in optimal solution but accumulator charge is one less, how is this a win-win situation ?
•  » » 4 months ago, # ^ |   0 Hi, I have the same query, were you able to find the reason as to why it's optimal?
 » 19 months ago, # |   0 Hello can anyone explain this paragraph further more I can't get its idea: Why should the sets of shovels for all purchases be consecutive subarrays? Suppose it's not so: let's pick two purchases such that they are "mixed" in the array of costs, i. e. there exists at least one shovel A bought in the first purchase such that there exists a shovel B cheaper than it and a shovel C more expensive than it, both bought in the second purchase. If shovel A is for free, then we may "swap" shovels A and C, otherwise we may swap shovels A and B, and the answer won't become worse. So, we can do it until all purchases correspond to subsegments in the array of costs.
 » 12 months ago, # | ← Rev. 2 →   0 How we can solve problem E if we have to choose a student which the summation of k closest students to the left and right is maximized?Sorry for my english
 » 10 months ago, # |   0 The number of inputs in the test is bigger than the data type that I use. Please help me solve this problem, I am using Java.
 » 9 months ago, # |   +8 Could anyone explain a "very easy" O(a log a) solution to G? AFAIK, all the comments here are somewhat related to the official solution in the editorial, but I'd like to know the other one(s). I just can't understand the solutions from the round as is, so thanks in advance!
•  » » 6 months ago, # ^ |   0 This is a very simple O(MAXlog(MAX) + Nlog(N)) solution, where MAX is 1e792523482
 » 5 months ago, # |   0 Someone please explain my segfault for D https://codeforces.com/contest/1154/submission/95521763