Solution of Codeforces Round #824 — editorial

Codeforces Round #824 — editorial

1735A - Working Week

Hint1

Let's consider that l1$l_1$, l2$l_2$, and l3$l_3$ are sorted working segments. Can we explicitly say something about one of them?

Answer to Hint1

l1$l_1$ must be equal to 1$1$.

Solution

Let's consider that l1$l_1$, l2$l_2$, and l3$l_3$ are sorted working segments.

If l1$l_1$ is not equal to 1$1$ then we can decrease l1$l_1$ by 1$1$ and increase l3$l_3$ by 1$1$. So we'll increase the answer.

We've got that l1=1$l_1=1$ and we have to work just with l2$l_2$ and l3$l_3$.

Now, our problem can be rewritten as:
l2+l3=n−4$l_2+l_3=n-4$, maximize min(l2−1,l3−l2)$min(l_2-1,l_3-l_2)$.

And as we know that l3=n−4−l2$l_3=n-4-l_2$, just:
maximize min(l2−1,n−4−2⋅l2)$min(l_2-1,n-4-2\cdot l_2)$.

If we increase both values under the minimum scope by one, solutions don't change:
maximize min(l2,(n−3)−2⋅l2)$min(l_2,(n-3)-2\cdot l_2)$.

If we choose l2=⌊n−33⌋$l_2=\lfloor \frac{n-3}{3}\rfloor$, then min(l2,(n−3)−2⋅l2)=⌊n−33⌋$min(l_2,(n-3)-2\cdot l_2)=\lfloor \frac{n-3}{3}\rfloor$.
If the answer is greater, then l2>n−33$l_2>\frac{n-3}{3}$ and (n−3)−2⋅l2>n−33$(n-3)-2\cdot l_2>\frac{n-3}{3}$, and it means that 2⋅(l2)+((n−3)−2⋅l2)>n−3$2\cdot (l_2)+((n-3)-2\cdot l_2)>n-3$ but 2⋅(l2)+((n−3)−2⋅l2)=n−3$2\cdot (l_2)+((n-3)-2\cdot l_2)=n-3$.

The only thing is left to do is to calculate final answer. And it is ⌊n−33⌋−1$\lfloor \frac{n-3}{3}\rfloor -1$ or just ⌊n3⌋−2$\lfloor \frac{n}{3}\rfloor -2$.

It was a mathematician way of solving. As it's pretty obvious that l2$l_2$ is approximately n3$\frac{n}{3}$, you could check l2=n3±5$l_2=\frac{n}{3}\pm 5$ and choose the best among them.

Code

174443363

1. #include <bits/stdc++.h>
3. using namespace std;
5. void solve() {
6. int n;
7. cin >> n;
8. int l_2 = (n - 3) / 3;
9. int ans = l_2 - 1;
10. cout << ans << '\n';
11. }
13. int main() {
14. ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
15. int t = 1;
16. cin >> t;
17. while (t--)
18. solve();
20. return 0;
21. }

1735B - Tea with Tangerines

Hint1

Is there a way to cut pieces to save the minimum value and satisfy required conditions?

Hint2

What is the minimum possible number of operations to perform it?
Is there any better solution?

Solution

Let's start with a simple solution.

Let's choose the minimum piece from a$a$ and assume that it will remain the minimum until the end.
As the array is sorted, let's define the minimum piece as a1$a_1$.
It means that in the end, all pieces must be smaller or equal to 2⋅a1−1$2\cdot a_1-1$.

The lower bound of the answer for this solution is ∑i=1n⌈ai2⋅a1−1⌉${\displaystyle \sum _{i=1}^n\lceil \frac{a_i}{2\cdot a_1-1}\rceil }$.

Let's show that this is achievable.
For each piece, while its size greater than 2⋅a1−1$2\cdot a_1-1$, let's cut off a piece of size 2⋅a1−1$2\cdot a_1-1$.
The only problem is that we could get a piece smaller than a1$a_1$ in the end.
But it means that before the last cut we had a piece in the range [2⋅a1,3⋅a1−2]$[2\cdot a_1,3\cdot a_1-2]$. All pieces in this range can be easily cut into pieces of the right size in one move.

The only left question is why the minimum piece in the end should have size a1$a_1$. Actually, it shouldn't, but it gives the best answer anyway.
As was described above, the lower bound of the solution with the minimal piece of size x$x$ in the end is ∑i=1n⌈ai2⋅x−1⌉${\displaystyle \sum _{i=1}^n\lceil \frac{a_i}{2\cdot x-1}\rceil }$.
Having a minimal piece with a smaller size, we can't get anything better, because the lower bound will be equal or greater for all x<a1$x<a_1$.

Code

174443424

1. #include <bits/stdc++.h>
3. using namespace std;
5. int n;
6. vector<int> a;
8. void solve() {
9. cin >> n;
10. a.resize(n);
11. int ans = 0;
12. for (auto &i : a) {
13. cin >> i;
14. ans += (i - 1) / (2 * a[0] - 1);
15. }
16. cout << ans << '\n';
17. }
19. int main() {
20. ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
21. int t = 1;
22. cin >> t;
23. while (t--)
24. solve();
26. return 0;
27. }

1735C - Phase Shift

Hint1

What is the first letter in the answer?

Answer to Hint1

a$a$ if t$t$ doesn't start with a$a$ and b$b$ otherwise.

Hint2

Ask the same question as Hint1 for each position.

Hint3

When we can't choose the minimum unused letter?

Answer to Hint3

If we form a circle of size less then 26$26$.
Maintain any structure to check it.

Solution

First of all, the encryption process is reversible. If we obtained t$t$ from s$s$ using the circle c$c$, we can obtain s$s$ from t$t$ using the same cycle c$c$, but reversed.
So, let's think in terms of encryption of t$t$.

Lexicographical order itself is a greedy thing. So, we can create a greedy algorithm.

Let's go from left to right and generate the result letter by letter. We have to choose the best possible option at each step. Let's describe the options we have.

• If the current letter was used earlier, we already know the replacement we need to choose.
• Otherwise, we would like to choose the minimum possible option. We need to maintain some structure to know what is acceptable.

Let's keep the circle that is already generated(it's a graph). For each letter we have one incoming edge and one outgoing edge in the end. Let's keep them for every letter: arrays in[26]$in[26]$, out[26]$out[26]$.
When we want to generate an outgoing edge at some step(let's define the letter on this step as x$x$), we have to choose the minimum letter that doesn't have an incoming edge yet. With one exception: if creating the edge using this rule creates a circle of size less than 26$26$. It would mean that we wouldn't have a full circle in the end. It's easy to see that there is no more than one such letter, as this letter is just the end of a chain starting in x$x$.
To check that a small circle wasn't generated, we can go along an outgoing edge 26$26$ times, starting at x$x$. If we end up in x$x$ or there was no edge at some step then everything is ok, we can create this edge.

Complexity is O(26⋅26+n)$\mathcal{O}(26\cdot 26+n)$, that is, O(n)$\mathcal{O}(n)$.

Code

174443480

1. #include <bits/stdc++.h>
3. using namespace std;
5. int n;
6. vector<int> a;
8. void solve() {
9. cin >> n;
10. a.resize(n);
11. int ans = 0;
12. for (auto &i : a) {
13. cin >> i;
14. ans += (i - 1) / (2 * a[0] - 1);
15. }
16. cout << ans << '\n';
17. }
19. int main() {
20. ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
21. int t = 1;
22. cin >> t;
23. while (t--)
24. solve();
26. return 0;
27. }

1735D - Meta-set

Hint1

How many sets can fit in 5$5$ cards?

Answer to Hint1

At most two.
If there are two sets among 5$5$ cards, there will be a central card.
Consider each card as a central card.

Solution

For every two cards, there is always a single card that forms a set with them.
[1] That means that two sets can share at most one card.

Let's prove that there are no more than 2$2$ sets in a meta-set.
Let's define 5$5$ cards as c1,c2,c3,c4,c5$c_1,c_2,c_3,c_4,c_5$. Let's guess that (c1,c2,c3)$(c_1,c_2,c_3)$ is a set.
All other sets can have at most one card among (c1,c2,c3)$(c_1,c_2,c_3)$ (according to [1]), so they must include c4$c_4$ and c5$c_5$. So we have at most one other set, otherwise they would have two same cards, which is prohibited according to [1].

So, every meta-set looks like 2$2$ sets with one common card. Let's call this card a central card.

Now there is just a simple combinatorics. For each card, we want to know the number of sets that include it. If this number is s$s$, then we should add s(s−1)2$\frac{s(s-1)}{2}$ to the answer — it is the number of meta-sets with this card as a central card.

To get the number of sets for each card, we can iterate over all pairs of cards (i,j)$(i,j)$, generate the complement to the set, and add 1$1$ to that card in a map/hashmap.

Complexity is O(kn2log(n))$\mathcal{O}(k{n}^2\log (n))$ or O(kn2)$\mathcal{O}(k{n}^2)$.

Code

174443540

1. #include <bits/stdc++.h>
3. using namespace std;
5. #define F first
6. #define S second
7. typedef long long ll;
8. typedef long double ld;
9. typedef pair<ll, ll> pll;
10. typedef pair<int, int> pii;
12. const long long kk = 1000;
13. const long long ml = kk * kk;
14. const long long mod = ml * kk + 7;
15. const long long inf = ml * ml * ml + 7;
16. #ifdef DEBUG
17. mt19937 rng(1033);
18. #else
19. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
20. #endif
21. int rnd(int mod) { return uniform_int_distribution<int>(0, mod - 1)(rng); }
24. bool viv = false;
25. int n, k;
26. vector<vector<int>> v;
28. vector<int> get_comp(vector<int> a, vector<int> b) {
29. vector<int> res(k);
30. for (int i = 0; i < k; i++)
31. res[i] = (6 - (a[i] + b[i])) % 3;
32. return res;
33. }
35. void solve() {
36. cin >> n >> k;
37. v.resize(n);
38. for (auto &vec : v) {
39. vec.resize(k);
40. for (auto &i : vec)
41. cin >> i;
42. }
43. map<vector<int>, int> cnt;
44. for (int i = 0; i < n; i++) {
45. for (int j = i + 1; j < n; j++) {
46. auto comp = get_comp(v[i], v[j]);
47. cnt[comp]++;
48. }
49. }
50. ll ans = 0;
51. for (auto vec : v) {
52. ans += (ll)cnt[vec] * (cnt[vec] - 1) / 2;
53. }
54. cout << ans << '\n';
55. }
57. int main() {
58. // viv = true;
59. ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
60. cout << fixed << setprecision(20);
61. int t = 1;
62. // cin >> t;
63. while (t--)
64. solve();
66. #ifdef DEBUG
67. cerr << "Runtime is: " << clock() * 1.0 / CLOCKS_PER_SEC << endl;
68. #endif
69. }

1735E - House Planning

Hint1

How many possible options are there for the distance between p1$p_1$ and p2$p_2$.

Answer to Hint1

We can limit it with 2⋅n$2\cdot n$ options.
Consider options d1[1]+d2[i]$d_1[1]+d_2[i]$, |d1[1]−d2[i]|$|d_1[1]-d_2[i]|$. Solve each one in linear(almost) time.

Hint2

Consider the biggest distance among d1$d_1$ and d2$d_2$.
Can we match it with something?

Hint3

Remove them one by one while they exceed the distance between p1$p_1$ and p2$p_2$. Then the problem is trivial.

Solution

Let's assume that considered point p1$p_1$ was to the left of considered point p2$p_2$.
Let's assume that we know the distance l$l$ between considered points p1$p_1$ and p2$p_2$. Let's show how to solve this problem in linear time(almost linear).

As long as there is a value greater than l$l$, let's get the largest among them(let's call it x$x$). Let's assume that this value is from d1$d_1$.
It's easy to see that this point is to the right of the considered point p2$p_2$ (because the largest distances is to the point p1$p_1$). It means that we can match distance x$x$ from d1$d_1$ to the distance x−l$x-l$ from d2$d_2$.

When there is no value greater than l$l$, all other houses are located between considered points. We can match them by sorting.

That is the O(nlog(n))$\mathcal{O}(nlog(n))$ solution.

Let's limit possible options of l$l$ with O(n)$\mathcal{O}(n)$ options.
If we know that some house has distances x$x$ and y$y$ to considered options, then there are 2$2$ options of l$l$: x+y$x+y$ and |x−y|$|x-y|$.
Let's consider 2⋅n$2\cdot n$ options d1[1]+d2[i]$d_1[1]+d_2[i]$, |d1[1]−d2[i]|$|d_1[1]-d_2[i]|$.

Complexity is O(n2log(n))$\mathcal{O}(n^{2}log(n))$.

Code

174443587

1. #include <bits/stdc++.h>
3. using namespace std;
5. #define F first
6. #define S second
7. typedef long long ll;
8. typedef long double ld;
9. typedef pair<ll, ll> pll;
10. typedef pair<int, int> pii;
12. const long long kk = 1000;
13. const long long ml = kk * kk;
14. const long long mod = ml * kk + 7;
15. const long long inf = ml * ml * ml + 7;
16. #ifdef DEBUG
17. mt19937 rng(1033);
18. #else
19. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
20. #endif
21. int rnd(int mod) { return uniform_int_distribution<int>(0, mod - 1)(rng); }
24. bool viv = false;
25. int n;
26. vector<int> d1, d2;
28. bool work(int points_diff) {
29. int p1 = 0;
30. int p2 = points_diff;
32. multiset<int, greater<int>> s1, s2;
33. for (auto i : d1)
34. s1.insert(i);
35. for (auto i : d2)
36. s2.insert(i);
39. auto farthest = [] (multiset<int, greater<int>> &s) {
40. return s.empty() ? -1 : *s.begin();
41. };
42. auto farthest_both = [&]() {
43. return max(farthest(s1), farthest(s2));
44. };
46. vector<int> ans;
47. while (farthest_both() > points_diff) {
48. bool choose_s1 = farthest(s1) > farthest(s2);
49. auto &s_far = choose_s1 ? s1 : s2;
50. auto &s_near = choose_s1 ? s2 : s1;
52. int value = *s_far.begin();
53. int complem = value - points_diff;
54. if (!s_near.count(complem))
55. return false;
57. s_far.erase(s_far.find(value));
58. s_near.erase(s_near.find(complem));
60. if (choose_s1)
61. ans.push_back(p1 + value);
62. else
63. ans.push_back(p2 - value);
64. }
66. vector<int> left1, left2;
67. for (auto i : s1)
68. left1.push_back(i);
69. for (auto i : s2)
70. left2.push_back(i);
71. sort(left1.begin(), left1.end());
72. sort(left2.rbegin(), left2.rend());
74. for (int i = 0; i < left1.size(); i++)
75. if (left1[i] + left2[i] != points_diff)
76. return false;
78. for (auto i : left1)
79. ans.push_back(i);
81. sort(ans.begin(), ans.end());
82. int sh = max(-ans[0], 0);
83. p1 += sh, p2 += sh;
84. for (auto &i : ans)
85. i += sh;
87. cout << "YES\n";
88. for (auto i : ans)
89. cout << i << ' ';
90. cout << '\n';
91. cout << p1 << ' ' << p2 << '\n';
92. return true;
93. }
95. void solve() {
96. cin >> n;
97. d1.resize(n);
98. d2.resize(n);
99. for (auto &d : d1)
100. cin >> d;
101. for (auto &d : d2)
102. cin >> d;
104. int dist1 = d1[0];
105. for (auto dist2 : d2) {
106. if (work(dist1 + dist2))
107. return;
108. if (work(abs(dist1 - dist2)))
109. return;
110. }
112. cout << "NO\n";
113. }
115. int main() {
116. // viv = true;
117. ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
118. cout << fixed << setprecision(20);
119. int t = 1;
120. cin >> t;
121. while (t--)
122. solve();
124. #ifdef DEBUG
125. cerr << "Runtime is: " << clock() * 1.0 / CLOCKS_PER_SEC << endl;
126. #endif
127. }

1735F - Pebbles and Beads

Solution

Will be added soon

Code

174443858

1. #include <bits/stdc++.h>
3. using namespace std;
5. #define F first
6. #define S second
7. typedef long long ll;
8. typedef long double ld;
9. typedef pair<ll, ll> pll;
10. typedef pair<int, int> pii;
12. const long long kk = 1000;
13. const long long ml = kk * kk;
14. const long long mod = ml * kk + 7;
15. const long long inf = ml * ml * ml + 7;
16. const ld eps = 1e-9;
17. #ifdef DEBUG
18. mt19937 rng(1033);
19. #else
20. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
21. #endif
22. int rnd(int mod) { return uniform_int_distribution<int>(0, mod - 1)(rng); }
25. int n, a, b;
26. vector<int> p, q;
29. struct Seg {
30. ll init_x, init_y;
31. int num;
32. ld x, y;
33. Seg() {}
34. Seg(int p, int q, int num): init_x(q), init_y(-p), num(num) {
35. x = init_x;
36. y = init_y;
37. }
39. friend bool operator<(const Seg &s1, const Seg &s2) {
40. if (s1.init_x * s2.init_y == s1.init_y * s2.init_x)
41. return s1.num < s2.num;
42. return s1.init_x * s2.init_y < s1.init_y * s2.init_x;
43. }
44. Seg operator*=(ld ratio) { x *= ratio; y *= ratio; return *this; }
46. void show() {
47. cout << "Seg(" << x << ' ' << y << ")";
48. }
49. };
51. struct Point {
52. ld x, y;
53. Point() {}
54. Point(int a, int b): x(b), y(a) {}
55. Point operator+=(const Point &v) { x += v.x; y += v.y; return *this; }
56. Point operator-=(const Point &v) { x -= v.x; y -= v.y; return *this; }
57. Point operator+=(const Seg &v) { x += v.x; y += v.y; return *this; }
58. Point operator-=(const Seg &v) { x -= v.x; y -= v.y; return *this; }
60. void show() {
61. cout << "Point(" << x << ' ' << y << ")";
62. }
63. };
66. struct Stock {
67. Point best_a;
68. Point best_b;
69. multiset<Seg> segs;
71. Stock(int a, int b) {
72. best_a = Point(a, 0);
73. best_b = Point(0, b);
75. Seg seg_1 = Seg(a, 0, -2);
76. Seg seg_2 = Seg(0, b, -1);
77. if (a)
78. segs.insert(seg_1);
79. if (b)
80. segs.insert(seg_2);
81. }
83. void add_seg(int p, int q, int num) {
84. Seg new_seg = Seg(2 * p, 2 * q, num);
85. segs.insert(new_seg);
87. Point shift(p, -q);
88. best_a += shift;
89. best_b -= shift;
91. cut_left();
92. cut_down();
93. }
95. void cut_left() {
96. while (best_a.x < 0) {
97. Seg l_seg = *segs.begin();
98. Point new_best_a = best_a;
99. new_best_a += l_seg;
101. if (new_best_a.x > eps) {
102. ld ratio = new_best_a.x / l_seg.x;
103. Seg l_seg_left = l_seg;
104. l_seg_left *= ratio;
105. segs.erase(segs.find(l_seg));
106. segs.insert(l_seg_left);
107. new_best_a -= l_seg_left;
108. new_best_a.x = max(new_best_a.x, (ld)0);
109. } else {
110. segs.erase(segs.begin());
111. }
112. best_a = new_best_a;
113. }
114. }
116. void cut_down() {
117. while (best_b.y < 0) {
118. Seg d_seg = *segs.rbegin();
119. Point new_best_b = best_b;
120. new_best_b -= d_seg;
122. if (new_best_b.y > eps) {
123. ld ratio = new_best_b.y / -d_seg.y;
124. Seg d_seg_left = d_seg;
125. d_seg_left *= ratio;
126. segs.erase(segs.find(d_seg));
127. segs.insert(d_seg_left);
128. new_best_b += d_seg_left;
129. new_best_b.y = max(new_best_b.y, (ld)0);
130. } else {
131. segs.erase(segs.find(d_seg));
132. }
133. best_b = new_best_b;
134. }
135. }
137. void print_best() {
138. cout << best_a.y << '\n';
139. }
141. void show() {
142. cout << "----\tStock\t----\n";
143. cout << "best_a = ";
144. best_a.show();
145. cout << endl;
147. Point cur = best_a;
148. for (auto seg : segs) {
149. cur += seg;
150. cout << "\t";
151. cur.show();
152. cout << endl;
153. }
155. cout << "best_b = ";
156. best_b.show();
157. cout << endl;
158. cout << "----\tEnd\t----\n\n";
159. }
160. };
162. void solve() {
163. cin >> n >> a >> b;
164. p.resize(n);
165. q.resize(n);
166. for (int i = 0; i < n; i++)
167. cin >> p[i];
168. for (int i = 0; i < n; i++)
169. cin >> q[i];
171. Stock st(a, b);
172. for (int i = 0; i < n; i++) {
173. st.add_seg(p[i], q[i], i);
174. st.print_best();
175. }
177. }
179. int main() {
180. ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
181. cout << fixed << setprecision(20);
182. int t = 1;
183. cin >> t;
184. while (t--)
185. solve();
187. #ifdef DEBUG
188. cerr << "Runtime is: " << clock() * 1.0 / CLOCKS_PER_SEC << endl;
189. #endif
190. }