1690A - Print a Pedestal (Codeforces logo?)

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++)
#define sz(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define eb emplace_back
void solve() {
int n;
cin >> n;
for (int a = 3; a < n; a++) {
int c = (n - a) / 2;
int b = n - a - c;
if (c > 1 && b+1 < a) {
c--;
b++;
}
if (a > b && b > c) {
cout << b << ' ' << a << ' ' << c << endl;
return;
}
}
}
int main() {
int t;
cin >> t;
forn(tt, t) {
solve();
}
}
```

Idea: MikeMirzayanov

**Tutorial**

Tutorial is loading...

**Solution**

```
#include<bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int inf = 1e9 + 7;
bool equals(vector<int>&a, vector<int>&b, int n){
int dif = inf;
forn(i, n){
if(b[i] != 0) dif = min(dif, a[i] - b[i]);
}
if(dif < 0) return false;
if(dif == inf) return true;
forn(i, n){
if(a[i] - b[i] > dif) return false;
if(b[i] != 0 && a[i] - b[i] < dif) return false;
}
return true;
}
void solve(){
int n;
cin >> n;
vector<int>a(n), b(n);
forn(i, n) cin >> a[i];
forn(i, n) cin >> b[i];
cout << (equals(a, b, n) ? "YES\n" : "NO\n");
}
int main(){
int t;
cin >> t;
while(t--){
solve();
}
}
```

1690C - Restoring the Duration of Tasks

Idea: MikeMirzayanov

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i, n) for (int i = 0; i < int(n); i++)
void solve() {
int n;
cin >> n;
int s[n];
int f[n];
for (int i = 0; i < n; ++i) {
cin >> s[i];
}
for (int i = 0; i < n; ++i) {
cin >> f[i];
}
int curTime = 0;
int d[n];
for (int i = 0; i < n; ++i) {
curTime = max(curTime, s[i]);
d[i] = f[i] - curTime;
curTime = f[i];
}
for (auto now: d) {
cout << now << " ";
}
cout << '\n';
}
int main() {
int tests;
cin >> tests;
forn(tt, tests) {
solve();
}
}
```

1690D - Black and White Stripe

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, k;
cin >> n >> k;
string s;
cin >> s;
vector<int> w(n + 1);
for (int i = 1; i <= n; i++)
w[i] = w[i - 1] + int(s[i - 1] == 'W');
int result = INT_MAX;
for (int i = k; i <= n; i++)
result = min(result, w[i] - w[i - k]);
cout << result << endl;
}
}
```

**Tutorial**

Tutorial is loading...

**Solution**

```
#include<bits/stdc++.h>
#define len(s) (int)s.size()
using namespace std;
using ll = long long;
void solve(){
int n, k;
cin >> n >> k;
vector<ll>a(n);
ll sum = 0;
for(int i = 0; i < n; i++) {
cin >> a[i];
sum += a[i] / k;
a[i] = a[i] % k;
}
sort(a.begin(), a.end(), [] (int x, int y){
return x > y;
});
for(int i = 0, j = n - 1; i < j; i++, j--){
while(a[i] + a[j] < k && i < j) j--;
if(i == j) break;
sum++;
}
cout << sum << endl;
}
int main(){
int t;
cin >> t;
while(t--){
solve();
}
return 0;
}
```

Idea: MikeMirzayanov

**Tutorial**

Tutorial is loading...

**Solution**

```
def gcd(a, b):
if b == 0:
return a;
return gcd(b, a % b)
def shift(s):
for i in range(1, len(s) + 1):
if s == s[i:] + s[:i]:
return i
def solve():
n = int(input())
s = input()
p = [int(x)-1 for x in input().split()]
used = [False] * n
ans = 1
i = 0
while i < n:
ss = ''
while not used[i]:
ss += s[i]
used[i] = True
i = p[i];
i += 1
if len(ss) == 0:
continue
ln = shift(ss)
ans = ans * ln // gcd(ans, ln)
print(ans)
t = int(input())
for _ in range(t):
solve()
```

Idea: Aris

**Tutorial**

Tutorial is loading...

**Solution**

```
#include<bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
vector<int> a(n);
set<int> tmp;
for (int i = 0; i < n; i++) {
cin >> a[i];
if (tmp.empty() || a[i] < a[*tmp.rbegin()]) {
tmp.insert(i);
}
}
for (int i = 0; i < m; i++) {
int j, d;
cin >> j >> d;
j--;
a[j] -= d;
auto it = tmp.upper_bound(j);
if (it != tmp.begin()) {
it = prev(it);
if (*it == j || a[*it] > a[j]) {
tmp.insert(j);
}
} else {
tmp.insert(j);
}
while (1) {
it = tmp.upper_bound(j);
if (it != tmp.end() && a[*it] >= a[j]) {
tmp.erase(it);
} else {
break;
}
}
cout << (int) tmp.size() << " ";
}
cout << '\n';
}
}
```

Auto comment: topic has been updated by Aris (previous revision, new revision, compare).No-one else understands your python code except you!!!

speedforces

Wasn't it round 797?

For users (like me) trying to learn implementation, I suggest looking at jiangly's submissions of these problems.

For G, can someone please give a proof to "remove in total no more than 2*n elements from the set".

The set contains the starts of trains. Initially there could be at most n trains. When the speed of a train is reduced, you can at most create one new train. This adds m additional trains. It is possible that every element could be removed from the set, so in total, n+m elements can be removed from the set.

is it possible that some subset of trains are getting removed and added? I mean after we remove a starting train from the set, it can be added as well afterward. doesn't this yield to an n^2 solution?

Not sure what you mean. Each operation can only create one new train. The operation can only create a new train with start index at the index of the operation. Indices before the operation will not be affected and indices after will either match the new value at the index of operation (and thus will be within the same train) or will not be affected.

If you are/were getting a

WA/REverdict on problems from this contest, you can get thesmallestpossiblecounter examplefor your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints.If you are not able to find a counter example even after changing the parameters, reply to this thread (only till the next 7 days), with links to your submission and ticket(s).

Hi, for problem $$$A$$$, since $$$n \leq 10^5$$$ we can use brute force. But I want to know $$$\mathcal{O}(1)$$$ solution. I saw codes from top people from standings. But I don't understand the idea

We want to have the

minimalvalue of h1.We know that h1 + h2 + h3 = n, so we should maximize the values of h2 and h3 in order to minimize the value of h1.

The "best case" scenario would be that n mod 3 = 0, so that we can set: h3 = n/3 — 1, h2 = n/3 = h3 + 1, h1 = n/3 + 1 = h/2 + 1. (because n / 3 is a whole number)

This is the best case because h1 > h2 > h3 is required by the problem statement.

If n mod 3 = 1, then (n — 1) mod 3 = 0. We can perform the above solution for n — 1 and get: h1 = (n-1) / 3 + 1, h2 = (n-1) / 3, h3 = (n-1) / 3 — 1. We have one extra block though, and the only way to place it without disrupting the inequality (h1 > h2 > h3) is to place it at the top of h1, making h1 = (n-1) / 3 + 1.

If n mod 3 = 2, we can follow the above process once again, this time placing our second extra block at the top of h2 making h2 = (n-2) / 3 + 1. Since h1 = (n-2) /3 + 2, the inequality is not disrupted and h1 stays minimal.

Thank you very much for detailed explanation. I will try to understand the concept. :)

Great explanation thanks!!

Without any ifs greedy solution:

`n`

— input;`h1, h2, h3`

— pedestals;We now that that

`h2 >= h3 + 1`

and`h1 >= h2 + 1 >= h3 + 2`

=>`n = h1 + h2 + h3 >= 3 * h3 + 3`

=> max`h3`

equals`h3=(n-3)/3`

(rounding down).Than just set

`s = n - h3`

Using the same logic

`s = h1 + h2 >= 2 * h2 + 1`

=> max`h2`

equals`h2 = (s - 1) / 2`

(rounding down again). And`h1 = s - h2`

Thanks :)

WOW! Thanks a lot

in contest submission: 159731522

Check out my submission. Let me know if you have any questions!

Auto comment: topic has been updated by Aris (previous revision, new revision, compare).Can anyone share their approach for problem F?

Why are we always considering the minimum shift? As we are taking LCM, it might be better to take a larger number if the LCM with ans is getting minimized.

deleted.

consider this string

abcabcabcthere is a period of length 3 so shifts are[3,6,9]notice that all shifts are multiple of period 3 so that minimal number is the best as itcontains the minimal number of prime factors.

Understood! Thanks!

but what if shifts like 2,5 are possible?

upd: got it sorry.if a,b is possible then a-b is also possible.

proof for E ?

This is not like a formal proof but should make the idea clear as it is basic mathematics.

Let C1, C2, C3,....Cm be the length of some m number of disjoint cycles present in the string, (m <= n). Pick any Ci. the length of cycle Ci means that if you do Ci number of operations as mentioned in the question, you will get the starting permutation of those indices and hence the string will be the same.

Say

X = LCM(C1, C2, C3, ..... Cm). Since we want the entire string to be as starting string after operations, all individual cycles must come back to the original configuration in starting string indices. And since lowest common multiple of cycle lengths is the least number when all lengths complete full rotation, we can guarantee that X is definitely the answer.But is X the best possible answer always ?

It might not be. Let me give an example. Consider the string "aaa". You can get "aaa" as same definitely after 3 rotations. but are 3 rotations necessary, No. You can also get the same after 1 rotation only because the possibility of characters might match.So instead of taking the cycle length 3 as possible rotations, you take 1. So formally answer becomes:

X = LCM(Y1, Y2, Y3,......Ym),where Yi (<= Ci) is the minimum number of shifts we need to perform for i-th cycle to make the string equivalent to a complete rotation.Here is my C++ implementation after reading from editorial.

Thanks bro, but i asked for E :D however i proofed my way

Could you please explain what proof you got?vukvuk

In

problem F, the rotation of string will cost o(n^2) time. it's ok for this problem. But I want to know is there any o(n) approach to do this work?You can use KMP algorithm for $$$O(n)$$$ search, or hashing will also give you average of $$$O(n)$$$ time.

Damn, I didn't even see that the constraints were so less up until I saw your comment. My approach was using a rolling string hash, which works in O(n) time and O(n) space.

Submision:https://codeforces.com/contest/1690/submission/159836832

Getting a TLE on 147, Can I get that testcase ?

My solution appears to be O(m log n)

try to use ap.lower_bound(v) instead of lower_bound(all(ap),v)

Wow! Worked, didn't know that both of them have this much difference in running time.

Thanks!

look at the section "Complexity" in https://en.cppreference.com/w/cpp/algorithm/lower_bound

That's because we can only visit a element in set in O(n), So using lower_bound(all(ap),v) will cost you O(nlogn) time.

In problem F, I have another approach, using the Chinese Remainder Theorem.

My approach:

I hope this could be useful for someone.

My code: https://codeforces.com/contest/1690/submission/160003457

Is there any DP idea for problem D, as at every

`W`

we have a choice to color it or not. If we color it then it contributes 1 to our cost and increases the max length of consecutive B so far by 1, if we choose not to color it, then from here max length becomes 0. Initially I thought of this approach but couldn't code it out. Am i thinking right/wrong in this direction ?The problem can be solved with two pointers. If you want to solve it by DP, you surely can, but that code will also boil down to a two-pointer code essentially. Since we want to maintain

kconsecutive Blacks, we do not have a choice for W to add it or not. If it happens to come inside our string of length G then we have to consider it otherwise not.Can you give me a solution/submission link of problem D using two pointers? I have upsolved D using prefix sum.

I think you are thinking about doing it using a sliding window. I recommend checking my last submission to see if it is the same idea. If not, you can try out your idea and see where you get stuck (why you can’t code it).

can someone tell me where this is failing? 160027351

Take the string $$$abab$$$ for example, it only need $$$2$$$ operations to repeat itself, but your code will calculate it as $$$4$$$

Is time complexity $$$m \log^2n$$$ per test case not allowed in G? I'm getting TLE for this submission 160038706. I've used segment tree with lazy propagation, and I've also used binary search. I'm making a range query for every iteration in the binary search, that's why its $$$m \log^2n$$$.

Don't quite know why you are getting TLE, but I used binary search + segment tree with lazy propagation and it passed. Here's my submission : https://codeforces.com/contest/1690/submission/159839709

That's a nice method, initially, I had written the exact same segment tree implementation as you (the cp-algorithms one lol), but I wasn't able to figure out the distinct numbers part, so I had to modify the type of queries I was making. Complexity wise our codes seem to be the same, maybe yours has a lower constant factor? If someone can pinpoint the reason for me getting TLE that would be really helpful.

deleted

In

`F`

why does having thesame character at multiple positionsdoesn't come into consideration?I.E. Couldn't there be a string such that the resultant string is the same as the original but indices are not the same since the same characters are occupying each other's place?

`Example:`

Original string and indices:

A B A B

0 1 2 3 // indices

After some permutations:

A B A B

2 1 0 3 // original indices of chars

That's exactly why we need to find $$$k_j$$$.

Problem E: Why does this TLE? For each test-case, I think only O(k) work is being done (both i and j only go once from k-1 to k/2, and 1 to O(k), respectively).

Edit: Turns out that map (O(log k)) gives TLE, but array (O(1)) does not (?).

Can G be done by segment trees?

yup,you can get the prefix minimum while updating using a segtree. also you can use fenwick

i tried segment tree approach for G but i got TLE — Test 134

https://codeforces.com/contest/1690/submission/160192601 is it possible to optimize this solution ? my idea is to merge elements from right array that are < min(left) to left array

example:left: 10 5 right: 8 7 4 2 merge result: 10 5 4 21690B - Array Decrements CODE: 161337471

PLZ CAN ANYONE TELL WHAT I AM DOING WRONG WITH THE CODE

This website might help you.

Thank you

anyone please explain the approach of problem E

Can anyone help me figure out why 162651629 is getting run time error? I tried using cfstress.com but for some reason, it doesn't work. All my manual testing doesn't produce a run time error either.

CF Stressreturns that verdict because your code doesn't compile on my machine, due to this line:It complains that that the second argument is

`long long unsigned`

. Explicitly typecasting this makes it compile, resulting in a counter example: Ticket 15364Thank you very much!

Another div 3 is coming soon

getting wrong answer for 2nd tc in array decrement problem.but,its showing correct in other compiler

Aris Vladosiya Gol_D DmitriyOwlet

For G, there are two unnecessary things in the following code segment-

1) the else segment is not required as the first train will always remain in the set and so upper_bound of any index can never point to tmp.begin(), so the code will never enter the else section!

2) in the nested if condition, there is no need to check if *it==j, as if this is true then we already know that jth index is there in the set so we don't need to confirm this condition in order to add jth index in the set.

more optimized solution for problem E

anyone please help me , why am i getting runtime error in problem E

165488550

For my submission link I can't find a small test case or not even a larger one. Need help.

1690C The time limit exceeds on the fourth test for whatever reason.