I'll add solution codes as soon as I can. If there are any mistakes, you can PM me.

C was nice

Amazing problems and solutions!!!!

can someone plz explain this to me for question B: Now to calculate the answer on a line we could use a known fact: point with the smallest summary distance is between left and right median.

Is there someone who tried to solve E as a dp[N][2] — minimum distance to reach a node where state 0 means using the second road now and and 1 for the using the first one? I WA o pretest 4,if you can give me your solution. My CODE

Systests for E seem to be weak, many $$$O(n^2)$$$ solutions including mine (107846073) passed with it.

Some video solutions for A-E, and somehow not FST'ing E

Really liked problem c and great problem set!!

weak pretests in A, didn't include overflow case

Thanks for the fast editorials!

C was nice but it would have been better if on exceeding query limit it threw some error other than WA. I thought my code was incorrect but it was exceeding query limit.

WA ON TC2 in prpb A . Can anyone give me whats the mistake.

f = 1

if n == 1:
    print("YES")
    return

if n==2:
    if l[0]==0 and l[1]==0:
        print("NO")
        return
    else:
        print("YES")
        return

extra = l[0]
for i in range(1, n):
    if l[i] > l[i - 1]:
        extra = extra + l[i] - l[i - 1] - 1
        l[i] = l[i-1]+1
    else:
        need = l[i - 1] - l[i] + 1
        if need <= extra:
            l[i] = l[i] + need
            extra = extra - need
        else:
            f = 0
            break
if f:
    print("YES")
else:
    print("NO")

Thanks

UPDATE: ITS SORTED OUT NOW

Why is my solution not correct for A ? I can't think of a case where it may fail;-;...pls someone check 107870406 i wasted 2 hrs on this piece of sheet;-;

okwedook Too many fake solution for E, suggest rejudge all submissions .

Just amazing contest,thanks to the autor! Waiting soon for ur next round.

I tried to solve D using ordered set, but I got WA on test case 7. I cant figure out why MY CODE

Can anyone please tell me why I got an fst on problem C ? WA_CODE

Such a good problem set, make me realize that I need to work hard. And that interactive questions, nice.

I will be thankful if someone recommends good and easy interactive questions, for beginners. Thanks in advance.

C was a great question, I'm still confused though on my find_left function.

at first, my mid calculations were the standard (lo + hi) / 2, but this causes infinity loop:

ll mid = lo + (hi - lo) / 2;

then I changed it to (lo + hi + 1) / 2, then got AC:

ll mid = lo + (hi - lo + 1) / 2;

full code:

ll find_left(ll secondMaxIdx)
{
	ll lo = 1, hi = secondMaxIdx - 1;
	while (lo < hi)
	{
		ll mid = lo + (hi - lo) / 2;
		if (ask(mid, secondMaxIdx) == secondMaxIdx)
		{
			lo = mid;
		}
		else
		{
			hi = mid - 1;
		}
	}
	return lo;
}

Can anyone with a better understanding of binary search explain why this works?

I solved E in another way(107874274). I'm not sure whether it is correct or not.

The naive solution is to use Dijkstra's algorithm and two loops to relax. Consider every vertex $$$u$$$. If it is used as middle vertex by some vertex $$$a$$$ and it is going to be used by vertex $$$b$$$.

According to Dijkstra's algorithm, ans[a] <= ans[b] must hold. If dis[a][u] <= dis[b][u], no vertex will be relaxed by $$$b$$$. So for every vertex, I record the minimum dis[a][u]. If it is equal or smaller than dis[b][u] then continue. Otherwise I just run the naive two loops.

Since every vertex will be used as middle vertex at most $$$maxw$$$ times, each relaxtion will call one pq.push. The time complexity may be $$$\mathcal{O}((N+M)logM + maxw\cdot (N+M)logM)$$$(I'm not sure about this)

E

"For a middle vertex we only...". what is a "middle vertex"?

"is the weight of the last edge...". What is the "last edge", last of what?

"Now for each starting edge..." What is "starting edge" here?

Is there anyone else who thanks Errichto whenever they see a binary search problem?

Can someone help me figure out where I am going wrong?

#include "bits/stdc++.h"
#define ll long long int
using namespace std;

const int mod = 1e9 + 7, mxN = 2e5 + 10;

int solve(int l, int r, int ind = -1)
{
  if(l >= r)
    return l;
  

  if(ind == -1)
  {
    cout << "? " << l << " " << r << endl;
    cin >> ind;
  }

  int mid = l + (r-l)/2;

  
  if(ind > mid)
  {
    int temp;
    cout << "? " << mid << " " << r << endl;
    cin >> temp;
    if(ind == temp)
      return solve(mid , r, temp);
    else
      return solve(l, mid - 1);
  }
  else
  {
    if(mid == l)
      return r;
    int temp;
    cout << "? " << l << " " << mid << endl;
    cin >> temp;
    if(ind == temp)
      return solve(l, mid, temp);
    else
      return solve(mid + 1, r);
  }
}

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(NULL);

  int tt;
  // cin >> tt;
  tt = 1;
  for (int pp = 0; pp < tt; pp++)
  {
    int n;
    cin >> n;

    int ans = solve(1, n);

    cout << "! " << ans << endl;
  }

  return 0;
}

Thanks in advance!

okwedook test cases for E are weak. Many $$$O(N^2)$$$ have been passed. So please consider rejudging all submissions.

I thought it has time complexity O(log n) but it's O(n).

int fun(int l, int r) {
	if(l == r)	return r;
	int m = (l + r) / 2;
	int x = fun(l, m);
	int y = fun(m + 1, r);
	cout << "? " << x << " " << y << endl;
	int q;	cin >> q;
	if(q == x)  return y;
	if(q == y)  return x;
	if(q > m)   return y;
	else        return x;
}

How to solve D by two pointers?

I am getting runtime error on testcase 6 for the E problem , here is the link of my submission , can some one please check it!!, What I have done is kept n*51 states and edge of weight 0 between (u,0) & (v,w) , edge of weight (a+w)^2 between (u,a) & (v,w) , for the edge u,v with weight w given in question, I applied dijkstras on transformed graph..

In problem D, I know that we can use binary search as described in the editorial. But I noticed that if $$$x$$$ is too small, we cannot find a sufficient subarray. Consider the first example in the statement of list $$$[1, 2, 3, 2, 1], k = 3$$$. Assume that we want to check if it is obtainable the median of $$$1$$$ or not. But we cannot choose from $$$[1, 2, 3, 2, 1]$$$ a subarray of length at least $$$3$$$ that has the median is $$$1$$$.

How can we overcome this?

After reading the solution to the problem D — wow that is very smart. The binary search never ceases to amaze me. Thank you for the beautiful problem (and the solution)

Can anyone please explain the formula of problem F?

About C: Actually we can do this with only 18 queries.

Here's my code: 107897123

I can't explain code clearly, it is copyed from my code in C1 and edited a little. (Code in C1: 107895318)

Maybe someone could explain how this worked or hack it?

Amazing solutions！！！Orz

It seems to me that D, E are too technical and without ideas (it was immediately clear to me from the statesment what to do), but they are still funny

https://mirror.codeforces.com/contest/1486/submission/107832284 can anyone point out why is this solution wrong, I ran query overall range and then ran two queries for f, mid and mid+1,l if I find the same index in either of the answers then I search in that range or If I don't find any matching index I go the half opposite to that previous queries

Thanks for the "Hint" part! Super helpful! :D

When will I become a CM? :-(

It's been a pain using the CF system tester to debug an interactive problem like C (even the asserts return nothing, just a Runtime Error). Here's a brief snippet in case anyone else would like to test this locally. It basically generates n different numbers (permutation from 1 to n) and shuffles them.

Instead of doing cout/cin operations, as you would do in the actual solution, here you could just call the ask() function and it would give you the second maximum for that range (each call takes O(n) time — so you would obviously time out if your overall solution is not some form of binary search / log(n))

vector<int> input;

void build(int n) {
	input.assign(n, 0);
	iota(input.begin(), input.end(), 1);
	unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
  	shuffle(input.begin(), input.end(), std::default_random_engine(seed));
}

int ask(int l, int r) {
	int mx1=-1, mx2=-1;
	for(int i=l; i<=r; i++) {
		if(mx1==-1 || input[i] > input[mx1]) {
			mx2 = mx1;
			mx1 = i;
		}
		else if(mx2 == -1 || input[i] > input[mx2])
			mx2 = i;
	}
	return mx2;
}

int main() {
	int n = 100000;
	build(n);
	int a = ask(0, n - 1);
        ...
}

Can someone please help me where my code is failing. TIA.

107911405

In the editorial solution of problem c2,in binary search l+1<r is used in while loop instead of l<r used usually.can someone explain the logic behind?

I'm getting this error in C1 and C2 problem " wrong answer Integer parameter [name=query_l] equals to 100000, violates the range [1, 99999]" Can anybody help to fix that this is my code

Quality of editorials have increased a lot from past few months.

If you use SPFA in E,you will be TLE.

Good problems, moderate difficulty, but weak tests of E.

Can someone please explain problem C2 didn't get the logic from the editorial. Thanks in advance :)

I can't get why my solution is giving me a wrong ans at test 7 of question D. My approach is a little different from the editorial. https://mirror.codeforces.com/contest/1486/submission/107932779

In C2 solution and find_left binary search why do we return hi instead of lo?

What does "wrong answer Integer parameter [name=query_r] equals to 49218, violates the range [50000, 100000]" mean? What am I missing? This is in testcase 5 problem C1

Can someone check my code for problem C. Still cant figure out the corner case I'm missing.

I can't explain me why my solution is wrong for problem A, can anyone help me? https://mirror.codeforces.com/contest/1486/submission/107785526

Can someone tell why it is giving wrong output 107936839

Why is this getting WA on testcase 3 ? can anyone help me. https://mirror.codeforces.com/contest/1486/submission/107964080

Can someone elaborate how you all are creating graph before applying Dijkstra? (problem E)

In the editorial's code for C2, why is the binary search done over 0...n-1 and not 1...n, I've already noticed that the answer is being returned after incrementing it by one.

In problem D, I dont understand why the answer is monotonic. Suppose the array is [6, 1, 1, 1, 1, 7, 8], k = 3, the answer exist for x = 7(ie subarray [1, 7, 8]), hence according to the editorial the answer is atleast 7, this means answer for x = 6 should also exist, but there is no subarray of length >= 3 for which 6 is the median.
Did I miss something? Any help is appreciated.

Except for the LCA part, I have had a nearly-linear implementation for task F.

My submission 108017714

I am observing about a 2x difference between the runtimes of two solutions, by just changing the way I am indexing the array. I understand that this is because of different localities of reference between the solutions.

Yet, I am not able to figure out why one of these has a higher locality of reference. If someone can help me figure out the same, it will be greatly appreciated.

These are the two submissions: 108047029 108047388

I was trying to solve C2 but I am not quite understanding where the queries are running out. According to me, I am asking only one query before dividing the segment any further, so I think my queries shouldn't be more than 20.

My code: 108106042