okwedook's blog

By okwedook, 10 days ago, translation, In English

1486A - Shifting Stacks

Hint1
Hint2
Solution

Solution using C++: 107892022
Solution using Python: 107892053

1486B - Eastern Exhibition

Hint1
Hint2
Solution

Solution using C++: 107892065
Solution using Python: 107892085

1486C1 - Guessing the Greatest (easy version)

Hint1
Hint2
Solution

Solution using C++: 107892097
Solution using Python: 107892140

1486C2 - Guessing the Greatest (hard version)

Kudos to Aleks5d for proposing a solution to this subproblem.

Hint1
Hint2
Hint3
Solution

Solution using C++: 107892122
Solution using Python: 107892144

1486D - Max Median

Hint1
Hint2
Hint3
Solution

Solution using C++: 107892153
Solution using Python: 107892163

1486E - Paired Payment

Hint1
Hint2
Hint3
Solution

Solution using C++: 107892178

1486F - Pairs of Paths

Hint1
Hint2
Hint3
Solution

Solution using C++: 107892186

 
 
 
 
  • Vote: I like it
  • +451
  • Vote: I do not like it

»
7 days ago, # |
  Vote: I like it +215 Vote: I do not like it

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

»
7 days ago, # |
  Vote: I like it +15 Vote: I do not like it

C was nice

»
7 days ago, # |
  Vote: I like it +21 Vote: I do not like it

Amazing problems and solutions!!!!

»
7 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    7 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    think about 4 points : (0,0) (0,1) (0,2) and (0,100). If you are fixing the median between (0,2) and (0,100) the first 3 point will have to move to the right(0,x+1) and that's bad for the solution.

  • »
    »
    7 days ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    Just imagine: there are n points in line. You are on the leftmost point and walk to the rightmost point. When you begin to walk, the sum of all distance will get smaller until you arrive at the median —— or 2 medians (if n is even, there are 2 medians and you will get a same summary between them)

  • »
    »
    7 days ago, # ^ |
    Rev. 6   Vote: I like it +7 Vote: I do not like it

    It is because you want to minimize $$$C = |x-x_1| + .. + |x-x_n|$$$ where $$$x_1\leq x_2\leq ... \leq x_n$$$. You have $$$|x -x_i|+|x-x_{n-i+1}|\geq x_{n-i+1}-x_i$$$; and "=" happens when $$$x_i\leq x\leq x_{n-i+1}$$$. To make it valid for all $$$i$$$, in the case $$$n$$$ is odd, $$$x$$$ must take the value of $$$x_{n/2}$$$, otherwise, $$$x$$$ can take any value from $$$x_{n/2}$$$ to $$$x_{n/2+1}$$$ (the two medians).

  • »
    »
    4 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Another way to think of it: for any two given points, choosing any point along the line connecting them contributes the same summary distance, i.e. the distance between them. So taking all the points as a whole, you can ignore the left-most and right-most point. You now have a smaller set, and you can keep doing this, until you either have 2 points left (if initial set had an even number of points) or 1 point left. So if you have 2 points left, any point between them will contribute the minimum (the distance between them), as going outside of those 2 points will contribute more than the distance between them. And obviously if you only have 1 point left, that point will contribute 0, and anything else would contribute more.

»
7 days ago, # |
  Vote: I like it +6 Vote: I do not like it

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

  • »
    »
    7 days ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    I solved it using a similar approach. Here is my code. Hope it helps : )

    • »
      »
      »
      7 days ago, # ^ |
      Rev. 2   Vote: I like it +8 Vote: I do not like it

      it's not, but thank you anyway :). I found my mistake. I didn't think about the case when we should use the same edge twice in a row like in this example :

      Spoiler
»
7 days ago, # |
  Vote: I like it +102 Vote: I do not like it

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

»
7 days ago, # |
  Vote: I like it +23 Vote: I do not like it

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

»
7 days ago, # |
  Vote: I like it +3 Vote: I do not like it

Really liked problem c and great problem set!!

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

weak pretests in A, didn't include overflow case

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the fast editorials!

»
7 days ago, # |
  Vote: I like it +5 Vote: I do not like it

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.

  • »
    »
    7 days ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    What else should it error as?

    • »
      »
      »
      7 days ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Something like Query Limit Exceeded.

      • »
        »
        »
        »
        7 days ago, # ^ |
          Vote: I like it +23 Vote: I do not like it

        In interective problems u can use assertion on number of queries to make sure whether it is wrong ans or query limit exceeded

        • »
          »
          »
          »
          »
          7 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Could you please tell me something about how to use assertion to konw whether or not my submission is query limit exceeded.

          • »
            »
            »
            »
            »
            »
            7 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Here is an article on assertion article Here is my yesterday code, although it failed still u can see how I used assert. Code link

      • »
        »
        »
        »
        7 days ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

        IMO this gives too much information, like in constructive problems if you print the wrong length you don't get a custom result.

      • »
        »
        »
        »
        7 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Maybe add if(totalQueriesMade>40) sleep(5) and purposely get TLE (assuming your code won't TLE otherwise). Hack-ish, admittedly.

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice editorial;)

»
7 days ago, # |
Rev. 3   Vote: I like it -8 Vote: I do not like it

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

Spoiler

Thanks

UPDATE: ITS SORTED OUT NOW

»
7 days ago, # |
  Vote: I like it -9 Vote: I do not like it

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;-;

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You need to read the entire line, even if you find sum < 0.

    • »
      »
      »
      7 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you!! I will cry in a corner now:)

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You break possibly before reading the input. I suggest read all the input before solving the testcase.

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    ur code fails on 3 3 0 0 1 3 0 1 0 3 1 0 0 answer is NO , NO , NO I guess your code guess a different answer. Refer https://codeforces.com/problemset/submission/1486/107870392 the function solve2

    • »
      »
      »
      7 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      sorry I stopped taking input when i got the answer so it messed up further inputs...

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi,the logic is no8t making any sense to me. Consider this sequence 0 1 2 2 8 9 20. Do you think your solution will give correct output? Even though h-i is negative at i=3, still the sum becomes positive. But do you think in this case a solution is possible?

    • »
      »
      »
      7 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      the logic is correct, I am checking for every input...I broke when I found the ans...didnt take all the inputs, thats why it gave wrong ans

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have the same mistake as you and wa on test2. Fortunately, I solved it.

»
7 days ago, # |
  Vote: I like it +96 Vote: I do not like it

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

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 days ago, # |
  Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    7 days ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    you get the max median of subarray of length exactly k not at least k

    • »
      »
      »
      7 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you explain why length k is not optimum, i think length k should be optimum

      • »
        »
        »
        »
        7 days ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        n = 3 k = 2

        5 2 5

      • »
        »
        »
        »
        7 days ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        With array $$$[2, 1, 2]$$$ and $$$k = 2$$$, the only possible median for subarrays of length $$$2$$$ is $$$1$$$, but the best possible median is $$$2$$$ attained when we consider the entire array.

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
7 days ago, # |
Rev. 5   Vote: I like it -14 Vote: I do not like it

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?

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    While hi = lo + 1, like lo is equal to 2 and hi is equal to 3, mid calculated by (lo + hi) / 2 is 2. In this point, you'll get stuck by lo = mid because lo will never change.

»
7 days ago, # |
Rev. 5   Vote: I like it +36 Vote: I do not like it

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)

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can't we solve this for general weight. Means we can construct a new graph in which there is an edge between u and v iff there is exactly one vertex z between u and v in original graph s.t. u-z and v-z are edges in the original graph and weight of uv in new graph will be as defined in the problem. Now simply we should run Dijkstra on this new graph.
    What is wrong with this method? Can you please point it out.

  • »
    »
    3 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't understand the meaning of the word "relaxed" here. Can you please explain Ji_Kuai

»
7 days ago, # |
  Vote: I like it +53 Vote: I do not like it

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?

»
7 days ago, # |
Rev. 3   Vote: I like it -33 Vote: I do not like it

Can you help me explain why my code: "Wrong answer on pretest 7"

#include <bits/stdc++.h>
 
using namespace std;
 
 
int n;
int positionOfSecond;
int temp;
 
int query(int l, int r) {
    if (1 <= positionOfSecond && positionOfSecond <= n) {
        printf("? %d %d\n", l, r);
        fflush(stdout);
        scanf("%d", &positionOfSecond);
    }
}
 
int main() {
    positionOfSecond = 1;
    scanf("%d", &n);
    int L = 1, R = n;
    while (L < R) {
        query(L, R);
        temp = positionOfSecond;
        int m = (L + R) / 2;
        if (temp < m) {
            query(L, m);
            if (temp != positionOfSecond) {
                L = m + 1;
            } else {
                R = m;
            }
        } else {
            query(m, R);
            if (temp != positionOfSecond) {
                R = m;
            } else {
                L = m + 1;
            }
        }
    }
    printf("! %d\n", L + L - 1 - positionOfSecond);
    fflush(stdout);
    return 0;
}
»
7 days ago, # |
  Vote: I like it +6 Vote: I do not like it

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

»
7 days ago, # |
  Vote: I like it -38 Vote: I do not like it

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!

  • »
    »
    7 days ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    To debug such scenarios, you can stress test your solution as well.

    You can write a bruteforce for this problem very easily. e.g.

    1. Generate random permutation A.
    2. Take your query into a separate function. Answer it by using the array A. You can find second max in O(n) easily.
    3. In the end, match the maximum element position returned by your program with actual maximum element position.

    Keep doing this for many iterations till you find a counter case. This kind of stress testing strategy helps a lot in many problems. You can see my submission for some hints regarding implementing this bruteforce. The code is really messy and unpolished, but I have attached it for reference anyway.

    • »
      »
      »
      7 days ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      Hey, thanks a lot. Found my mistake! Also, am I not supposed to post solutions in the comments or something? Since I got a lot of negative feedback? If no, then I'll delete the comment.

      • »
        »
        »
        »
        3 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Don't post the solution as it is in the comment. Instead, post a link to the submission or use a spoiler tag

»
7 days ago, # |
  Vote: I like it +74 Vote: I do not like it

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

  • »
    »
    7 days ago, # ^ |
      Vote: I like it -70 Vote: I do not like it

    Unfortunately we won't rejudge all the submissions Uphacks are already added to tests, so from this point all the solutions will be judged with updated tests Sorry for the inconvenience

    • »
      »
      »
      6 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I don't think they are added . Still O(n^2) submissions are getting AC

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

Spoiler
  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It seems that every interval like $$$[1,2],[3,4],\cdots,[n-1,n]$$$ will cost 1 query and the number of those intervals is $$$\Omega(n)$$$. In addition, there are other intervals that will cost 1 query.

»
7 days ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve D by two pointers?

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I tried but it gives TLE on test 5, and I don't think it can be optimized further.

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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..

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    how are you making sure that you always travel two edges at once?

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The binary search asks the question: is there a subarray of some length with a median of at least 1?

    So we replace all elements that are 1 or more in the array with a 1, and those that are less than 1 with a -1, resulting in [1, 1, 1, 1, 1]. We can find a subarray of length at least 3 with the median 1, so it follows that the answer is 1 or more.

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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)

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please explain the formula of problem F?

  • »
    »
    7 days ago, # ^ |
      Vote: I like it +77 Vote: I do not like it

    I'm not sure what the official solution is, but I can try to explain my solution to F. Consider a vertex $$$u$$$, and say we want to count all pairs of paths that have $$$u$$$ as their unique common vertex. First arbitrarily root the tree at $$$1$$$. We break the paths into $$$4$$$ types:

    • up paths: paths that start at $$$u$$$ and go towards the root
    • through paths: paths that contain the parent of $$$u$$$, $$$u$$$, and another node in the subtree of $$$u$$$
    • down paths: paths that have $$$u$$$ as the LCA of the endpoints and are not strictly up or down the tree
    • vertex paths: paths that are from $$$u$$$ to $$$u$$$

    For a fixed $$$u$$$, we can take care of all pairs of paths that contains vertex paths easily, so we ignore those. We can pair any up path and down path. We may also pair through paths and down paths that do not overlap. We may also pair a down path with a down path if they do not overlap. We can easily count all these quantities using Heavy Light Decomposition and LCA.

    Submission link

»
7 days ago, # |
  Vote: I like it +3 Vote: I do not like it

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?

»
7 days ago, # |
  Vote: I like it +4 Vote: I do not like it

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

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

The Problems were Amazing! Thanks for great contest.

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

https://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

»
7 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
7 days ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

When will I become a CM? :-(

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    107905723 In line 150, you are initializing p with INT_MAX, it should be zero because if you don't consider any element ie prev sum, the value of p should be 0.

»
7 days ago, # |
Rev. 6   Vote: I like it 0 Vote: I do not like it

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))

Simulator for Problem C
»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

107911405

  • »
    »
    7 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Worst case needs O(n) queries. Try: [7 6 5 4 3 2 1 8]

    • »
      »
      »
      7 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But I am always halving the search space? Can't seem to figure out the error in my logic.

      • »
        »
        »
        »
        7 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        mid==l is possible, and when you call binarysearch(mid+1, r), you are decreasing the search space by size 1, not halving it.

        More importantly it sometimes gives wrong answer. Try 4 5 6 1 2 3

        • »
          »
          »
          »
          »
          7 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Oh I got it. I made 2 variables mid and and middle and got confused between them :(

»
7 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    7 days ago, # ^ |
    Rev. 4   Vote: I like it +1 Vote: I do not like it

    Let's consider the case when smax<maxpos (the first while loop in the code). The loop invariant property is that the range [l,..,r] always contains ~ smax~~ and maxpos. It is beneficial to break the loop just when l and r become adjacent (i.e. when r - l > 1 becomes false) because now the only way for the above property to hold is that ~~l==smax and~~ r==maxpos, and we can immediately output r (or r+1, in case of 1-based indexing).

    • »
      »
      »
      7 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      why is it like the range[l...r] will contain both smax and maxpos like in the example: 1 4 3 2 5 the loop will break at l=3 and r=4 whereas the index of smax is '1'(0 indexing).

      • »
        »
        »
        »
        7 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oops.. the claim about containing of smax is not true at all.. Feeling stupid now.

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 days ago, # |
  Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    7 days ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Can you please explain problem E, not able to get what the editorial says.

    Spoiler
»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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://codeforces.com/contest/1486/submission/107932779

  • »
    »
    7 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    You get the max median of subarray of size exactly k not at least k so you bug on 3 2 2 1 2 Your answer is 1 true answer is 2

    • »
      »
      »
      6 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      oh got it, I missed the at least part. Thanks a lot man!

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Cause it's the first element to get the needed answer as written in the editorial

    • »
      »
      »
      7 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ok got it, thank you for the very fast response

    • »
      »
      »
      6 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please tell the logic behind using r-l>1 instead of usual l<r in binary search in the editorial solution?

      • »
        »
        »
        »
        6 days ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        I use binary search with subsegment $$$[l, r)$$$, so it means I look at elements $$$l, l+1, \ldots r - 1$$$. This is called a half-interval (in russian at least). That's why $$$[l, l+1)$$$ contains only one element.

        • »
          »
          »
          »
          »
          6 days ago, # ^ |
          Rev. 3   Vote: I like it 0 Vote: I do not like it

          Thanks! If i use l<r, the program stucks in infinite loop like in the sample test case 5 1 4 2 3 it goes like:


          5 ? 1 5 3 ? 1 3 3 ? 2 3 2 ? 1 3 3 ? 1 3 .....

          why so?

          • »
            »
            »
            »
            »
            »
            6 days ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            Well, because l is always less than r. That's the beauty of half-interval.

            • »
              »
              »
              »
              »
              »
              »
              6 days ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Can it be generalised that when we should use l<r and when l+1<r in binary search or is it just for this specific problem?

              • »
                »
                »
                »
                »
                »
                »
                »
                6 days ago, # ^ |
                  Vote: I like it +4 Vote: I do not like it

                I always write binary search this way. Just use half-intervals and you'll be happy. Consider it like this: l is minimal possible value and r is the first value, that is most definitely working out for you. You can rotate the problem (make segment $$$(l, r]$$$ and code wouldn't change at all (only checks and output).

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 days ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  ok,thanks a lot!

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 days ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Thanks for your explanation, really appreciate it!

                  It would be really great, if you could elaborate on these points —

                  Consider it like this: l is minimal possible value

                  Minimal with respect to what condition?

                  and r is the first value, that is most definitely working out for you

                  You mean the first True value?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 days ago, # ^ |
                    Vote: I like it +1 Vote: I do not like it

                  If the answer is in range $$$[1, n]$$$ you would use $$$[1, n + 1)$$$ or $$$(0, n]$$$. That easy, just add 1 (or -1) when needed and cover all the possible answers. Actually $$$(0, n +1)$$$ should work fine too.

        • »
          »
          »
          »
          »
          6 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          What are the initial conditions for l and r, in case I use your half-interval technique?

»
7 days ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

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

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Please help me out with this one. What i thought for A problem is this : Try reducing given sequence to 0,1,2,3,4.... by shifting any extra ele to right and now check if the sequence is strictly increasing or not. Solution : 107820006

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    When $$$Z > A_i$$$ you're incrementing $$$A_i$$$ with the extra rather decrementing extra from $$$A_i$$$.

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell why it is giving wrong output 107936839

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If n = 5 and inputs are 2 1 1 1 1, then for loop breaks in the fourth iteration and the last one is acting as n for next test case.

    • »
      »
      »
      6 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How did you debug so fast... I'm a beginner and often unable to find out mistake in my own code and often waste much time finding out mistakes, please tell how to do that

»
6 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
6 days ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

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

  • »
    »
    6 days ago, # ^ |
    Rev. 4   Vote: I like it +15 Vote: I do not like it

    I have considered $$$0$$$ based indexing of nodes to save memory.

    Since weights of all edges is between $$$1$$$ and $$$50$$$ . For each node say $$$nd$$$ , create $$$51$$$ nodes say $$$nd*51$$$,$$$nd*51+1$$$,$$$nd*51+2$$$,....$$$nd*51+50$$$.

    Now for each edge $$$x,y,w$$$ as input , make edges $$$(x,y,w)$$$ and $$$(y,x,w)$$$ as shown in following code since edges are bidirectional.

    add edges

    Let's understand how Dijkstra will work here with example :

    consider nodes $$$0,1,2$$$ . Suppose edge length between $$$0$$$ and $$$1$$$ is $$$e_0$$$ and edge length between $$$1$$$ to $$$2$$$ is $$$e_1$$$. Thus distance between $$$0$$$ and $$$2$$$ is $$$(e_0+e_1)*(e_0+e_1)$$$ by using definition in question.

    First we will insert $$$0$$$ to priority queue . Since $$$0$$$ is connected to $$$1*51+e_0$$$ with edge length $$$0$$$ , $$$(0,1*51+e_0)$$$ will be inserted in priority queue. Also $$$1*51+e_0$$$ is connected to $$$2*51$$$ with edge length $$$(e_0+e_1)*(e_0+e_1)$$$ , thus $$$((e_0+e_1)*(e_0+e_1),2*51)$$$ will be inserted to priority queue .Hence distance between $$$0$$$ and $$$2$$$ is $$$(e_0+e_1)*(e_0+e_1)$$$.

    Now try to scale above example to any number of vertices and it will be clear why it works.

    priority queue based implementation : 107975317 set based implementation : 107975265

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

What if the problem 1486A - Shifting Stacks was to find the most efficient arrangement of strictly increasing stacks i.e. the strictly increasing arrangement possible with minimum number of moves.

An approach that I thought of:

Spread out the extra blocks given to us evenly with the stacks available. Like for example, we have [0 13 0 0] as the heights, now if we were to make the stacks strictly increasing with the least possible blocks we would have done it like this [0 1 2 3], so here we have got 7 extra blocks which can be spread to 3 stacks as we can't move the blocks backwards. So we can go and spread ceil(extra blocks/stacks available) i,e 2 blocks here to each stack thus making it [0 3 4 5] and that extra block left has to go to the last stack the most efficient arrangement of stacks would be [0 3 4 6].

is this the most efficient way of doing it??

Also what if we were asked to find the minimum number of moves required to make it strictly increasing??

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Let's binary search the answer

How ?

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me in C1? I am getting TLE on 4th test case though third has passed. This is the link to my submission.

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    When your $$$check()$$$ function returns $$$true$$$ for some value $$$x$$$, it does not mean that there will be a subarray with median $$$x$$$, it means that the median is atleast $$$x$$$.

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The answer will only exist for an arbitrary number $$$x$$$ in $$$[1, n]$$$ if there's an subarray of size $$$\geq k$$$ in the prefix array with $$$sum > 0$$$.

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain to me that if we had max as the position of 2nd greatest element in l -> r, if max is still the position of 2nd greatest element in l -> mid ( mid = l + r >> 1) then the position of greatest element is in l -> mid?

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

My submission 108017714

  • »
    »
    6 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    So you are strong enough:)
    Actually, I have written a pretty neat data structure to get RMQ in O(1) online (so it can handle LCA online of course).

    • »
      »
      »
      5 days ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      I didn't understand why you praised me until I actually read your editorial. :)

      I am not going to show off. However, I would like to add my little bit to nowadays's problem approaching style.

      In my opinion, the (nearly)-linear algorithm is the easiest to implement, without using any heavy data structure. Back in to the old days, the people who know HLD / LCT is the true master. XD

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain the logic of taking -1 and 1 in question d .

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Now let's think that smax is less than mid (for symmetrical reasons).

These assumptions are taking me down difficult for me of thinking to assume this

»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

What's wrong in my code... can anyone explain...

Checker comment wrong answer element at position 43742 is not maximum

here is my code for problem C

»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem B, do we not need to consider unique points for x? suppose we have (0,0) (6,1) (8,2) (8,3) (8,4) and (10,4). Then vector for x will have <0,6,8,8,8,10> and the ans for this will be size = 6 x[3] — x[2] + 1 that is 1 but answer should be 3 (6,7,8)? pls help.

  • »
    »
    4 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Why do you think the answer should be 3? The answer is 1(only 8).

    1. for 6: the sum of distance is 16.

    2. for 7: the sum of distance is 14.

    3. for 8: the sum of distance is 12. Cleary, The minimal distance is for 8 only.

»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there a DP solution for problem D?

»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help me why I get Time limit Exceeded in problem D?

»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain logic for problem B, I am having tough time in understanding the editorial for the same.