1714A - Everyone Loves to Sleep

Idea: Vladosiya

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
#define int long long
#define pb emplace_back
#define mp make_pair
#define x first
#define y second
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
typedef long double ld;
typedef long long ll;
using namespace std;
mt19937 rnd(143);
const int inf = 1e15;
const int M = 1e9 + 7;
const ld pi = atan2(0, -1);
const ld eps = 1e-6;
void solve(){
int n;
cin >> n;
int time, h, m;
cin >> h >> m;
time = 60 * h + m;
int ans = 24 * 60;
for(int i = 0; i < n; ++i){
cin >> h >> m;
int t = 60 * h + m - time;
if(t < 0) t += 24 * 60;
ans = min(ans, t);
}
cout << ans / 60 << " " << ans % 60;
}
bool multi = true;
signed main() {
int t = 1;
if (multi)cin >> t;
for (; t; --t) {
solve();
cout << endl;
}
return 0;
}
```

Idea: MikeMirzayanov

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); i++)
int main() {
int t;
cin >> t;
forn(tt, t) {
int n;
cin >> n;
vector<int> a(n);
forn(i, n)
cin >> a[i];
bool yes = false;
set<int> c;
for (int i = n - 1; i >= 0; i--) {
if (c.count(a[i])) {
cout << i + 1 << endl;
yes = true;
break;
}
c.insert(a[i]);
}
if (!yes)
cout << 0 << endl;
}
}
```

Idea: MikeMirzayanov

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); i++)
int main() {
int t;
cin >> t;
forn(tt, t) {
int s;
cin >> s;
string result;
for (int d = 9; d >= 1; d--)
if (s >= d) {
result = char('0' + d) + result;
s -= d;
}
cout << result << endl;
}
}
```

1714D - Color with Occurrences

Idea: MikeMirzayanov

**Tutorial**

Tutorial is loading...

**Solution**

```
#include<bits/stdc++.h>
#define len(s) (int)s.size()
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
int ans = 0;
bool ok = true;
void Find(int a, int b, string &t, vector<string>&str, vector<pair<int, int>>&match){
int Max = 0, id = -1, pos = -1;
for(int i = a; i <= b; i++){
for(int j = 0; j < len(str); j++){
string s = str[j];
if(i + len(s) > len(t) || i + len(s) <= b) continue;
if(t.substr(i, len(s)) == s) {
if(i + len(s) > Max){
Max = i + len(s);
id = j;
pos = i;
}
}
}
}
if(id == -1) {
ok = false;
return;
}
else{
match.emplace_back(id, pos);
ans++;
if(Max == len(t)) return;
else Find(max(pos + 1, b +1), Max, t, str, match);
}
}
void solve(){
ans = 0;
ok = true;
string t;
cin >> t;
int n;
cin >> n;
vector<string>s(n);
vector<pair<int, int>>match;
forn(i, n) {
cin >> s[i];
}
Find(0, 0, t, s, match);
if(!ok) cout << "-1\n";
else{
cout << ans << endl;
for(auto &p : match) cout << p.first + 1 << ' ' << p.second + 1 << endl;
}
}
int main(){
int q;
cin >> q;
while(q--){
solve();
}
return 0;
}
```

Idea: DmitriyOwlet

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
using namespace std;
int next(int x) {
return x + x % 10;
}
void solve() {
int n;
cin >> n;
vector<int> a(n);
bool flag = false;
for (int i = 0; i < n; ++i) {
cin >> a[i];
if (a[i] % 5 == 0) {
flag = true;
a[i] = next(a[i]);
}
}
if (flag) {
cout << (*min_element(a.begin(), a.end()) == *max_element(a.begin(), a.end()) ? "Yes": "No") << '\n';
} else {
bool flag2 = false, flag12 = false;
for (int i = 0; i < n; ++i) {
int x = a[i];
while (x % 10 != 2) {
x = next(x);
}
if (x % 20 == 2) {
flag2 = true;
} else {
flag12 = true;
}
}
cout << ((flag2 & flag12) ? "No" : "Yes") << '\n';
}
}
int main() {
int t = 1;
cin >> t;
for (int it = 0; it < t; ++it) {
solve();
}
return 0;
}
```

1714F - Build a Tree and That Is It

Idea: MikeMirzayanov

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); i++)
int main() {
int t;
cin >> t;
forn(tt, t) {
int n;
cin >> n;
vector<int> d(3);
forn(i, 3)
cin >> d[i];
int sum = d[0] + d[1] + d[2];
if (sum % 2 == 0) {
vector<int> w(3);
forn(i, 3)
w[i] = sum / 2 - d[(i + 1) % 3];
vector<int> sw(w.begin(), w.end());
sort(sw.begin(), sw.end());
if (sw[0] >= 0 && sw[1] >= 1) {
vector<pair<int,int>> edges;
int num = 3;
int center;
if (sw[0] == 0)
center = min_element(w.begin(), w.end()) - w.begin();
else
center = num++;
forn(i, 3) {
int before = center;
forn(j, w[i] - 1) {
edges.push_back({before, num});
before = num++;
}
if (w[i] > 0)
edges.push_back({before, i});
}
if (num <= n) {
while (num < n)
edges.push_back({center, num++});
cout << "YES" << endl;
for (auto& [u, v]: edges)
cout << u + 1 << " " << v + 1 << endl;
continue;
}
}
}
cout << "NO" << endl;
}
}
```

Idea: MikeMirzayanov

**Tutorial**

Tutorial is loading...

**Solution**

```
#pragma GCC optimize("O3","unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e5+5;
vector<int> ch[maxn];
int a[maxn];
int b[maxn];
int ans[maxn];
vector<int> vb;
int curb=0;
int cura=0;
void dfs(int x){
curb+=b[x];
cura+=a[x];
vb.push_back(curb);
ans[x]=upper_bound(vb.begin(),vb.end(),cura)-vb.begin();
for(int v:ch[x]){
dfs(v);
}
curb-=b[x];
cura-=a[x];
vb.pop_back();
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;
cin>>t;
while(t--){
int n;cin>>n;
for(int i=0;i<n;++i) ch[i].clear();
for(int i=1;i<n;++i){
int pr,a1,b1;
cin>>pr>>a1>>b1;
--pr;
ch[pr].push_back(i);
a[i]=a1;
b[i]=b1;
}
dfs(0);
for(int i=1;i<n;++i) cout<<ans[i]-1<<' ';
cout<<'\n';
}
return 0;
}
```

Good editorial!

yes its such a good one! :D thanks op for the editorial

Code for D is messed up a bit.

yes

Here is a better intuitive solution.

Solution166883799

I implemented it in an easier way.

My SubmissionCould you please share your idea?

hey man i sort of did the same implementation as yours, but I'm getting MLE, can you please tell me why ? D

Mike Mirzayanov thanks for awesome editorial

Idk, awesome editorial in my understanding contains much more detailed and intuitive solutions with hints, this one is just ok.

Question D is a great problem,but why is the code for D so messy？

Hey, can anyone tell me why did I get a MLE on D with submission 166572453? I precomputed every segment that can be painted in one step, however there can at most be 100*10 such segments for every test case. If every segment is 3 integers (12 bytes) then they use at most 12000 bytes of memory. Lets say that I copy all segments once into

`final`

, then I use at most 2*12000=24000 bytes per test case. This is way below the 256 MB memory limit, so why did my solution get MLE? Thanks.How to solve question D with DP? Can you tell me about it and share your code? If you can help me, I will thank you very much.

Here is my solution: 166798483

What does your dp[i] mean？

dp[i] is the minimum number of steps needed to color prefix(length is i) of text t in red.

use[i]: If an operation was done at a certain location, I recorded the selected subscript.

from[i]: Otherwise I recorded which operation the location was affected by.

thanks

dp is an array and i is the element position in the array

wth is this shit man. Stop it

This comment does not have enough downvotes for destroying almost the entire comment section of the editorial.

Indented solution of problem D from editorial:

Solution"When you color a letter in red again, it stays red."

Missed this line during contest does this make the question similar to Jump game? ->where we can jump from index to any index in range (i,i+a[i])

Yes essentially the same problem. Here's my implementation using this idea.

https://codeforces.com/contest/1714/submission/169954163

Can someone help me out with my wa for E? https://codeforces.com/problemset/submission/1714/166799175

Approach:

Take a look at Ticket 15975 from

CF Stressfor a counter example.The code for

F: Build a Tree and That is itdoes not really clarify things mentioned in tutorial rather it has checks and implementations that makes it seem like the code to be working on a different idea. Can anyone either explain the tutorial or the code ? Thanks.Can you help me with

G.I checked ur code, but can't understand, Can u explain ur idea ? Thanks.So, let's first make a DFS call and make array

Asum[N],where Asum[u] stores the sum of all the A-values along the edges from root to node u.Now notice that B values of all edges are positive. Let's pick any node u. And let's say,

Path[u] = [B1, B2, B3, B4, B5,.....Bx]where the Bi indicates the B-values of all edges from root to node u.Since Bi s are positive the prefix sum on Path[u] will only increase. Let's call

the prefix sum on Path[u]asPrefixPath[u].Since we want to know maximum prefix path that doesnt go beyond all A values sum in the path from root to u, the final answer for node u will be

Answer[u] = Largest index k in PrefixPath[u] such that PrefixPath[k] > Asum[u].I can explain my idea of solution if it can help you.

Let's place $$$1,2$$$ and $$$3$$$ nodes. There is $$$4$$$ possible ways to do it: link to image

The first case: $$$d_{23} = d_{31} + d_{12}$$$. Let's check it, if it is right, then let's build our tree like in image.

The second case: $$$d_{31} = d_{23} + d_{12}$$$. Let's check it, if it is right, then let's build our tree like in image.

The third case: $$$d_{12} = d_{23} + d_{31}$$$. Let's check it, if it is right, then let's build our tree like in image.

The last case: let's see that $$$d_{12} + d_{23} + d_{31} \le n$$$, let's get loop for $$$d_{14} = [1..n]$$$ (sum of $$$n$$$ for all cases is $$$\le 10^5$$$ so we can do it), now we know $$$d_{34} = d_{31} - d_{14}$$$ etc. If all this right, then let's build our tree like in image.

If all cases are wrong, answer is NO.

Woah...Thank you so much. The image actually made your idea very clear. upvote_plus_plus

My Editorial for the problems I solved

AConvert all the times hi mi to minutes. This can be done by multiplying the hour time by 60 and adding that to the minute time. Then calculate the minimum of the differences from the start time to each of the alarms. If the difference is negative, add 24*60 to it. Now that we've got the smallest distance in minutes, divide it by 60 to get the number of hours and take it modulo 60 to get the number of minutes.

166513127

BI just used a map and filled it up with all the values in the array beforehand. Then I kept removing a larger and larger prefix of elements until eventually all the resulting elements were unique.

166516865

CRecursion/Bitmasks Brute force. For each of the digits from 1-9, you have 2 choices: use it, or not. Just get all the 2^9 numbers and find the smallest one that works. This can be done by sorting the digits from smallest to largest and using that as your answer

166525073

DTo solve this problem I kept repeating the following process until all the elements were colored, or no more elements could be colored. Start from the first uncolored element and go down all the way to the first element. Then brute force all the possible input strings that can fit at that position and count the number of new elements that can be colored. If no new elements can be colored, then it's impossible to color everything. Otherwise, use the one that gave you the most new elements, mark those as visited, and move on to the element right after the end of that string.

166548769

EMy approach for this problem was quite messy but it surprisingly worked. There are 3 cases. Case 1: Only numbers that end with 0's and 5's are in the input. 2: Only numbers that end with 1's, 2's, 3's, 4's, 6's, 7's, 8's, and 9's. 3: A mix of both. It can be proven that there is no answer in Case 3. For Case 1: Just add 5's to all the numbers with a units digit of 5 and check if they are all equal. For Case 2, what I did is I first added 1's to all the numbers with unit's digit of 1. I did the same for numbers with unit's digits of 3, 7, and 9. This will then convert all the numbers to having unit's digits of 2, 4, 8, and 6, Then keep adding 20 to all the numbers until they are all less than 20 away from each other. 20 is special because it preserves the units digit and can be added using the operations. Now if there are multiple numbers that have the same unit's digit after adding 20, then there's no solution because it's impossible to ever make them equal. Now we just have (0-1) numbers with unit's digit 2, (0-1) numbers with unit's digit 4, (0-1) numbers with unit's digit 6, and (0-1) numbers with digit 8. Now for all 16 pairs, just check if it's possible to go from the smaller number to the larger number. This means that it is possible for them all to converge to a single value. This solution is really an overcomplicated version of most solutions, and the code is really messy and inefficent.

166575249

It was a very good contest D was interesting but i think you should reorder the problem like this B C A E D G F

B C A E G D F

B C A D E G F

I read the solution "Thus, we will apply the operation to each element of the array until its remainder modulo 10 becomes, for example, 2, and then check that the array does not contain both remainders 2 and 12 modulo 20." I don't know why do we need to check that "the aray does not contain both remainders 2 and 12 modulo 20". Why do we have to do that. Can you explain for me. Thanks

There are only 2 possible cycles when considered modulo 20 (2 -> 4 -> 8 -> 16 -> 2) and (12 -> 14 -> 18 -> 6 -> 12). If members of both cycles are present, you can never make all the numbers the same.

Oh wow, thank you expert

we also can apply operation until we get either 2 or 4 or 6 or 8 as remainder of 10 from each (as all element eventually add-up and give even output) and then we can do same process ( which is checking whether array contain all same element)

if we choose 2 all element will be 12 or 2 // while propagating (3,6,7,9) we can get 12 after some operation while changing element to module 20

for 3's propagation ->3 6 12 14 18 26 32 34 38 46 ->>(%20)->> 3 6

1214 18 61214 18 6for 6's propagation ->6 12 14 18 26 3 34 328 46->>(%20)->> 6

1214 18 61214 18 6for 7's propagation ->7 14 18 26 32 34 38 46 ->>(%20)->> 7 14 18 6

1214 18 6for 9's propagation ->9 18 26 32 34 38 46 52 ->>(%20)->> 9 18 6

1214 18 612for other numbers (1,2,4,8) we can get 2 after some operation while changing element to module 20

for 1's propagation ->1 2 4 8 16 22 24 28 36 42->>(%20)->> 1

24 8 1624 8 162for 2's propagation ->2 4 8 16 22 24 28 36 42->>(%20)->>

24 8 1624 8 162for 4's propagation ->4 8 16 22 24 28 36 42->>(%20)->> 4 8 16

24 8 162for 8's propagation ->8 16 22 24 28 36 42->>(%20)->> 8 16

24 8 162mark we can get 2 for (1,2,4,8) but we can't get 12 and similarly we can get 12 for (3,6,7,9) but we can't get 2;

mark in similar way we can get 4 for (1,2,4,8) not 14 and we can get 14 for(3,6,7,9) not 4

so change all element to either 2 or 4 or 6 or 8 you will end up having either (2,12) or (4,14) or (6,16) or (8,18) respectively and then check whether all same or not answer accordingly

if 5 and 0 as (%10) present we need to check them separately either all same who having 0 as (%10) and if 5 present all should be 5 less from all element who are having 0 as (%10);

Wow. Thanks a lot <3

How to solve C using dp ??

Do you mean problem D?

No, I am trying to solve C using dp. But I am getting wrong answers. This is my code : Its a link to Tutorial point compiler

http://tpcg.io/_28VQ7L

Problem D and E were very nice But I think problem E is much easier than D.

Problem F is also very nice and I think problem F is easier than D and E because I successfully passed F in the contest but failed to pass D and E.

Code for $$$Problem D$$$ should be posted like this :

SolutionI think Vladosiya has forgotten to write

`</spoiler>`

at the end.Thanks for tagging, Fixed

Does anybody have E wa3 ,only one line of code was different between the two submissions Submissions id(wa3) : 166896597 Submissions id(ac) : 166900206 I'd like to know what the problem is. Could you please take a look at it for me，thanks！！！！！

Take a look at Ticket 15979 from

CF Stressfor a counter example.thanks a lot！！！

G is not that hard compared to F, D

agree?

Problem D can be also done with DP approach: 166555787

can you please explain your approach .

It took some time for me but I solved it finally :)

I started by stating out the different series that are being made and what commonalities they have. I deduced that there are two disjoint sets (if you exclude the multiples of 5 of which there are several disjoint sets.) that you get.

I called the set {1,2,4,8,16,22,24,...,96} for evenSet. And the set {3, 6, 12, 14, 18, 26, ..., 98} for oddSet.

The trick is to know that it's only the last two digits in every number which denotes which set it belongs to. For example 111 is equivalent to 11 in the series since they can converge.

What about prime numbers like 17? For them, we can see that 17 + 17 % 10 = 24 is a member of the evenSet. This is true for all such numbers, we can just check if either the number or the next number of the series of the current number is in the set we're interested to check.

What about multiples of 5? For them, we know that {5, 10} is one set, {15,20} another. The set cannot increase and thus we only need to worry about checking if all numbers are equal to the latter in the set. i.e. if a % 10 == 5, then we should look for a + 5. But note that we will check for all other numbers b, if b == a or b+5==a.

Once we have this, the solution should be quite straightforward:

Generate the evenSet and the oddSet.

Check if there are any multiples of 5, if so then we know that all of them should be in the same multiples set.

If there were not any multiples of 5, then check if a or a + a%10 is in the evenSet or the oddSet. (Only take the last two digits of the number!). If there are already any in the oddSet, then since the sets are disjoint, then we know there are no way to make them equal. Similarly, we check in the oddSet and if there are any in the evenSet.

Took a bit of time but well worth it, learned a lot. Can probably be cleaned up a lot:

In problem E, why flag12 and flag2 should not be true for the answer to be YES?

Remainders 2, 4, 6, 8 cycles and in that cycle number increases by 20. So difference between every two elements must divide by 20 (and these elements must have the same remainder modulo 20).

If I understood it right, like if number 12 and 22 both exist in array we wont be able to make these numbers equal, since they will be be converted to 32 and 42 respectively, and this goes on, there wouldn't be a point where they will become equal.

i coded D iteratively, but its giving me MLE, can someone please tell me why ?

iterative D soln

Why I got TLE ? What's wrong with my code[submission:166546367]

Is there a way to solve G using binary lifting

Yes 167804403

Can someone kindly explain the solution for B?

You can try to think the solution in this way:

Either the integers occurs multiple times in array or just one time.

If all are occurring single time, then problem is already solved and no changes required.

Solution: https://codeforces.com/contest/1714/submission/169048774

Could someone explain why this submission for G of mine get TLE ? I know it's inefficient but I still don't get why it doesn't work

First I do a dfs to precompute all prefix sums for a and b. Then for each leaf I find the path from it to the root, reverse the path, and use binary search for each vertices on the path to get the answer.

Hi can anyone help me figure out why my code for D is wrong? Thanks a lot! Basically I have tried to iteratively find the places with maximum coverage. However, it gives WA on a later TC.

CodeTake a look at Ticket 16127 from

CF Stressfor a counter example.Thanks! However, I am also interested to know why the editorial solution won't face the same problem as my solution.

The testcase that I shared is pretty small, with only 3 candidate substrings.

I would suggest you to dry run that testcase, first on your submission to find out why it doesn't work, and then on the editorialist's solution to figure out why their solution does not hit this issue.

Could someone tell me what's wrong with my solution for G here? I tried all the combos of lb/ub but test case 4 is WA each time.

Use 'long long' type in sum variables. because sum of the numbers may not fit in integer.171566697

facepalm. Thanks!For Problem D Solution: else Find(max(pos + 1, b +1), Max, t, str, match);

I do not get why we are passing the max(pos + 1, b + 1) as the first argument , should it not be just pos + 1? Can anyone explain ?

I got wrong answer on test case 2 844th token but i couldnt realize why, I just modulo all the elements except 5 and 0 by 20 and tried to complete all to their max values < 20 by adding e= elements , while ( e + e%10 ) < 20 , {e += e%10} and also if e %10 == 5 round it up and compare the all elements in the array where am i wrong

I fixed thanks.

In** E — Add modulo 10**, we can make an array of size 10 where a[i] is what needs to be added to numbers ending with i so that every number is ending with the same digit. This eliminates the inner while loop and makes the code slightly faster. My solution

Problem C in O(1) complexity (Python) 182612155

i have an easier code to understand about question B for new learners.186176378