Challenge. In problem A can U solve if a , b <= 10 ^ 18 ?

Problem A is O(1). Here is my answer.

May you please find a mistake behind a logic of my approach for problem C : 27416588

In probelm E，the tutorial is too short to understand,could anybody give more details about how it be solved? Thx :)

Explanations in the editorial are shorter than the corresponding problem statements

Another way to solve A:

We know that, Sum of first n odd numbers = n*n and sum of first n even numbers = n*(n+1).

Notice that Vladik always gives odd number of candies and Valera always gives odd number of candies.

If Vladik can gift n times, then n*n should be at least a, so, n = floor(sqrt(a)) . Notice that Vladik can't give right amount, if Valera can give gift at least same number of times, i.e. n times.

Now, to gift n times with even numbers, Valera needs n*(n+1) candies. If Valera has at least n*(n+1) candies, then he can gift n times, and then Vladik is first who can't give right amount of gifts.

int a, b, n;
cin>>a>>b;
n = sqrt(a);
if(b>=n*(n+1))
    cout << "Vladik\n";
else cout << "Valera\n";

Problem B for n, m ≤ 10⁶ can be solved with AVL, there are another way for solve it?

The time of problem B is O(n·m)???

For this problem n, m ≤ 10⁴ so if n = m = 10⁴ then the time would be , that runs on 2 seconds???

you can solve problem A in O(1)

by using this formula Sn = n/2 *(2*a+(n-1)*d)

n number of terms , a = the first element of series "1 for Vladik and 2 for Valera" , d= increment = 2

so the formula for count the number of term for

Vladik = n/2 * (2*1+(n-1)*2) = n(1+n-1) = n^2 = a so na = sqrt(a)

Valera = n/2 * (2*2+(n-1)*2) = n(2+n-1) = n^2+n = b so n^2+n -b =0 and solve it by quadratic equation nb = ( -1 + sqrt(1 + b*4) ) / 2

if (na <= nb) "Vladik"

else "Valera"

For the challenge of D part . I have an idea with string of size atmost 4*n*m.

The idea is first just generate the string from start to final assuming all buttons are correct.Lets call s1.

Now assume (L/R) is reversed and simulate s1 from start to see which position it reaches.from that position generate a string which reaches final from it assuming broken (L/R) . Lets call this S.

Now concatenate s2=s1+S.

Now assume (U/D) is reversed and simulate s2 from start to see which position it reaches.from that position generate a string which reaches final from it assuming broken (U/D) . Lets call this S.

Now concatenate s3=s2+S.

Now assume (L/R) & (U/D) is reversed and simulate s3 from start to see which position it reaches.from that position generate a string which reaches final from it assuming broken (L/R) && (U/D) . Lets call this S.

Now concatenate s4=s3+S.

Now it must be visible that s4 passes through final for any possible breakings.

Can someone find a flaw in this??

problem A can be solved in 0(1). http://mirror.codeforces.com/contest/811/submission/27385965

How to solve the challenge problem for problem C

Is it possible to solve E using SQRT-decomposition? I mean something like this (but I missed that spots can be splitted, so it is wrong anyway).

What is the meaning of this line , can anybody explain?

Assume, that there was such train carriage, that finished at position i. Then iterate it's start from right to left, also maintaining maximal ls, minimal fr and xor of distinct codes cur. If current range [j, i] is ok for forming the train carriage, update dpi with value dpj - 1 + cur.

So how to solve C for n, a[i] ≤ 10^5 ?

A lot of people (including myself) found the explanation for problem C hard to understand, so I thought I'd explain my solution.

for (int i = 0; i < n; ++i)
    en[a[i]] = i;
for (int i = n-1; i >= 0; --i)
    start[a[i]] = i;

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

const short N = 5001;
short a[N], start[N], en[N]; // a is the initial list of numbers, start and en our the first and last occurrences of a certain number.
long dp[N];
bool s[N];

int main() {
  short n;
  cin >> n;
  for (short i = 0; i < n; ++i) {
	cin >> a[i];
	en[a[i]] = i;
  }
  for (short i = n-1; i >= 0; --i)
	start[a[i]] = i;

  dp[0] = 0;
  for (short i = 0; i < n; ++i) {
	if (en[a[i]] != i)
	  dp[i+1] = dp[i];
	else {
	  // s[N] keeps track of which numbers we have encountered or not
	  for (short k = 0; k < N; ++k) s[k] = false;
	  short mi = start[a[i]]; // predicted start of our segment
	  bool valid = true;
	  for (short j = i; valid and j >= mi; --j) {
		if (en[a[j]] > en[a[i]])
		  valid = false;
		s[a[j]] = true;
		mi = min(mi, start[a[j]]);
	  }
	  if (valid) {
		long acc = 0;
		for (short k = 0; k < N; ++k)
		  if (s[k])
			acc ^= k;
		dp[i+1] = max(dp[i], dp[mi] + acc);
	  }
	  else
		dp[i+1] = dp[i];
	}
  }

  cout << dp[n] << endl;
}

When n ≤ 10⁴ I always assume that O(n²) shouldn't work. I'm surprised!

Would someone mind help me look at my code for Problem E? I suppose my code have a time complexity of O(N*(M+Q)*logM) with each merge action as O(N), but I suspect that I messed up part of the implementation thus causing TLE (is the bfs search too expensive for merging?).

http://mirror.codeforces.com/contest/811/submission/27392571

Thanks in advance.

Challenge Div2C
Let dp[i] denote answer when we have created segments till 'i'.

We can construct a segment tree which can answer the following for a range [l, r] -
1. Maximum of last occurrences of the elements in the range [l, r] -> Q(l, r).last
2. Minimum of first occurrences of the elements in the range [l, r] -> Q(l, r).first
3. XOR of the elements whose last occurrences lie in [l, r] -> Q(l, r).ans

For a valid segment, Q(l, r).first = l & Q(l, r).last = r. So we are checking at those indices only where Q(l, r).last = r. And if Q(l, r).first != l, then we need to change 'l' to atleast Q(l, r).first and then again check the condition.

dp[i] = dp[i-1]
If Q(l, r).first = l && Q(l, r).last = r
    dp[i] = max(dp[i], dp[l-1] + Q(l, r).ans)

If Q(l, r).first < l && Q(l, r).last = r
    While l < Q(l, r).first && Q(l, r).last = r
        l = Q(l, r).first 
    If QUERY(l, r).first = l && QUERY(l, r).last = r
        dp[i] = dp[l-1] + Q(l, r).ans

We can save the optimal index for 'l', which will bring the overall complexity to O(nlogn).

Solution

Problem C dfs solution

http://mirror.codeforces.com/contest/811/submission/27572002

Description:

1. Put all LR segments in a tree where each segment's parent is either whole list with root = MAXN or smallest segment that fully contains it.
2. Mark all segments that contain some other elements other than their children with w[i] = 1, their value cannot be xor, only sum of its children
3. Run dfs from root, and based on value of w[u] return either sum of all children segments results or if w[u] == 0 maximum between sum and xor.

My O(n) solution for problem C... Since I'm a beginner in dp (and English So I just implement my own thoughts.. and then I get the code blow.. http://mirror.codeforces.com/contest/811/submission/29330084

Problem D is so bad.