Codeforces Round #826 (Div. 3) Editorial

another opportunity to feel dumb

G is good and can be extended to weighted graph

Nice contest and great editorial!

F a little harder

Nice G

If we replace mar = *max_element(...) with *min_element(...) in problem D, we are getting AC in both cases. I did min element there so someone can just give example or any explanation why is it working? Thanks in advance :)

Can someone explain F editorial? Thanks.

Video Editorial for Chinese：

Bilibili

Wanted to reach specialist using div3 as a ladder, instead got negative delta. bleh. Need to grind more.

Problem D. To decide to swap or not we do not need to calculate maximum. Enough to compare the first element with middle value.

and could've been swapped, at least in my opinion is way easier than .

I have another solution for C:

We calculate the sum of the whole sequence, and consider its divisors: For every divisor , we check whether we can divide the sequence into segments of sum , and calculate the length of the longest segment. Doing that for every divisor gives us the time complexity of , which is still good enough to get AC.

Solution: 175584583

What is wrong in my submission for problem D? 175630153

I have a slightly different idea of C 1)I sum up all values of array 2)build a prefix sum of array 3)went through all divisor of Sum 4)now let Div be the current divisor then this div should exists In prefix sum,it multiple should exists, 5)I took the longest i In prefix sum where Div exist and updated the answer!!

My first solution got hacked just becoz I didn't consider 1 as divisor .

There's another solution to B, which I believe to be more intuitive.

If n equals 3 print -1.

If n is even, then the permutation looks like this:

If n is odd, just print the permutation for n + 1, but without the first element, which will always be equal to n + 1, so the permutation is valid.

Solution: 175595206

Does anyone know what the 17th test case of test case 3 for F is? 175777495

I have another solution for G. It got AC but I'm not sure if it is actually correct.

For problem D, we can first check all leaves. Start from a1, we consider every pair (ai,ai+1), it must be like (x,x+1) or (x+1,x), if not, we cannot sort it. Otherwise, when the form is (x+1,x) we are supposed to swap it. Put (x+1)/2 to its father node. After do this we get a new array which length is n/2. And repeat it until the array length is 1. link

why isn't rating's updated yet?

Wouldn't the complexity remain O(mn) for D even after pre-calculating min and max for each vertex since we are swapping elements at each level?

Can anyone explain why 175793640 gives MLE on test 24 (problem G)? It works for other test cases which have higher n and m.

I like E, pretty standard and good

Here's an alternative solution to F w/ time complexity and less code.

As done in the editorial, traverse the segments after sorting by left coordinate, and again after transforming to . Instead of keeping track of 2 maximal segments, though, we keep track of the rightmost endpoint of each color with a max segment tree, and when we are processing segment X, if the query result is to the right of X's left endpoint, we can set to 0, otherwise set to the distance between the left endpoint and the query result.

The above algorithm nearly works, except for when a segment is only adjacent to differently colored segments inside itself. Though, we can then use one additional check: the fact that if segment X contains the midpoint of segment Y, then segments X and Y intersect. This is also insufficient standalone as the converse is false, but kills the edge case. Using a std::multiset, we can perform it in .

Implementation: https://codeforces.com/contest/1741/submission/175824953

Alternative implementation, with an additional factor of in space and time complexity, but uses no data structures outside std::set<int>: https://codeforces.com/contest/1741/submission/175826713

(EDIT: the use of a segtree can be circumvented in my original solution with the bitwise maximum technique in this implementation, which should also improve execution time. Though, that is something one would be far less likely to come up with in contest.)

Can someone help me understand the editorial for problem G? I'm not sure what the editorial is trying to say, and I'm finding it difficult to decipher the code in the given solution.

Another solution. May be intuitive using range trees.

175830429

But it uses extra space.

I would like to share my DFS solution approach for problem E. There can be at most O(2*n) valid subarrays. Each segment is consisted of 2 parts length and numbers. In a segment the length can be either on left or on right. Now, if we consider a[i] as one segment's length indicating cell, then the segment will be either of [i-a[i],i] range or of [i,i+a[i]] range. Let's consider each index as a node. If there are two nodes(segments) having range [i,R1] and [j, R2] where R1+1==j, then we will put an edge between them. Now, lets run a dfs from node 1. If we can reach the node (n+1), then answer is "YES", otherwise "NO". (n+1) is just a dummy node at additional index (n+1). My submission: https://codeforces.com/contest/1741/submission/175659624

Problem C can also be solved by considering all factors of the sum (sum of all elements of array), and trying to split the array for each factor. There can be maximum of log2(sum) factors making the complexity O(NlogN).

Here is my solution: https://codeforces.com/contest/1741/submission/175841633

Can someone explain the solution for C in more detail?

I tried drawing a stack diagram and all.

I even ran their code locally and it did not output the right answer.

Does anyone know subcase 26 in test case 3 for G? 176090403

176213193 which is my way to solve D using sparse table :)

My D solution, iterative and using swap_range stl function

haha bullshit

Can someone explain the Problem F editorial? It is not easy to understand the concept/idea used in that.

Hey, I came up with a different iterative solution. Wanted to drop it in if it is of use to someone.

The intuition is to check for sizes of multiple of 2.

First check consecutive blocks of size 1 and if there is disorder swap the blocks.

then check two different blocks of size 2 and if there is disorder swap the blocks.

Also I have created a validate function which can check if it is possible to form an increasing sequence.

Take a two blocks [5, 7] [8, 9] here min element in block 1 is 5. iterate over first block and check if absolute difference is less than block size. Here abs(7 — 5) will be 2. So we won't be able to arrange the whole tree in increasing order. Trying this with some of examples above and block of even larger size might clear things out.

As this is my first comment. Any suggestions on etiquette and improvements are welcome.

// Aabhas Sao, 19-11-2000
#include <bits/stdc++.h>
using namespace std;

#define ll long long int

bool validate(int segmentSize, int i, vector<int>& v) {
  int half = segmentSize / 2;

  int mn = v[i];

  for (int j = 0; j < half; j++) {
    if (abs(v[j + i] - mn) >= half) {
      // cout << v[j] << " " << mn << " " << half << endl;
      return false;
    }
  }

  mn = v[i + half];

  for (int j = 0; j < half; j++) {
    if (abs(v[i + j + half] - mn) >= half) {
      return false;
    }
  }

  return true;
}

void solve() {
  int n;
  cin >> n;
  vector<int> v(n);

  for (int i = 0; i < n; i++) {
    cin >> v[i];
    if (v[i] > n) {
      cout << -1 << endl;
      return;
    }
  }

  int skips = 2;
  int ans = 0;

  while (skips <= n) {
    for (int i = 0; i < n; i += skips) {
      int mid = i + skips / 2;

      if (!validate(skips, i, v)) {
        // cout << i << " " << skips << endl;
        cout << -1 << endl;
        return;
      }

      if (v[mid] < v[i]) {
        for (int j = 0; j < skips / 2; j++) {
          swap(v[i + j], v[mid + j]);
        }

        ans++;
      }
    }

    // cout << ans << endl;

    skips *= 2;
  }

  cout << ans << endl;
}

int main() {
#ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#endif
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}