Codeforces Round #839 (Div. 3) Editorial

#	User	Rating
1	Radewoosh	3759
2	orzdevinwang	3697
3	jiangly	3662
4	Benq	3644
5	-0.5	3545
6	ecnerwala	3505
7	tourist	3486
8	inaFSTream	3478
9	maroonrk	3454
10	Rebelz	3415

#	User	Contrib.
1	adamant	172
2	awoo	165
2	nor	165
4	SecondThread	164
5	maroonrk	162
5	BledDest	162
7	Um_nik	161
8	-is-this-fft-	149
9	Geothermal	146
10	ko_osaga	142

Tutorial

Solution (BledDest)

t = int(input())
for i in range(t):
    print(eval(input()))

1772B - Matrix Rotation

Idea: BledDest

Tutorial

Solution (BledDest)

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int t;
    cin >> t;
    for(int _ = 0; _ < t; _++)
    {
        vector<int> a(4);
        for(int i = 0; i < 4; i++)
            cin >> a[i];
        int maxpos = max_element(a.begin(), a.end()) - a.begin();
        int minpos = min_element(a.begin(), a.end()) - a.begin();
        if(maxpos + minpos == 3)
            puts("YES");
        else
            puts("NO");
    }
}

1772C - Different Differences

Idea: BledDest

Tutorial

Solution (BledDest)

def construct(f, k):
    return [(i + 2 if i < f - 1 else 1) for i in range(k)]

t = int(input())
for i in range(t):
    k, n = map(int, input().split())
    ans = 1
    for f in range(1, k):
        d = construct(f, k - 1)
        if sum(d) <= n - 1:
            ans = f
    res = [1]
    d = construct(ans, k - 1)
    for x in d:
        res.append(res[-1] + x)
    print(*res)

1772D - Absolute Sorting

Idea: BledDest

Tutorial

Solution (BledDest)

#include <bits/stdc++.h>
 
using namespace std;

int main()
{
    int t;
    cin >> t;
    for(int i = 0; i < t; i++)
    {
        int n;
        cin >> n;
        vector<int> a(n);
        for(int j = 0; j < n; j++)
            cin >> a[j];
        int mn = 0, mx = int(1e9);
        for(int j = 0; j + 1 < n; j++)
        {
            int x = a[j];
            int y = a[j + 1];
            int midL = (x + y) / 2;
            int midR = (x + y + 1) / 2;
            if(x < y)
                mx = min(mx, midL);
            if(x > y)
                mn = max(mn, midR);
        }
        if(mn <= mx) cout << mn << endl;
        else cout << -1 << endl;
    }
}

1772E - Permutation Game

Idea: BledDest

Tutorial

Solution (Neon)

for tc in range(int(input())):
  n = int(input())
  p = list(map(int, input().split()))
  a, b, c = 0, 0, 0
  for i in range(n):
    if p[i] != i + 1 and p[i] != n - i:
      c += 1
    elif p[i] != i + 1:
      a += 1
    elif p[i] != n - i:
      b += 1
  if a + c <= b:
    print("First")
  elif b + c < a:
    print("Second")
  else:
    print("Tie")

1772F - Copy of a Copy of a Copy

Idea: BledDest

Tutorial

Solution (awoo)

#include <bits/stdc++.h>
 
using namespace std;
 
#define forn(i, n) for(int i = 0; i < int(n); i++)

struct op{
    int t, x, y, i;
};

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

int main(){
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<string>> a(k + 1, vector<string>(n));
    forn(z, k + 1) forn(i, n)
        cin >> a[z][i];
    
    vector<int> cnt(k + 1);
    forn(z, k + 1){
        for (int i = 1; i < n - 1; ++i){
            for (int j = 1; j < m - 1; ++j){
                bool ok = true;
                forn(t, 4)
                    ok &= a[z][i][j] != a[z][i + dx[t]][j + dy[t]];
                cnt[z] += ok;
            }
        }
    }
    
    vector<int> ord(k + 1);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&cnt](int x, int y){
        return cnt[x] > cnt[y];
    });
    
    vector<op> ops;
    forn(z, k){
        forn(i, n) forn(j, m) if (a[ord[z]][i][j] != a[ord[z + 1]][i][j]){
            a[ord[z]][i][j] ^= '0' ^ '1';
            ops.push_back({1, i + 1, j + 1, -1});
        }
        ops.push_back({2, -1, -1, ord[z + 1] + 1});
    }
    
    cout << ord[0] + 1 << '\n';
    cout << ops.size() << '\n';
    for (auto it : ops){
        cout << it.t << " ";
        if (it.t == 1)
            cout << it.x << " " << it.y << '\n';
        else
            cout << it.i << '\n';
    }
}

1772G - Gaining Rating

Idea: BledDest

Tutorial

Solution (adedalic)

#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())

typedef long long li;

int n;
li x, y;
vector<li> a;

inline bool read() {
    if(!(cin >> n >> x >> y))
        return false;
    a.resize(n);
    fore (i, 0, n)
        cin >> a[i];
    return true;
}

li ceil(li a, li b) {
    assert(a >= 0 && b >= 0);
    return (a + b - 1) / b;
}

inline void solve() {
    sort(a.begin(), a.end());
    
    vector<li> t(n), b(n);
    fore (i, 0, n) {
        if (i > 0 && b[i - 1] >= a[i]) {
            t[i] = t[i - 1];
            b[i] = b[i - 1] + 1;
        } else {
            t[i] = a[i] - i;
            b[i] = a[i] + 1;
        }
    }
    
    li ans = 0;
    while (x < y) {
        int pos = int(upper_bound(t.begin(), t.end(), x) - t.begin());
        
        li p = pos, m = n - pos;
        if (x + p >= y) {
            cout << ans + (y - x) << endl;
            return;
        }
        if (p <= m) {
            cout << -1 << endl;
            return;
        }
        
        //1. x + k(p - m) + p >= y
        li k = ceil(y - x - p, p - m);
        if (pos < n) {
            //2. x + k(p - m) >= t[pos]
            k = min(k, ceil(t[pos] - x, p - m));
        }
        ans += k * n;
        //x + k(p - m) < y, since 1. and p >= p - m
        x += k * (p - m);
    }
    assert(false);
}

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    int tt = clock();
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(15);
    
    int t; cin >> t;
    while (t--) {
        read();
        solve();
        
#ifdef _DEBUG
        cerr << "TIME = " << clock() - tt << endl;
        tt = clock();
#endif
    }
    return 0;
}

1 4 2 10 2 2 2 15 Ans: 14 1 3 1 100000000 1 2 1000000000 Ans: 299999993 1 3 1 1000000000 1 2 10000000000 Ans: 2999999993 1 4 8 15 2 2 2 20 Ans: 11 1 4 5 13 2 2 2 10 Ans: 10 1 4 5 18 2 3 7 10 Ans: 15 1 5 4 17 4 5 6 15 15 Ans: 45 1 5 8 20 4 5 6 15 100 Ans: 32

#include <bits/stdc++.h> using namespace std; int main() { // Your code goes here; vector<int> g; for(int n=1; n<40; n++) g.push_back(n*(n+1)/2); int t; cin>>t; while(t--){ int k, n; cin>>k>>n; vector<int> ans(k); for(int i=0; i<k; i++){ if(g[i]<=n-(k-i-1)) ans[i]=g[i]; else ans[i]=ans[i-1]+1; } for(int i=0; i<k; i++){ cout<<ans[i]<<" "; } cout<<"\n"; } return 0; }

Comments (50)

Write comment?

adityav664

12 months ago, # |

Can anyone help me with question D Absolute Sorting 185861518 where did i gone wrong?

→ Reply

B_Consistent

12 months ago, # ^ |

← Rev. 2 →

try these may be you will find your bug.

Expected output: 0

c_plus_plus

By the way, a more "natural" way to deduce the relations for D (without doing a lot of casework) is to square both sides of the inequality, because if $$$|x| \leqslant |y| \Rightarrow x^2 \leqslant y^2$$$. This gives $$$(a_i - x)^2 \leqslant (a_{i + 1} - x)^2$$$ for all valid $$$i$$$. This implies that $$$a_i^2 - 2a_ix + x^2 \leqslant a_{i + 1}^2 - 2a_{i + 1}x + x^2 \Rightarrow (a_i^2 - a_{i + 1}^2) - 2(a_i - a_{i + 1})x \leqslant 0 \Rightarrow (a_i - a_{i + 1})(a_i + a_{i + 1} - 2x) \leqslant 0$$$, and then we can continue in the same way as editorial.

bhanu.kode5

Thank you, this is also good

71IQ

It's more natural to just binary search the answer 185850639 (I suppose)

a.rjput

interesting, could you explain your approach a bit in detail?

First, let's denote min(a) as L, max(a) as H and M as (L + H) / 2, it's pointless to look for a solution where x > H or x < L because they will give array of the same (sortness) as H and L. try x = 5, 6 and x = 3, 2 on a = [5, 3, 5] for example, it'll give [0, 2, 0], [1, 3, 1] and [2, 0, 2], [3, 1, 3], respectively. every binary search loop iteration you loop through the array and check for any abs(M — a[i]) < abs(M — a[i — 1]) (which makes the result unsorted obviously), in case we found it we need to prolong the distance between M, a[i] and shorten it between M, a[i — 1] so we updaet H = M — 1 in case a[i] > a[i — 1] or L = M + 1 in case a[i] < a[i — 1]

PepeTheBuilder_74

11 months ago, # ^ |

how do we know when to do h=m-1 or l=m+1

absolute value means distance so if abs(m-a[i]) < abs(m-a[i-1]) that means m was closer to a[i] than a[i — 1] when it should have been further or equal, so we we make it closer to a[i-1]. if a[i] > a[i — 1] we need to make m smaller by doing h=m-1 and vice versa

Aight . Got it , Thanks. I actually tried doing it by taking l=0 and h=1e9 and it worked , idk why or how but it got accepted.

yehya_m

7 weeks ago, # ^ |

so we should check all abs(a[i]-m)
my question is in this case what should i do : a[1]-m<a[2]-m at the same time a[3]-m>a[4]-m

TheINDIANBAKI

Damnn , thanks for thisss!

BCXNSD

Thanks a lot,I got it!

Fanarill

+10

If you want to do it more natural, you can apply difference of squares identity: $$$a^2 - b^2 = (a - b)(a + b)$$$ i.e. $$$(a_i−x)^2\le(a_{i+1}−x)^2 \Leftrightarrow (a_i−x)^2 - (a_{i+1}−x)^2 \le 0 \Leftrightarrow (a_i - a_{i + 1})(a_i + a_{i + 1} - 2x) \le 0$$$

Abhay22

could not understand if(mn <= mx) cout << mn << endl; this part why we are taking mn<=mx

So to check if the obtained range is a "possible" range example, if two numbers are 3 and 6, then >=3 and <=6 is a possible range, but >=6 and <=3 is not a possible range. We are checking if 3 < 6

Ars_

I still don't understand the strategy used in Permutation Game. For me at least, the only possible outcome was a tie, because the other player can mess with the correct ordered ones. For example: 1 2 3 5 4 The first one colors 5 1 2 3 B5 4 The second colors any other to not let the first payer win B1 2 3 B5 4 The first color the last element B1 2 3 B5 B4 The second starts to mess the order of elements B5 2 3 B1 B4 And we have at least two elements out of order for player one, and it will require at least two first movements, but for any of them the other player will undo that movement. So what's the strategy?

BledDest

You can swap more than two blue elements in one turn. You can reorder them as you want, the only condition is that all red elements stay on their positions.

I thought the swap was meant for only two elements, thanks.

micky2100

Why cant 2nd player win in [2,3,1] . Why the answer is Tie.

first player [2B,3,1]

2nd player[2B,3B,1]

1st player skips

2nd player exchanges [3B,2B,1]

vgtcross

If the starting configuration is [2,3,1], 1st player wouldn't start by making the 2 blue. The game would go like this:

1st player [2,3,1B]

2nd player [2B,3,1B]

2nd player skips

2nd player skips . . .

Neither player can arramge the numbers in their goal orders, and making the 3 blue would allow the opponent to win, so bot players just skip turns and it's a tie.

MrAI003

7 months ago, # ^ |

Me too! I think the problem simply didn't describe this properly. It hints at it, but no example seemed to show this clearly either. It would have been nice to show such a multi-swap, because with that the problem seems simple, without it just confusing.

Wait, was that the problem itself? That it was deliberately hard to understand?

penguinarsonist

For Problem G, why can we assume that we require a whole cycle in the reasoning for $$$x+k(p-m) \geq t_p$$$? What if $$$x$$$ exceeds $$$t_p$$$ mid-cycle? Then the number of wins in this particular cycle iteration would be $$$p+1$$$ and not $$$p$$$.

adedalic

+13

The $$$t_p$$$ is the rating you need at the start of the cycle to be able to win the $$$p$$$-th opponent (i.e. first $$$p+1$$$ opponents). If your $$$x < t_p$$$ at the start of the cycle — you can't win against the $$$p$$$-opponent.

can we keep for each i, t[i] = a[i]-i and b[i] = a[i]+1 ?
instead of if and else in for loop?

+12

Nope, suppose array $$$a = [5, 5, 5, 6]$$$. Arrays $$$t = [5, 4, 3, 3]$$$ and $$$b = [6, 6, 6, 7]$$$ don't make any sense.

adobese

please also post c++ codes

man9pum0

i'm new here,anyone could help me in C?,i don't understand what its mean.

new-in-coding

Uh,the meaning of the C question is that two integers marked k and n are given,and you are requested to choose k integers from these integers ranging from 1 to n,then,sort these k integers in ascending order,Thus,an asending array has come into being. Postulate the array is{a1,a2,a3....ak},(a1<a2<a3<...<ak),we can get k-1 integer such that a2-a1,a3-a2,....ak-a(k-1),((k-1) is just a subscript :)),make up a set(mark the set with A) with the k-1 integers.(You should notice that the k-1 integers don't distincted to each other,so the number of the elements in the set(mark the number with g) doesn't necessarily be k-1.)You have different methods to choose k intergers,which corrospond the diffrent values of g.You should print the choice method that could let the g be maxminum. (I suggest you read the text carefully again and learn to guess what the meaning of the question is ,After all,my English is poor....It's my pleasure if my reply can offer you some help:)

thanks ! i got a aot from your reply :D

Yashraj1402

My solution for D using Binary Search:

I got the idea from this line in the problem:

It can be shown that if such an integer x exists, there is at least one such integer between 0 and 10^9.

Initially, left = 0, right = 10^9 and x will be our mid, for any x the array should satisfy |a[i]-x| > |a[i-1]-x| for all i (0 <= i < n), if it doesn't, note that |a[i]-x| > |a[i-1]-x| means that x should be closer to a[i-1] than to a[i], so for any x that does not satisfy |a[i]-x| > |a[i-1]-x| we have 2 cases:

a[i-1] > a[i] then to move x closer to a[i-1] we should increase x i.e. left = x+1
a[i-1] < a[i] then we should decrease x i.e. right = x-1

My Submission, complexity: O(nlog(10^9)) per testcase

rinku11

Nice observations. If we took x closer to a[i-1] in the case of a[i-1] < a[i] then it goes away from a[i] and maximizes the value of |a[i]-x|.

Can you say how to observe these types of questions During the contest, I was trying to observe some kind of pattern and failed . Thanks :)

← Rev. 3 →

Here are some testcases for G

variety-jonas

can you add test case suite to problem G ?

sieunhan283

← Rev. 4 →

The checker got me wrong answer to have the array which is not in ascending order in question C. Is this a bug? 186207153

stakudog

Here, fixed it for you.

https://codeforces.com/contest/1772/submission/186978335

The logic was pretty much spot on. The only problem was in your 2nd while loop. In case the calculated cnt is bigger than a, your code would simply print more numbers than are asked for. So, I just added a check there.

Maha

In problem D "Thus, take the minimum over the pairs of one type. Take the maximum over the pairs of another type. If two resulting values are contradictory, then there is no answer. Otherwise, any value inside the resulting range of x works." Why should that satisfied ?

Sybil

For problem F, Shouldn't it pass in O(k^2*n*m) time complexity in 2 seconds, as it is O(10^7) operation? My solution 186467598. Can anyone help with this?

can someone confirm How many operations can we make in one second in codeforces ?

I have tested cf servers once and it was approximately $$$3*10^9$$$ per second for simple operations like memset which is actually enormously fast (blog with the same question)

nikhilreddydev

Different Differences

can someone explain me what does it mean to be "We need to find an array [d1,d2,…,dk−1] so that the sum of elements in it is not greater than n−1"?

Donvito-911

Let's do some cases and math to understand it.

Let $$$k=n=4$$$. So $$$a$$$ will be $$$[a_1, a_2, a_3, a_4]$$$ and $$$d$$$ as $$$[d_1, d_2, d_3]$$$ or, specifically, $$$[a_2-a_1, a_3 - a_2, a_4-a_3]$$$. Start all elements of $$$d$$$ in $$$1$$$ (which is the minimum possible, since $$$a_{i+1}> a_{i})$$$, so $$$d=[1,1,1]$$$. Note the sum of $$$d$$$ is $$$3$$$ which is not greater than $$$n-1 = 3$$$. If you were to change $$$d$$$ for $$$d=[2,1,1]\Rightarrow a = [1, 3, 4, 5]$$$, note that this violates the statement "Construct an increasing array of k integers from 1 to n" because $$$a_4=5>n$$$ . Therefore, you can increment elements of an initialized $$$d = [1, 1, 1]$$$ such that the sum of it is not greater than $$$n-1$$$.

Let's do other example with $$$k=3, n=4$$$. Now, $$$a = [a_1, a_2, a_3]$$$ and $$$d=[d_1, d_2] = [a_2-a_1, a_3-a_2]$$$ Initialize $$$d = [1,1]$$$ (you know an array $$$d$$$ of size $$$k$$$ full of 1s is always the minimum possible solution because $$$a_{i+1} > a_i$$$ and $$$ k \leq n $$$). The sum of $$$d$$$ is $$$2$$$ which is not greater than $$$n-1=3$$$, Note this time if you increase one of his elements, i.e., $$$d=[2,1]$$$ it actually maintains the condition of the sum ($$$3$$$) not being greater that $$$n-1 = 3$$$. Between these two possibilities the second one has the maximum possible characteristic which is 2 different elements, while the first one only has 1. So using the second $$$d\Rightarrow a = [1, 3, 4] $$$, which is one plausible solution. I hope this was helpful.

PD: Math part for deep understanding

¿where is coming from this "weird" condition of the sum of $$$d$$$ not greater than $$$n -1$$$? Well, you can actually take any strict increasing finite sequence such as $$$a = 1,2,3,4$$$ or $$$a = 7,23, 50, 51$$$ and take the first difference $$$d$$$ and see that the last element of the sequence is always greater that the sum of $$$d$$$. For the first sequence, $$$d=1,1,1$$$ and the sum of it (3) is less than the last element of the sequence (4). For the second one, $$$d=16,27,1$$$. Taking the sum (44), it is still less than its last element of (51). Even though you can see this apparently works, you must prove it for all $$$k\geq 2$$$

Take a finite strict-increasing sequence of $$$k$$$ elements $$$a=[a_1, a_2, a_3, ..., a_k]$$$. The sum of $$$d=[a_2-a_1, ..., a_k - a_{k-1}]$$$ is $$$\sum_{i=2}^k (a_i - a_{i-1}) = (a_2-a_1) + (a_3-a_2) + \dots + (a_k-a_{k-1})$$$.

Then the statement you want to prove is simply $$$\sum_{i=2}^k (a_i - a_{i-1}) < a_k$$$ and this can be proved easily by induction (left to the reader).

Therefore, if the sum of $$$d$$$ is greater or equal to $$$a_k$$$ (or following the tutorial, simply greater than $$$a_k -1$$$) there is no finite strict-increasing sequence $$$a=a_1, ..., a_k$$$. So, when you are checking for all the possible $$$d$$$'s, if the condition is not satisfied then the $$$d$$$ that does not satisfy cannot lead to a finite strict-increasing $$$a = a_1, ..., a_k$$$, which was exactly what happened in the very first example $$$k=n=4$$$ when we tried with $$$d=[2,1,1]$$$.

Thank you for that brief explanation. I really appreciate your effort in this.

mokone

Can anyone help me understand the solution for C? It really looks like there are two magic observations, which are key to unlock the solution

coderama

11 months ago, # |

For Problem C, why these outputs are not accepted?

1 2 4 7 9

1 2 4 7 11

1 2 3

1 2 4

1 2 3 4

1 2 4 6

1 2 4 7 8 9 10 11

Edit: Got accepted, no worries!

Glydon

What's wrong with problem E? For Arrangement of "1 2 4 3" How First Can Win?

Optimal Steps — for initial state of 1(R) 2(R) 4(R) 3(R) moves - First Player — R to B for 3, current state 1(R) 2(R) 4(R) 3(B) Second Player — R to B for 1, current state 1(B) 2(R) 4(R) 3(B) First Player — R to B for 4, current state 1(B) 2(R) 4(B) 3(B) Second Player — swap (1, 4), current state 4(B) 2(R) 1(B) 3(B) and keeps going on.

The Optimal steps can lead to a tie. Because of we can skip our moves. Am I getting the problem in the wrong way? Can anyone guide me?

*NOTE — Many have come to the conclusion that 1st operation of rearranging should be done only if there is an instant win. But Is it really? We can use that operation to let the opponent suffer from winning too right? like I won't win but you won't too.

memoryallocator

Second Player — swap (1, 4), current state 4(B) 2(R) 1(B) 3(B)

First Player -- rearrange: 1 2 3 4, win. Players do not just swap the two elements. Each turn, a new permutation is produced. In other words, they are free to change the order of all the blue elements at the same time.

Oh! Thanks, man, I misread :3

vmpyr

what's wrong with this solution for part C? I'm getting wrong answer in test 2

pratts_02

9 months ago, # |

197560571 whats wrong with this can anyone help

awoo's blog