Educational Codeforces Round 157 Editorial

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Tutorial

Solution (awoo)

for _ in range(int(input())):
    x, y, k = map(int, input().split())
    if y < x:
      print(x)
    else:
      print(y + max(0, y - x - k))

1895B - Points and Minimum Distance

Idea: fcspartakm

Tutorial

Solution (fcspartakm)

#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> a;

inline void read() {
  cin >> n;
  a.clear();
  for (int i = 0; i < 2 * n; i++) {
      int x;
      cin >> x;
      a.pb(x);
  }
}
inline void solve() {
    sort(all(a));
    vector<pair<int, int> > pts;
    for (int i = 0; i < n; i++) {
        pts.pb(mp(a[i], a[i + n]));
    }
    int ans = 0;
    for (int i = 1; i < n; i++) {
        ans += abs(pts[i].ft - pts[i - 1].ft) + abs(pts[i].sc - pts[i - 1].sc);
    }
    cout << ans << endl;
    for (int i = 0; i < n; i++) {
        cout << pts[i].ft << ' ' << pts[i].sc << endl;
    }
}
 
int main () {
    int t;
    cin >> t;
    while (t--){
        read();
        solve();
    }
}

1895C - Torn Lucky Ticket

Idea: BledDest

Tutorial

Solution (awoo)

n = int(input())
s = input().split()
ans = 0
cnt = [[0 for k in range(46)] for k in range(6)]
for y in s:
    cnt[len(y)][sum([int(c) for c in y])] += 1
for L in s:
    for lenr in range(len(L) % 2, len(L) + 1, 2):
        l = len(L) + lenr
        suml = sum([int(c) for c in L[:l // 2]])
        sumr = sum([int(c) for c in L[l // 2:]])
        if suml - sumr >= 0:
            ans += cnt[lenr][suml - sumr]
for R in s:
    for lenl in range(len(R) % 2, len(R), 2):
        l = len(R) + lenl
        suml = sum([int(c) for c in R[-l // 2:]])
        sumr = sum([int(c) for c in R[:-l // 2]])
        if suml - sumr >= 0:
            ans += cnt[lenl][suml - sumr]
print(ans)

1895D - XOR Construction

Idea: AcidWrongGod

Tutorial

Solution (Neon)

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

const int LOG = 20;

int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 1; i < n; ++i) {
    cin >> a[i];
    a[i] ^= a[i - 1];
  }
  vector<array<int, 2>> t({{-1, -1}});
  auto add = [&](int x) {
    int v = 0;
    for (int i = LOG - 1; i >= 0; --i) {
      int j = (x >> i) & 1;
      if (t[v][j] == -1) {
        t[v][j] = t.size();
        t.push_back({-1, -1});
      }
      v = t[v][j];
    }
  };  
  for (int x : a) add(x);
  auto get = [&](int x) {
    int v = 0;
    for (int i = LOG - 1; i >= 0; --i) {
      int j = (x >> i) & 1;
      if (t[v][j ^ 1] != -1) j ^= 1;
      x ^= j << i;
      v = t[v][j];
    }
    return x;
  };
  for (int x = 0; x < n; ++x) {
    if (get(x) == n - 1) {
      for (int i : a) cout << (x ^ i) << ' ';
      break;
    }
  }
}

1895E - Infinite Card Game

Idea: BledDest

Tutorial

Solution (awoo)

//

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

struct card{
  int x, y;
  card() {}
  card(int x, int y) : x(x), y(y) {}
};

void dfs(int v, const vector<int> &g, vector<int> &res, vector<char> &used){
  if (used[v]) return;
  used[v] = true;
  dfs(g[v], g, res, used);
  res[v] = -res[g[v]];
}

void solve(){
  vector<vector<card>> a(2);
  vector<vector<int>> prpos(2);
  forn(z, 2){
    int n;
    scanf("%d", &n);
    a[z].resize(n);
    forn(i, n) scanf("%d", &a[z][i].x);
    forn(i, n) scanf("%d", &a[z][i].y);
    sort(a[z].begin(), a[z].end(), [](const card &a, const card &b){
      return a.x > b.x;
    });
    prpos[z].resize(n + 1, -1);
    forn(i, n){
      if (prpos[z][i] == -1 || a[z][i].y > a[z][prpos[z][i]].y)
        prpos[z][i + 1] = i;
      else
        prpos[z][i + 1] = prpos[z][i];
    }
  }
  int n = a[0].size();
  vector<int> g(n + a[1].size());
  forn(z, 2) forn(i, a[z].size()){
    int cnt = lower_bound(a[z ^ 1].begin(), a[z ^ 1].end(), card(a[z][i].y, -1), [](const card &a, const card &b){
      return a.x > b.x;
    }) - a[z ^ 1].begin();
    g[i + z * n] = prpos[z ^ 1][cnt] == -1 ? -1 : prpos[z ^ 1][cnt] + (z ^ 1) * n;
  }
  vector<int> res(g.size());
  vector<char> used(g.size());
  forn(i, g.size()) if (g[i] == -1) res[i] = 1, used[i] = true;
  int w = 0, l = 0;
  forn(i, n){
    if (!used[i]) dfs(i, g, res, used);
    w += res[i] == 1;
    l += res[i] == -1;
  }
  printf("%d %d %d\n", w, n - l - w, l);
}

int main(){
  int t;
  scanf("%d", &t);
  while (t--) solve();
}

1895F - Fancy Arrays

Idea: Neon

Tutorial

Solution (Neon)

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

#define forn(i, n) for (int i = 0; i < int(n); ++i)

const int MOD = 1e9 + 7;
const int N = 40;

using mat = array<array<int, N>, N>;

int add(int x, int y) {
  x += y;
  if (x >= MOD) x -= MOD;
  if (x < 0) x += MOD;
  return x;
}

int mul(int x, int y) {
  return x * 1LL * y % MOD;
}

mat mul(mat x, mat y) {
  mat res;
  forn(i, N) forn(j, N) res[i][j] = 0;
  forn(i, N) forn(j, N) forn(k, N)
    res[i][j] = add(res[i][j], mul(x[i][k], y[k][j]));
  return res;
}

template<class T>
T binpow(T x, int y, T e) {
  T res = e;
  while (y) {
    if (y & 1) res = mul(res, x);
    x = mul(x, x);
    y >>= 1;
  }
  return res;
}

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n, x, k;
    cin >> n >> x >> k;
    mat a, e;
    forn(i, N) forn(j, N) a[i][j] = (i < x && abs(i - j) <= k);
    forn(i, N) forn(j, N) e[i][j] = (i == j);
    mat b = binpow(a, n - 1, e);
    int ans = mul(x + k, binpow(2 * k + 1, n - 1, 1));
    forn(i, x) forn(j, x) ans = add(ans, -b[i][j]);
    cout << ans << '\n';
  }
}

1895G - Two Characters, Two Colors

Idea: BledDest

Tutorial

Solution (BledDest)

#include<bits/stdc++.h>

using namespace std;

mt19937 rnd(42);

struct node
{
  long long x;
  int y;
  int cnt;
  int sum;
  int push;
  node* l;
  node* r;
  node() {};
  node(long long x, int y, int cnt, int sum, int push, node* l, node* r) : x(x), y(y), cnt(cnt), sum(sum), push(push), l(l), r(r) {};
};

typedef node* treap;
typedef pair<treap, treap> ptt;

int getSum(treap t)
{
  return (t ? t->sum : 0);
}

int getCnt(treap t)
{
  return (t ? t->cnt : 0);
}

treap fix(treap t)
{
  if(!t) return t;
  int p = t->push;
  if(p != 0)
  {
    if(t->l) t->l->push += p;
    if(t->r) t->r->push += p;
    t->x += p;
    t->push = 0;
  }
  t->sum = getSum(t->l) + t->cnt + getSum(t->r);
  return t;
}

treap merge(treap a, treap b)
{
  a = fix(a);
  b = fix(b);
  if(!a) return b;
  if(!b) return a;
  if(a->y > b->y)
  {
    a->r = merge(a->r, b);
    return fix(a);
  }
  else
  {
    b->l = merge(a, b->l);
    return fix(b);
  }
}

bool hasKey(treap t, long long x)
{
  t = fix(t);
  if(!t) return false;
  if(t->x == x) return true;
  if(t->x < x) return hasKey(t->r, x);
  return hasKey(t->l, x);
}

ptt splitKey(treap t, long long x)
{
  t = fix(t);
  if(!t) return make_pair(t, t);
  if(t->x < x)
  {
    ptt p = splitKey(t->r, x);
    t->r = p.first;
    return make_pair(fix(t), p.second);
  }
  else
  {
    ptt p = splitKey(t->l, x);
    t->l = p.second;
    return make_pair(p.first, fix(t));
  }
}

long long kthMax(treap t, int k)
{
  t = fix(t);
  if(!t) return -1;
  int sumR = getSum(t->r);
  if(sumR >= k) return kthMax(t->r, k);
  if(sumR + t->cnt >= k) return t->x;
  return kthMax(t->l, k - sumR - t->cnt);
}

int getCntByKey(treap t, long long x)
{
  t = fix(t);
  if(!t) return 0;
  if(t->x == x) return t->cnt;
  if(t->x > x) return getCntByKey(t->l, x);
  return getCntByKey(t->r, x);
}

treap increaseKey(treap t, long long x, int cnt)
{
  t = fix(t);
  if(!t) return t;
  if(t->x == x)
  {
    t->cnt += cnt;
  }
  else if(t->x > x)
  {
    t->l = increaseKey(t->l, x, cnt);
  }
  else
  {
    t->r = increaseKey(t->r, x, cnt);
  }
  return fix(t);
}

treap insert(treap t, long long x, int y, int cnt)
{
  t = fix(t);
  if(!t || t->y < y)
  {
    ptt p = splitKey(t, x);
    treap res = new node(x, y, cnt, cnt, 0, p.first, p.second);
    return fix(res);
  }
  if(t->x > x)
    t->l = insert(t->l, x, y, cnt);
  else
    t->r = insert(t->r, x, y, cnt);
  return fix(t);
}

treap insertMain(treap t, long long x, int cnt)
{
  if(hasKey(t, x))
    return increaseKey(t, x, cnt);
  else
    return insert(t, x, rnd(), cnt);
}

treap eraseKey(treap t, long long x)
{
  t = fix(t);
  if(!t) return NULL;
  if(t->x > x)
  {
    t->l = eraseKey(t->l, x);
    return fix(t);
  }
  if(t->x < x)
  {
    t->r = eraseKey(t->r, x);
    return fix(t);
  }
  treap tnew = merge(t->l, t->r);
  delete t;
  return tnew;
}

ptt splitSum(treap t, int k)
{
  t = fix(t);
  if(!t) return make_pair(t, t);
  if(k == 0) return make_pair(t, treap(NULL));
  long long x = kthMax(t, k);
  int cnt = getCntByKey(t, x);
  t = eraseKey(t, x);
  ptt p = splitKey(t, x);
  k -= getSum(p.second);
  if(k > 0) p.second = merge(new node(x, rnd(), k, k, 0, NULL, NULL), p.second);
  if(k < cnt) p.first = merge(p.first, new node(x, rnd(), cnt - k, cnt - k, 0, NULL, NULL));
  return p;
}

long long minKey(treap t)
{
  t = fix(t);
  if(!t) return 1e18;
  if(t->l) return minKey(t->l);
  return t->x;
}

treap decreaseUpToKLargest(treap t, int k, int& res)
{
  if(!k) return t;
  t = fix(t);
  k = min(k, getSum(t));
  res = k;
  ptt p = splitSum(t, k);
  if(p.second)
  {
    p.second->push--;
    for(int i = 0; i < 2; i++)
    {
        long long x = minKey(p.second);
        int cntMin = getCntByKey(p.second, x);
        p.second = eraseKey(p.second, x);
        if(x != 0 && cntMin != 0)
          p.first = insertMain(p.first, x, cntMin);
    }
  }
  return merge(p.first, p.second);
}

void destroy(treap t)
{
  if(!t) return;
  if(t->l) destroy(t->l);
  if(t->r) destroy(t->r);
  delete t;
}

void solve()
{
  int n;
  cin >> n;
  string s;
  cin >> s;
  vector<long long> r(n), b(n);
  for(int i = 0; i < n; i++) cin >> r[i];
  for(int i = 0; i < n; i++) cin >> b[i];
  long long sum = 0;
  for(int i = 0; i < n; i++) sum += r[i] + b[i];
  long long flow = 0;
  treap t = NULL;
  for(int i = 0; i < n; i++)
  {
    long long d = min(r[i], b[i]);
    flow += d;
    r[i] -= d;
    b[i] -= d;
    if(s[i] == '0')
    {
      int add = 0;
      if(r[i] > 1e9) r[i] = 1e9;
      t = decreaseUpToKLargest(t, r[i], add);
      flow += add;
    }
    else
    {
      if(r[i] != 0) t = insertMain(t, r[i], 1);
    }
  }
  cout << sum - flow << endl;
}

int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t;
  cin >> t;
  for(int i = 0; i < t; i++) solve();
}

BITS = 32 def calc(s): """ Logic: (Applicable for all 'n' and 'a' for which atleast one valid solution exists) NOTE: 'b' can be obtained by XORing 's' by some appropriate value. If at a bit position in 's', the count of '0' is more then, the corresponding bit position in all elements of 's' will be XORed with '0'. (Hence, effectively it is unchanged) If at a bit position in 's', the count of '1' is more then, the corresponding bit position in all elements of 's' will be XORed with '1'. (Hence, effectively it is "flipped") Otherwise, if both '0' and '1' count are equal at a bit position of 's', the bit position may be arbbitrarily chosen to be either flipped or kept unchanged for all elements. """ global BITS res = 0 for i in range(BITS): count = [0, 0] for j in range(len(s)): count[(s[j]>>i) & 1] += 1 res += (count[0]<count[1])<<i return res

void increment(std::span<bool> bits) { bool carry = true; for (bool &b : bits) { bool next_carry = carry & b; b ^= carry; carry = next_carry; if (!carry) break; // this early exit is what makes it amortized O(n) } }

void increment(std::span<std::bitset<20>> bits, std::bitset<20> carry) { for (auto &b : bits) { auto next_carry = carry & b; b ^= carry; carry = next_carry; if (carry.none()) break; } }

void increment(std::span<std::pair<std::bitset<20>, std::bitset<20>> bits, std::bitset<20> carry) { for (auto &[lo, hi] : bits) { assert((lo & hi).none()); // invariant: we have only 0, 1, or 2 as the digit, not 3 hi |= carry & lo; lo ^= carry; if (we_dont_bother_carrying_further()) break; carry = hi; hi.reset(); } }

Comments (45)

Show archived | Write comment?

gvne

13 months ago, # |

+16

→ Reply

goextreme

+19

problems C and D were excellent

mcclane57

For problem D it is possible to find b1 bit by bit. Calculate the amount of ones in i-th bit of all b-th if b1_i = 1 and compare with the amount of 1th for numbers from 0 to n-1. If they are different b1_i=0

AcidWrongGod

13 months ago, # ^ |

Yes, this is author's solution)

Sure, but it does not require binary trie:)

+14

I meant that author’s (my) solution also does not contain trie. Maybe trie is more educational trick, that's why it is using in editorial.

harsh-apcr

How do you prove the correctness, that if $$$b_1$$$ is chosen optimally then all the numbers are distinct ? Is it because of the property that $$$a_i \leq 2n$$$

thanhdno

← Rev. 2 →

rumike

5 months ago, # ^ |

The question say that there exists a at least a valid array b. So suppose that array exists, and from it we construct c, if two element of c are the same at i and j, so whatever the b1, at some moment, bi == bj, and that can't give a permutation.

Chiefash

This was really nice idea. Thanks

k_ano

I thought of the following logic but I feel it is more efficient as I do not require to calculate 1's from 0 to (n-1):

The following function 'calc' return the first element b[0] of the sequence.

It takes input 's', which is equivalent to 'c' in the editorial:

(defined as: s[0] = 0 ; s[i] = s[i-1] ^ a[i-1] ;)

The code is written in Python.

You are just using the fact that amount of 1s on every position is not greater than amount of 0s — agree)

Yes indeed I am. (So is this precomputation considered cheating?)

nope, but are you using it? it is trivial to prove. For any number with bits from the power = 0 (x1, x2, ... x_i, 1,...) the number (x1, x2, ... x_i, 0,...) is smaller so if there is 1 then there is also 0.

juneharold

how does your solution ensure that the largest b[i] is less than n?

Since there is a solution and the constructed one satisfies all an-s.

Consider the possible solutions for some given 'n'. (In Binary Notation)

It follows from one constraint that, if 'v' is a solution, then all solutions satisfying that constraint may be obtained by simply complementing(~) all elements of 'v' at some 0 or more bit-positions.

('c' defined as : c[0] = 0 ; c[i] = c[i-1] ^ a[i-1] ; is also a solution to this constraint)

Now, as per the other constraint 'v' must also be a permutation of {0, ..., n-1}

Let us try to find a path to reach this solution that satisfies both, starting from 'c'.

Properties of the goal that we are trying to reach:

As our goal is a permutation of {0, ..., n-1}, properties of permutations of {0, ..., n-1} apply to our goal

The i'th bit position will have as many 1's as present in the i'th bit from 0 to n-1.

The i'th bit position will always have equal or more 0's than 1's (shown by mcclane57)

Now, it turns out that satisfaction of these two properties suffice to reach our goal, assuming that it exists. My program simply tries to satisfy the above 2 properties.

_apurv_

The above solution will only work for even length right? For odd length, you'll have to simply find b1 I guess.

I think that I've never used in the "proofs" that lengthh is even but indeed for the odd case I calculated b1 as 0^1^...^(n-1)^a2^a4^...^an

Roronoa__Zoro

231233772. Is this what u talking about.. If Yes can u explain what does the portion bit1[i] != bit2[i] mean ?

conclr

12 months ago, # ^ |

But if when b1_i = 1 and when b1_i = 0, the amout of ones are both equal to the amout of ones for numbers from 0 to n-1, you cannot exclude one of them. So how to prove that b1_i = 0 and b1_i = 1 are both right?

all ones and zeros have the same multiset of tails 0-(i-1) bit so there is no difference which numbers are equal to 1 and which ones to 0)

brave-kid

6 months ago, # ^ |

yeah

Akil_Newaz_Chy

Plz someone explain bit by bit solution for problem D. And also explain properly! (Not Editorial solution)

Sure. The same as in editorial we want to understand the value of b1, then b2 = b1^a1, b3 = b2^a2 and so on. Since XOR is a bitwise operation we can solve this problem bit by bit. For i-th bit of b1 there are two possible cases b1_i = 0 or b1_i = 1. By calculating explicitly b2_i, b3_i ... bn_i we can count the amount of 1 among these values. If the bit is set correctly for b1 then the amount will be equal to amount of numbers from 0 to n-1 with nonzero i-th bit (if amount of 1th equal to amount of 0th then any value of this bit will lead to the solution). The complexity is O(32n) while using bitset<32> to go from int to bits and reverse.

Why no of 1 and no of 0s matter?

since it is a bitwise operation other bits does not affect the i-th bit of the final numbers and the fact that solution exists. 1 — If the number of 1s differs then it is not a solution. 2 — If the number of 1s = number of 0s then nothing change from swapping between 1 and 0 since the multisets of prefixes "0-(I-1)" bit for 0s and 1s are the same (corollary from the equality of number of 1s and 0s).

It is sad that I was almost 1 hour solving problem D with operator OR (always have a problem where I failed to "read" the problem) and had no time for problem E but C-E are nice problems for educational.

taicristiano

Plz explain me problem C why suml — sumr>0 made Lucky Ticket,thanks.

vstiff

Check my implementation, it feels a bit simpler to me with similar idea.

Let's say we are checking 52349. Split it at every digit and try as left and right part of ticket:

         52349 | anything with length 5, sum 23 (5,23)
         5234 | 9 + (3,14)
         523 | 49 + (1, 5)
 (1,9) + 52 | 349
(3,13) + 5 | 2349

magnus.hegdahl

+79

Problem D is solvable in linear time (ignoring IO) in the word RAM model.

I'll show an alternate $$$O(n \log n)$$$ solution, and then show how to optimize it.

Notice that among the numbers from $$$0$$$ to $$$n-1$$$, $$$\left \lfloor\frac{n}{2}\right\rfloor$$$ numbers are odd, and the rest are even.

If $$$n$$$ is odd, these two counts are different, so we can use it to determine whether the first number of $$$b$$$ should be odd or even. Make it even if the count is already correct, and odd if we need to correct the count.

If $$$n$$$ is even, toggling the $$$0$$$-th bit in each number is a bijection from the list onto itself, so it doesn't matter whether we set the bit in the first number of $$$b$$$.

A similar argument can be made for each of the other bit positions, but the formula for the expected count is a bit more complicated. The expected number of $$$1$$$-bits in the $$$j$$$-th bit position is $$$n - \left \lfloor\frac{n}{2^{j+1}}\right\rfloor \cdot 2^j - \min\left(n \bmod 2^{j+1}, 2^j\right)$$$

So now we have a way to construct the answer given the number of $$$1$$$-bits seen in each bit position. Counting this in $$$O(n \log n)$$$ time is easy, but doing it in $$$O(n)$$$ is also possible, using bitset. I learned this trick from simonlindholm's "troll" subtask in the problem ligatures.

The idea is that when incrementing a counter, we very rarely need to carry. It takes $$$2^j$$$ increments before we increment the $$$j$$$-th bit, so the total number of carries when incrementing a number $$$n$$$ times starting from $$$0$$$ is $$$\frac{n}{1} + \frac{n}{2} + \frac{n}{4} + \dots \in O(n)$$$

In code it looks something like this:

So for a single counter, we can implement the counting in linear time while operating on just $$$O(1)$$$ bits at a time. But in the word RAM model, we can operate on $$$\Omega(\log n)$$$ bits at a time. We'll use this to run several counters in parallel. For each bit-position in the counter, instead of storing a single bit, we store a bitset, and then the increment function takes a mask of which of the counters to increment:

But modifying the code like this broke the amortization argument. Different counters may need to carry at different times. The trick to fix this is to somehow synchronize the carrying by allowing different representations of the same number inside the counters. Instead of letting each digit in the binary representation be $$$0$$$ or $$$1$$$, we let it be $$$0$$$, $$$1$$$, or $$$2$$$. It's still base $$$2$$$, it's just that digits are allowed to be a little too big. It can also be seen as storing the carry bit as a lazy update. To do this, we store a pair of bitmasks for each bit position:

Now if we pick an appropriate condition for not bothering to carry further, we can both maintain the digit-invariant and achieve $$$O(n)$$$ complexity. In case the $$$0$$$-th digit becomes $$$2$$$ after $$$2$$$ steps, we need to carry in the $$$3$$$-rd step. After that the $$$0$$$-th digit is either $$$0$$$ or $$$1$$$. From then on, we need to carry from the $$$0$$$-th digit every $$$2$$$-nd step. For simplicity, we can ignore the $$$2$$$ carry-less increments at the start, and just always carry from the $$$0$$$-th digit every other step. Similar arguments can show that we need to carry from the $$$i$$$-th digit every $$$2^i$$$-th step. How many steps we need to carry turns out to be the number of trailing zeros in the number of steps we have completed so far.

Here's an implementation: 231387717

Note that this is not the most efficient parallel bit-counter. You might get better performance by doing this trick in base $$$4$$$ instead, and with some extra care, you can let the digits go further past their usual allowed range.

Cosmoss

← Rev. 5 →

In problem D, how bit by bit logic is working in below case cause even after bit flips the count of set bits at 2nd bit are unequal in b.

n=6, a= 1 6 1 4 7, b= 0 1 7 6 2 5(calculated prefix xor of a if b starts with 0)

output: is not in range of 0-5 but it exceeded for above test case

It seems to me that this example does not satisfy any solution!

Then how how can we ensure that after flipping i-th bit, where count of set bits is unequal becomes equal to that of set bits of at i-th bit in (0-n-1). Could you please clarify in detail?

if it is not true than there is no solution because the I-s bit should be either 1 or 0.

SNX03

Trie is a more standard way to solve D, I like it better!

Can someone explain the trie solution ? how the trie is constructed, and how are they finding max b_1^c_i

Okay so since b2 = a1 ^ b1, b3 = a1 ^ a2 ^ b1, ..., bn = a1 ^ ... ^ an-1 ^ b1.

From this fact you can observe that finding b1 will automatically result in finding all the other values.

So start by forming a Trie which contains pointer to a bit array of size [2] (for each bit 0\1. Now since all you need to check is that MAX(b1 ^ pref[i]) < N insert all the pref values inside the trie bit by bit. After inserting these values enumerate for each b1 in the range [0, N).

Now how do you find MAX(b1^pref[i]) in LOG(N) well since XOR is only one for two non-similar bits. Start iterating for each bit and checking if the trie has a bit opposite to the set bit in the b1 you are checking, if this is true then choose that path and descend the trie else move forward.

implementation

A basic Trie that does the job.

Basic

struct T {
    T* bits[2];
    T() {
        bits[0]=nullptr; bits[1] = nullptr;
    }
};
void insert(T* R, int N) {
    T* ND = R;
    for(int i=21; i>=0; i--) {
        if(!ND->bits[N >> i & 1]) ND->bits[N >> i & 1] = new T();
 
        ND = ND->bits[N >> i & 1];
    }
}
 
int F(T* R, int N) {
    T* ND = R;
    int mx = 0;
    for(int i=21; i>=0; i--) {
        if(ND->bits[1 ^ N >> i & 1]) {
            mx |= 1 << i;
            ND = ND->bits[1 ^ N >> i & 1];
        } else 
            ND = ND->bits[N >> i & 1];
    }
    return mx;
}

ivan100sic

12 months ago, # |

Problem D can be solved by just counting the number of 0 and 1 bits at each position and comparing with the expected count for the sequence $$$[0, \ldots, n-1]$$$. If at some position the count is wrong, we must flip that bit. 231908591

_Secret_Ninja

Could you explain what you mean by expected count for the sequence? Maybe with an example

wow great solution!!But why does it work?Any proof?

Amdadul

Problem D :

!!Read first solution from the comment box.

There is a proof or simple observations that if n==(2^k) then anything is possible as b1. But when n!=(2^k) then the number of open and close form of a particular bit are not same , in this case we can take decision . But some bits open and close forms number are same ,in this case first observation works.

starcat

9 months ago, # |

D:this is a good question, i love it

6 months ago, # |

I solved $$$D$$$ with binary search

awoo's blog