**Tutorial**

Tutorial is loading...

**Solution (Vovuh, O(n^2))**

```
#include <bits/stdc++.h>
using namespace std;
#define sz(a) int((a).size())
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n, k;
string t;
cin >> n >> k >> t;
int cnt = 1;
int pos = 1;
string ans = t;
while (cnt < k) {
if (pos >= sz(ans)) {
ans += t;
++cnt;
} else {
bool ok = true;
int len = 0;
for (int i = 0; i < sz(t); ++i) {
if (pos + i >= sz(ans)) break;
++len;
if (ans[pos + i] != t[i]) ok = false;
}
if (ok) {
ans += t.substr(len);
++cnt;
}
}
++pos;
}
cout << ans << endl;
return 0;
}
```

**Solution (Vovuh, prefix-function)**

```
#include <bits/stdc++.h>
using namespace std;
#define sz(a) int((a).size())
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n, k;
string t;
cin >> n >> k >> t;
vector<int> p(n);
for (int i = 1; i < sz(t); ++i) {
int j = p[i - 1];
while (j > 0 && t[j] != t[i])
j = p[j - 1];
if (t[i] == t[j])
++j;
p[i] = j;
}
int len = sz(t) - p[n - 1];
for (int i = 0; i < k - 1; ++i)
cout << t.substr(0, len);
cout << t << endl;
return 0;
}
```

**Tutorial**

Tutorial is loading...

**Solution (Vovuh)**

```
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
#endif
int n;
scanf("%d", &n);
vector<int> a(n);
for (int i = 0; i < n; ++i)
scanf("%d", &a[i]);
int ans = 0;
for (int i = 0; i < n; ++i) {
int j = i;
while (j + 1 < n && a[j + 1] <= a[j] * 2)
++j;
ans = max(ans, j - i + 1);
i = j;
}
printf("%d\n", ans);
}
```

**Tutorial**

Tutorial is loading...

**Solution (PikMike)**

```
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int N = 300 * 1000 + 13;
const int INF = int(1e9);
int n;
int prl[N], prr[N], sul[N], sur[N];
int l[N], r[N];
int main() {
scanf("%d", &n);
forn(i, n)
scanf("%d%d", &l[i], &r[i]);
prl[0] = sul[n] = 0;
prr[0] = sur[n] = INF;
forn(i, n){
prl[i + 1] = max(prl[i], l[i]);
prr[i + 1] = min(prr[i], r[i]);
}
for (int i = n - 1; i >= 0; --i){
sul[i] = max(sul[i + 1], l[i]);
sur[i] = min(sur[i + 1], r[i]);
}
int ans = 0;
forn(i, n)
ans = max(ans, min(prr[i], sur[i + 1]) - max(prl[i], sul[i + 1]));
printf("%d\n", ans);
return 0;
}
```

1029D - Concatenated Multiples

**Tutorial**

Tutorial is loading...

**Solution (PikMike)**

```
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
typedef long long li;
using namespace std;
const int N = 200 * 1000 + 13;
const int LOGN = 11;
int n, k;
int a[N];
int len[N];
vector<int> rems[LOGN];
int pw[LOGN];
int main() {
scanf("%d%d", &n, &k);
forn(i, n) scanf("%d", &a[i]);
pw[0] = 1;
forn(i, LOGN - 1)
pw[i + 1] = pw[i] * 10 % k;
forn(i, n){
int x = a[i];
while (x > 0){
++len[i];
x /= 10;
}
rems[len[i]].push_back(a[i] % k);
}
forn(i, LOGN)
sort(rems[i].begin(), rems[i].end());
li ans = 0;
forn(i, n){
for (int j = 1; j < LOGN; ++j){
int rem = (a[i] * li(pw[j])) % k;
int xrem = (k - rem) % k;
auto l = lower_bound(rems[j].begin(), rems[j].end(), xrem);
auto r = upper_bound(rems[j].begin(), rems[j].end(), xrem);
ans += (r - l);
if (len[i] == j && (rem + a[i] % k) % k == 0)
--ans;
}
}
printf("%lld\n", ans);
return 0;
}
```

1029E - Tree with Small Distances

**Tutorial**

Tutorial is loading...

**Solution (Vovuh)**

```
#include <bits/stdc++.h>
using namespace std;
const int N = 200 * 1000 + 11;
int p[N];
int d[N];
vector<int> g[N];
void dfs(int v, int pr = -1, int dst = 0) {
d[v] = dst;
p[v] = pr;
for (auto to : g[v]) {
if (to != pr) {
dfs(to, v, dst + 1);
}
}
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
#endif
int n;
scanf("%d", &n);
for (int i = 0; i < n - 1; ++i) {
int x, y;
scanf("%d %d", &x, &y);
--x, --y;
g[x].push_back(y);
g[y].push_back(x);
}
dfs(0);
set<pair<int, int>> st;
for (int i = 0; i < n; ++i) {
if (d[i] > 2) {
st.insert(make_pair(-d[i], i));
}
}
int ans = 0;
while (!st.empty()) {
int v = st.begin()->second;
v = p[v];
++ans;
auto it = st.find(make_pair(-d[v], v));
if (it != st.end()) {
st.erase(it);
}
for (auto to : g[v]) {
auto it = st.find(make_pair(-d[to], to));
if (it != st.end()) {
st.erase(it);
}
}
}
printf("%d\n", ans);
}
```

**Tutorial**

Tutorial is loading...

**Solution (PikMike)**

```
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
typedef long long li;
using namespace std;
const int N = 1000 * 1000;
int lens[N];
int k;
li solve(li a, li b){
k = 0;
for (li i = 1; i * i <= b; ++i)
if (b % i == 0)
lens[k++] = i;
li ans = 2 * (a + b) + 2;
li x = a + b;
int l = 0;
for (li i = 1; i * i <= x; ++i){
if (x % i == 0){
while (l + 1 < k && lens[l + 1] <= i)
++l;
if (b / lens[l] <= x / i)
ans = min(ans, (i + x / i) * 2);
}
}
return ans;
}
int main() {
li a, b;
scanf("%lld%lld", &a, &b);
printf("%lld\n", min(solve(a, b), solve(b, a)));
return 0;
}
```

May I know how to solve C using segment tree? A lot of folks seem to have done it this way.

You can use segment tree to get range min and range max instead of doing a clever precomp. This adds log factor. I did it with RMQ table because I am lazy.

You can use multiset to get

O(nlogn) with a simpler solution: 42096347yes it is simple and elegant and effective.

Brilliant!

Your solution looks really small and pretty. Can you explain the logic behind it ? I can't seem to get it.

Okay i got what you were trying to do. I guess multiset is actually a kind of Self-Balancing BST. Isn't it ? that's why we get n * log(n) solution.

Multiset works like a set, but allows repeated elements. We just need to find

minRandmaxL, but each time ignoring one of thenintervals. We add all L's and R's to the multisets, and then, for each interval, remove it's values and check for max/min and get best value. It's easy to query because multiset is ordered like set, so min = .begin(), and max = .rbegin()This can be used too in 2D like in this recent problem: 1028C - Прямоугольники

Solution with multisets: 42187139

My segment tree answers the question: What is the intersection segment of segments between index

land indexrinclusive?So, I just iterated over all

ithat 1 < =i< =n, and in each iterate I asked about the intersection segment of segments from 1 toi- 1 inclusive and the intersection segment of segments fromi+ 1 ton(i.e. I removed the segment with indexi), then merged the two resulting intersection segment to obtain the segment which its length should enter in the result maximizing operation.For merging two segments [

a,b] and [c,d], the resulting segment is [lft,rht], wherelft=max(a,c) andrht=min(b,d). Then iflft>rhtlet this segment equal to [ - 1, - 1] as a sign for the future merges that this segment contains nothing.This is my submission.

I was actually looking at your solution before you replied! thanks!

How can we do this question using segment tree if we were allowed to remove (say) m segments at a time.

I really don't know, bro ;)

I used Sparse table for RMQ. Whenever I write sparse table, I feel very proud.

For problem B,

Can anyone tell me why is my solution failing?

http://codeforces.com/contest/1029/submission/42053121

Maybe you misunderstood the problem? for every index i, since the list is sorted, you just have to make sure i+1 is less than 2*a[i]. You only need one such value to satisfy the condition. Just replace your search function with a check 2*a[i]>=a[i+1] or something like that.

Oh yes, Thanks.

I misunderstood the problem. My bad.

Thanks again. :)

The solution given for problem B, For testcase —

11 2 3 4The solution gives

4as output, whereas actual answer is3[2,3,4].Edit — My bad, I dint understand the problem :(

I think we made the same mistake. Can you please check what's wrong with my solution? http://codeforces.com/blog/entry/61439?#comment-454828

yes,we made the same mistake.

you are finding only the element which is (<= 2 * a[i])

we are suppose to check if that element exist and go for next element adding that to the answer

for suppose —

1

1 2 3 4

what we are doing is —

at 1 — ans = 2 [1,2]

at 2 — ans = 3 [2,3,4]

at 3 — ans = 2 [3,4]

at 4 — ans = 1 [4]

our ans is max = 3

but actually we are supposed to do this way -

at 1 — check if 2 exists, if so ans = 2

at 2 — check if any element <= 4 exists if so ans = ans + (index of element — current index + 1)

and move current index to the element (<=4)

and keep going so on

Damn word play!

"There is only one condition that should be satisfied: for each problem but the hardest one (the problem with the maximum difficulty) there

should be a problemwith the difficulty greater than the difficulty of this problem but not greater than twice the difficulty of this problem."Thanks for the help!

Here is one of my solutions for problem E which apparently works in linear time without dynamic programming.

It uses BFS

`O(n+n-1) = O(n)`

to get vertexes sorted by distance from the first vertex.Your code has Python flavor.

What is this supposed to mean?

Nothing. Just saying ;)

I solved the problem A by using Z-function. Also a solution :)

The problem E doesn't need any sorting, just dfs on a tree Code

The idea is to connect the parent of the furthest vertexes to the first vertex, and then mark all parent's children as used ones.

Amazing solution :)

In D, can't you use a hashmap with the remainders mod k, instead of appending to rem_len_i and binary search? It should decrease the complexity to O(n) too.

do you mean D?

yes, you can. here is my (cleaned) solution (which is actually slower than PikMike's) ^_^

I meant D. Edited thanks! Thanks also for the solution leoniduvk!

I submitted D 15 times using an O(10 * n * 2) solution (i < j then i > j), finally passed systests with O(10 * n) by precomputing everything first then handling i != j

Your solution just has the same problem as the majority of all the others, you're doing

res += map[ x ]

without actually checking if x was in the map originally. This generates a lot of empty elements that add up to the complexity. Your submission got acccepted with 1980 ms, submit the same code again and it might not even actually get accepted.

Still TLEs even with the find check

I know you have checked; what i am saying is that your program still uses a lot of memory, like when i wasn't doing the check, so there's gotta be something wrong.

So you could run some tests displaying the size of the map(s) before and after inserting some known amount of elements, and checking whether that's correct or not.

can someone help me i am getting tle for 1029D — Concatenated Multiples https://onlinegdb.com/rks1jEywm

Check this condition ,or else element temp will be created and inserted in map. And changed long long to unsigned long long

link

thanks!, It works for me, i didnt know that a[i]=0 that element is inserted in map

thank you! it worrked

My solution for F is getting WA for test case #37 42102854. Can someone please take a quick look? Edit: nevermind, found a silly mistake.

val can be more than INT_MAX, use long long everywhere

thank you!

On problem E i got WA on testcase 11. The answear differs by 1. Can anyone tell why? Code : http://codeforces.com/contest/1029/submission/42104188 Edit: Fixed.

The following is a simple and compact C++17 solution for problem 1029A - Many Equal Substrings using the STL function

`string::substr()`

.42106199

Thanks

Can someone help me out ! In problem F , #testcase 37: intput: 99999999999973 99999999999971 answer: 199999999999948 we need to find out the minimal perimeter of rectangle formed from a,b. So i calculated the answer for this case is a rectangle has:

3089852923 widthand64728 height. The perimeter of this rectangle is6179835302, which is smaller than the answer. So the answer should be6179835302, not199999999999948. Edited: my fail , i misunderstand the problem!I solved E using dynamic programming in linear time but it is failing test case 8 , Can someone tell me what is wrong with my code ?

The answer to this test should be 2. 1 -> 5, 1 -> 8.

Got it! Thanks for the help! :)

I can't understand why my solution of problem C fails. Can anyone help me?

Check this test case:

Thanks! I've just found the error... It was a such stupid one

Can someone explain DP on tree solution for Problem E?

If you are trying to solve E with DP and are having some WA submissions then I suggest try these following 2 test cases. It is just my humble advice but I did use those 2 cases to find out the AC method.

teststest 1 (answer is 2: you need (1 -> 5) and (1 -> 8) (thanks a guy up there for this test :D)):

test 2 (answer is 2):

First of all, you can see that we have already had a tree with the root is vertex 1. Since the shortest path from vertex 1 to any other vertex at most 2, you may come up with this idea: let

f[u][i] be the minimal number of edges that should be added so that the shortest path from 1 touisiand the subtree with root vertex isusatisfy the given condition. Thus, every vertex has 2 states:f[u][1] andf[u][2]. However, later you will see that every vertex has 3 states :vIf the distance from vertex 1 to

uis 1, it can easily be seen that (v is a child vertex ofu).If the distance from vertex 1 to vertex

uis 2, vertexuis sure to be connected with a vertex that has the shortest path from vertex 1 is 1. Here now there are 2 options: connectuwith its direct ancestor or a child vertex of it. In order to implement, I denote the second subcase asf[u][3].f[u][3] =min(f[u][2] -min(f[v][1],f[v][3]) +f[v][1])In addition, it can be seen that the base cases are those leaves of the tree and

f[u][1] = 1,f[u][2] = 0,f[u][3] = ∞.Look through my AC code ?

Sorry if you consider my English is bad :(

Can someone give better explanation for problem D?

For D, we can maintain an array

tenpfor (10^{i})modk, for 1 ≤i≤ 10 (since maximum number of digits is 10). We can also maintain a`HashMap`

, that maps the modulus to it's count. That is the key is (A[i])modK,and the value is the number of times a number inA, that has the same value after moding byk.Now, for every number

A[i], we have to find numbersbsuch that (b× 10^{d}+A[i])%k= 0.(Wheredis the number of digits inA[i]). This can be written as,b%k× (10^{d})%k)%k+A[i]%k)%k= 0. Let $1$

n=A[i]%k, α = (10^{d})%kandm=b%k. So, it becomes:m× α)%k+n)%k= 0Thus, if $n=0$, then, we can satisfy the condition when

m= 0 or when α = 0. We can search for the number of times a zero is inside the`HashMap`

, for checking them= 0 condition. If α = 0, then we know that every number intAcan be used to satisfy the condition, as the whole number will always be divisible byk.Now, if

n> 0, then (m× α)%k= (k-n), thus,Thus, we'll just have to count the number of occurrences of $m$ inside the

`HashMap`

.My implementation didn't work quite well, so I think there must be some quirk left behind that may make this implementation unreasonable. Any help appreciated!

I tried something similar, In C++ I made array of maps where ith map stores occurences of modulus for only the numbers whose length is i digits. But I'm getting TLE, I tried using unordered_map instead of map and still TLE

code with maps: http://codeforces.com/contest/1029/submission/42203638

code with unordered_map : http://codeforces.com/contest/1029/submission/42203638

EDIT: Turns out I was just using map ineffeciently. The approach works fine. Here is accepted code : http://codeforces.com/contest/1029/submission/42205875

for problem D, does this solution have any specific algorithm

Thanks @Mooncrater

Can someone help me with 1029D.http://codeforces.com/contest/1029/submission/42209023

For the explanation of question F, what do they mean by "a+b should be area of the outer rectangle." Like is there even an outer rectangle?

Problem 1029E Why does this code use set (-d[i], i) instead of (d[i], i)? I used (d[i], i) and failed the test.

in set it is sorted in increasing order. now in the case of this problem u need to know the furthest distance from the root node. and you need to keep it at the beginning of the set. if you take the positive value of the distance it will be stored at the end. but if you take the negative value it will be the smallest and stored at the beginning. :)

Thank You, Wall-E!

In problem D, the only difference between the editorial and my approach is that i've used "unordered_map<int,int> mp[11]" where mp[d][x] stores the frequency of numbers which have d digits and leave a remainder x when divided by k. I get TLE. why?

This is the link to my solution. 42241992

I used an ordinary map, and I too faced the same issue.

Apparently, checking if an element is present in the map before trying to retrieve it, significantly reduces the running time.

In your code, instead of

do a

I think the algorythm for A is incorrect, for 'abab' it gives out the wrong answer — this answer is longer than the right one, can anyone tell me am I right or not? If not, why?

For problem A, isn't the first idea in O(n^3)? Because for this example 'aa..aac', for every k we need to verify the prefix in (n * (n + 1)) / 2 steps. But in the first solution, which implements this idea, the author says that it's in O(n^2) 'Solution (Vovuh, O(n^2))'.

My solution for problem B gets WA on test 4. No idea why. Can anyone help me please? http://codeforces.com/contest/1029/submission/42271885

Thanks in advance!

In problem 1029C — Maximal Intersection .

Can anyone give me proof of this. I want to know why this happens?

We want to find the longest segment that is an intersection of some segments

[l1,r1], [l2,r2], ..., [ln,rn]. To maximize the length, we want to find the leftmost and rightmost points on this segment.The leftmost point guaranteed to be in all the segments is

max(li)for somei. To prove this, we can use contradiction. Assume the leftmost point guaranteed to be in all segments islj, for somelj < liandj != i. But then thei-th segment (with endpoints [li,ri]) isnot guaranteedto be in the wanted intersection, because a case likerj<liis possible (you can visualize the segments as: [lj]----[rj]....[li]--------[ri]). Therefore the assumption is false and the original claim is true.Similar logic for the rightmost point.

Thank you very much.

For problem D,can someone tell me why in PikMike's code,he can use code

`if (len[i] == j && (rem + a[i] % k) % k == 0) --ans;`

to subtract the pair of (i,i)? I think it is possible that there are two numbers which have same length and satisfy the problem but their value don't equal.

ok i think i know the reason ,forget me.

In Problem C, instead of storing result in partial sum like arrays, we can store 4 values which are max of left, min of right and second largest max of l, second largest min of r.

Now, my result is min — max > 0 ? min — max : 0.

So, now I iterate over all the segments and see if removing that improves my answer which maximum length intersection between the remaining.

if the current segments left is equal to max then I replace max my second largest max, else it remains same. Similarly, if current segments right is equal to min then I replace min by second largest min, else it remains same.

Now I keep checking in the loop if my result increases and finally output the maximum result.

This solution also works in O(n) but extra space complexity is reduced to O(1), since it does not require partial sum array.

43075255

Can you please explain why this logic works?

Hi,

For any given set of line segments,

`intersection length = max(left indices) - min(right indices)`

.And for an intersection to occur, this number must be greater than 0.

Now, if I have to remove 1 segment so as to increase the intersection length, I have to keep track of the new max and min after removing that segment.

So, basically I will loop over all segments and calculate new intersection length after removing that segment.

For, instance if I remove a segment whose left index was max, then I have to resort to second max in order to calculate the new intersection length, because that is the new left max now.

Similarly for min right and second min right.

Therefore, I have to keep track of max of left, second max of left and min of right, second min of right.

Since I am removing only 1 segment therefore storing these 4 value will work, whereas if I had to remove k segments then I would have to store more values.

Therefore, this logic will only work for this particular problem statement only.

How to solve this for removing k segments?

Above, logic won't work for removing k segments, and removing k segments is indeed a very good question.

Naive Solution: Brute Force using recursion. Complexity O(n^k).

Better Solution: I will get back to you on this.

how can it be done within O(n) complexity?

By using greedy approach, I think it can be done in O(n*k), but I can't think of any solution in O(n). In fact, I don't think there is any solution in O(n).

how? I mean how can we get all possible subsets in O(n*k). As for removing k segments we have to pick k segments out of n total segments. Any pseudocode will be helpful.

In greedy approch we reduce a problem into a smaller problem, using a safe move. So, if the safe move is right then the algorithm will work. For this case, for an array of n elements, just remove 1 segment which will maximise the intersection. This will reduxe it to a problem of sizs n-1. Now, we will remove a single segment from array of size n-1 to maximise intersection thereby reducing it to an array of size n-2. Then just continue till the array is reduced to size n-k.

Here each reduction will take O(n) since in each reduction we are removing 1 element. Therefore, O(n*k).

Also this is based on the assumption that the safe move is correct. If you’ve the test cases I think it’s worth a try. I think it will work.

But I guess that all possible subsets of size k should be removed once and then the maximum intersection possible should be checked. Similarly for other possible subsets of array with size k should be removed and score should be calculated. Shouldn't this be correct ?

You're not getting the point. Okay, let's try to understand using another problem.

Let's say you've to find k minimum elements in array.

Would you extract every possible subset of size k and see if these are k minimum elements.

Or would you find the minimum element and then the second minimum element, and so on, until you reach k minimum elements.

This is known as greedy approach, where I am reducing the problem size by finding minimum element to n-1, and then finding the minimum element in new reduced array of size n-1.

Now, do you get the point ? Yes, you can find the answer, by finding all possible subsets, but that's not very efficient. It's like saying you can sort an array in O(n^2). Yes you can, but you do have more efficient and complex algorithms for the same.

Now, coming back to the original problem, I understand that greedy approach might be a little difficult to digest.

But try to generalize the problem by removing 1 segment, then 2 segments, 3 segments and so on. You will see a pattern.

And if you still don't, try to read more about greedy algorithms, and simple problems which can be solved by using greedy algorithms, this will seem very easy then.

Problem E , my solution is make the edge with vertex v have maximum number of pv (pv is a vertex have distance to vertex v is 1) , why i am wrong . my code : http://codeforces.com/contest/1029/submission/43141795