Misuki's blog

By Misuki, 3 months ago, In English

Except hints/solutions, I try to add a "general idea" section discuss about some general strategy and standard ideas used to solve the problem, hope you would like it :)

2001A - Make All Equal

idea & solution: Misuki

Hint 1
Hint 2
General idea
Solution
Code

2001B - Generate Permutation

idea & solution: Misuki

Hints/General idea of solution path 1
Hints/General idea of solution path 2
Solution
Code

2001C - Guess The Tree

idea: feecle6418, solution: Kaey

Hint 1 for solution 2
Hint 2 for solution 2
Solution
Solution 2
Code
Code 2

2001D - Longest Max Min Subsequence

idea & solution: Misuki, tester's code: SorahISA

Hint 1
Hint 2
General idea
Solution
Code
Tester's code

2001E1 - Deterministic Heap (Easy Version)

idea & solution: Misuki

Hint 1
Hint 2
Further hints for solution path 1 (official solution)
Further hints for solution path 2 (alternative solution)
General idea
Solution
Code

2001E2 - Deterministic Heap (Hard Version)

idea & solution: Misuki

Hint 1
Hint 2
Hint 3
General idea
Solution
Code
  • Vote: I like it
  • +212
  • Vote: I do not like it

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

Someone gotta explain C, cause solution above is unclear.

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

    we can easily find if two nodes have edges or not using a divide & conquer approach. Lets say if we have two nodes $$$ x $$$ and $$$ y $$$. querying them will give us a node $$$ m $$$ such that m is the center of the distance. then we can solve it for $$$ (x, m) $$$ and $$$ (m, y) $$$ and so on until the answer of a query is either of the nodes.

    The second big observation is that the root of tree is 1 so every node will be connected to 1 in some manner. so instead of applying divide & conquer between two random nodes, we can apply divide & conquer to 1 and any of the unvisited nodes yet.

    Submission

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

    For C there is a simpler solution with only n log n queries.

    You can just "root" the tree in 1, and after that for each node, you'll determine is father. For each node $$$a$$$: $$$x_1$$$ = query(a,1)

    $$$x_2$$$ = query(a,$$$x_1$$$) ...

    $$$x_{l}$$$ = query(a,$$$x_{l-1}$$$)

    When $$$x_{l}=a$$$ you stop and you know that the father of $$$a$$$ is $$$x_{l-1}$$$. $$$l<\lceil log(n)\rceil$$$ because each time you divide your path by 2. So at end it'll be n log n queries.

    Hope I was clear.

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

      Edit: Sniped above :)

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

      Why can we root the tree at 1? Can't the root be any one of the nodes provided?

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

        Since the edges are undirected, any node can become the root. Trying to draw a tree starting from any node at the zeroth level will help to understand this.

        Random example
      • »
        »
        »
        »
        3 months ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        Any vertex of the tree can be the root of a tree. So, the statement "the root can be any one of the nodes provided" is true. This means we can choose any node as the root and proceed with the process. Nodes 1, 2, ..., n are all valid choices. In this solution, we chose node 1 as the root, but selecting any other node would also be correct. (But please remember: you can only choose one node as the root in a solution. If you choose a different node, for example, node 3, then you need to consider nodes 1, 2, 4, 5, ..., n.)

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

    consider a and b in a tree and distance between them is 7, so x would be some node in distance of 3 from a, and in distance of 4 from b, now you should change b to x (binary search) now you will give new x between a and new b, and distance between a and x is 1, distance between x and b is 2, that means you have an edge between a and x,

    continue doing this approach for all node from 2 to n, you will find what is the parent of node i, and because we have a tree (we have n — 1 edges, that's why you should loop from 2 to n and not 1 to n), it works true.

    you can see my code for better understanding,

    hope it helps.

    i couldn't accept it during the contest because my previous solution works in O(2*n*lon2(n)) and its more than 15*n.

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

Thanks for the super fast tutorial

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

Fast Tutorial

»
3 months ago, # |
Rev. 2   Vote: I like it +14 Vote: I do not like it

i got ABSOLUTELY crushed. this contest made me rethink my life decisions and contemplate on quitting CP forever :(

gotta give props for the blazingly fast editorial though

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

    Keep going, I had thought about that, but it is very satisfying to see your improvement over time

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

    Well, I still try to go on even after 44 unsuccessful contests. :( Maybe, you can draw some inspiration from me and ...

    Спойлер

    Just kidding!!

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

I don't think I understood B, can someone please explain why for n == 4, 3 1 4 2 isn't valid? I thought that you could build on this for even n, making n==2 the only impossible input.

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

    Forwards takes 2 passes, backwards takes 3.

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

      a = [3, 1, 4, 2]

      The typewriter 1 will go 1 and carriage return once, then go to 2 and carriage return twice and go to 3 and then to 4

      So the carriage return total of typewriter 1 is 2

      Now let's consider typewriter 2, typewriter 2 will go to 1 and carriage return then go to 2 and to 3 and carriage return twice and then go to 4

      Both of them take 2 carriage return so it should be valid rigtht?

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

        Typewriter 1 can go from 1 to 2 without returning in between.

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

        "The typewriter 1 will go 1 and carriage return once, then go to 2 and carriage return twice and go to 3 and then to 4"

        It is possible for typewriter A to collect 1 and 2 without returning. Since we are looking to minimize the carriage return operation, the optimal number would be 2.

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

        if we consider minimum carriage returns in your permutation typewriter1 needs 2 returns and typewriter2 needs 3.

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

    from the pointer facing at 1, to generate 3 1 4 2, you could do 1 2 in one traversal and then return and do 3 4 in 1 traversal. So 1 return in total.

    but from the pointer facing at n, to generate 3 1 4 2, you first need to get to third poositing and make it 1 then return, then traverse to make 2 and 3 and return again and then make 4 (since 4 comes before 3 that way) so you made 2 returns in that way. Minimum of 2 isnt equal.

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

    for left typewriter it will be 1 return pass as 1 2 return 3 4, but for right typewriter it will be 2 return pass as 1 return 2 3 return 4.

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

Super-fast editorial!!!

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

We can do binary search on trees ?!?!

»
3 months ago, # |
  Vote: I like it +10 Vote: I do not like it

this contest gave me the encourage to quit CP

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

Could someone tell me the prbleam about my code? ~~~~~~~~~~ //this is my code from sys import stdout def ss(x,y): if x!=y and b[x][y]==0: print('?',x,y) stdout.flush() z=int(input()) b[x][y]=z if x==z: a.append(x) a.append(y) else: if x<z: ss(x,z) else: ss(z,x) if z<y: ss(z,y) else: ss(y,z) for _ in range(int(input())): n=int(input()) a=[] b=[[0 for i in range(n+1)] for i in range(n+1)] for i in range(1,n): for j in range(i+1,n+1): if b[i][j]==0: ss(i,j) print('!',*a)
~~~~~~~~~~

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

    this is C

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

      Could you please put it in a code block for easier visualization?

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Your code here...
        from sys import stdout
        def ss(x,y):
            if x!=y and b[x][y]==0:
                print('?',x,y)
                stdout.flush()
                z=int(input())
                b[x][y]=z
                if x==z:
                    a.append(x)
                    a.append(y)
                else:
                    if x<z:
                      ss(x,z)
                    else:
                        ss(z,x)
                    if z<y:
                      ss(z,y)
                    else:
                        ss(y,z)
        for _ in range(int(input())):
          n=int(input())
          a=[]
          b=[[0 for i in range(n+1)] for i in range(n+1)]
          for i in range(1,n):
            for j in range(i+1,n+1):
              if b[i][j]==0:
                ss(i,j)
          print('!',*a)      
        
        
        • »
          »
          »
          »
          »
          3 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Please use collapse/spoilers the comments are getting quite messy and lengthy.

»
3 months ago, # |
  Vote: I like it +5 Vote: I do not like it

E1 can be solved in a much simpler way (277414233) without any binomial coefficients or combinatorics.

»
3 months ago, # |
Rev. 4   Vote: I like it +6 Vote: I do not like it

D can be solve in O(n).

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

D was pretty nice, I wish I actually knew trees, so I could attempt C as well. I think I'm gonna reach expert regardless though! very nice contest, thank you!

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

B was easy, If we can understand the problem and write some testcases

In most of such problems , I end up not understanding but today I did B

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

SUPER FAST!Thank You!

The Problem is funny.I love this round!

»
3 months ago, # |
  Vote: I like it +4 Vote: I do not like it

general idea is really useful.

Thanks.

Btw, problem D is nice

»
3 months ago, # |
  Vote: I like it +56 Vote: I do not like it

Another approach to solving problem C is to assume that the tree is rooted at vertex $$$1$$$. For each vertex $$$u = 2, 3, \ldots, n$$$, the goal is to find its parent $$$p(u)$$$.

By using the function $$$\texttt{query}(u, 1)$$$, you can get the midpoint of the path from $$$u$$$ to its ancestor $$$1$$$. Keep halving the path until $$$\texttt{query}(u, x) = u$$$, which means that $$$x$$$ must be $$$p(u)$$$. This method will find $$$p(u)$$$ in no more than $$$\lceil \log_2 (n-1) \rceil$$$ queries!


Code
»
3 months ago, # |
  Vote: I like it +20 Vote: I do not like it

I like that General idea,it really help me much!!!

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

    glad you like it :)

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

      I am sorry to bother you ,but can you tell me the General idea of promlem C
      I am confused about the Solution.I cant find out the index logic.

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

        It have less standard idea and rely on pure puzzle solving ability more in my opinion, but if you have a good perspectice about the problem it might be easier. For example, I think the problem as some kind of spanning tree problem and try to keep finding edge connect different component. (Solution2 in editorial)

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

    I cant understand problem C .How the binary work? Why use the binary search?

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

      Sorry, I was thinking hint for my solution when writing it but the solution part is from coordinator. I've add Soluion2 which correspond to the hint section.

»
3 months ago, # |
Rev. 2   Vote: I like it +16 Vote: I do not like it

Maybe I'm misreading the solution to C, but I think this is simpler. The key idea is that $$$(u, v)$$$ is an edge if and only if querying ? u v returns $$$u$$$. Then, for each $$$2\le v\le n$$$, we can query ? v 1, take the result $$$x$$$ to query ? v x, etc, until we reach some node $$$u$$$ with ? v u being $$$v$$$.

In this way, you can think of this as rooting the tree at node $$$1$$$ and discovering the parent of node $$$v$$$ for each $$$v\neq 1$$$ in this rooted tree, which must by definition give $$$n - 1$$$ distinct edges.

Edit: Sniped above :)

»
3 months ago, # |
  Vote: I like it +12 Vote: I do not like it

It seems I have an alt approach for C.

Step 1-1
Step 1-2
Step 2

277363292

Additional note
»
3 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it
Another way of doing C

Edit: seems like a few other people posted the same solution while I was typing it, lol

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

For C I did the following. Initialize a stack of pairs with all (i, j) where i < j. While the stack is empty, I pop (a, b). I check using a DSU if a and b belong to the same connected component (that has been discovered till now, and skip if they do. If they don't, then I query ? a b and push the output x to the stack if x != a. Otherwise, I push the found edge and merge the two components.

I think this should always find all edges while remaining under the query limit. But I don't understand why this WAs. Could someone explain?

277403335

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

For C, I used DFS and it seems to have worked somehow. Could someone explain it?

277409228

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

Do anyone know a software that have a faster execution for interactive problem?

I use jdoodles but it not stable

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

I was unsure before submitting the code for problem C but it passed the pretests.

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

Problem D is nice idea but it's hard implementation!

»
3 months ago, # |
Rev. 2   Vote: I like it +20 Vote: I do not like it

Solution D in O(n) (attempt: 277409175)

We will store the current response in the ans array. Initially, ans is empty.

Let's build an array r, where r[x] is the maximum index i, such that c[i] = x

Let's build an array of used, where used[x] = True if the value of x is contained in ans and False otherwise. Initially, all values are False

Let's go through the c array.

Let's consider the value of c[i], if used[c[i]] = True, go ahead, otherwise we will execute the next cycle:

If ans is empty, we do nothing and exit the loop

If r[ans.back()] <= i, exit the loop

1) If ans.size() % 2 == 0, then

1.1) If c[i] < ans.back(), then delete the value of ans.back(), do not forget to put the corresponding value to the array used (used[ans.back()] = False) and return to the beginning of the cycle

1.2) Otherwise (if c[i] > ans.back()), check

1.2.1) If c[i] > ans[-2] (the penultimate element in ans), then remove the last two elements from ans, do not forget to change used, return to the beginning of the cycle

1.2.2) Otherwise (if c[i] < ans[-2]), exit the loop

2) Otherwise (if ans.size() % 2 == 1) we perform actions similar to 1), but change the signs to the opposite ones (> to <, and vice versa) After the loop, add c[i] to ans, do not forget to change used (used[c[i]] = True)

When we go through the entire c array, the ans array will be the optimal answer.

Since we add and remove each element from ans once, the asymptotics is O(n)

»
3 months ago, # |
  Vote: I like it +15 Vote: I do not like it

Reading question B reminds me of how research papers are written ;))

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

The problems were enjoyable, but Problem B lacked clarity. In future contests, it would be great to see more emphasis on covering more cases for such problems.

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

What topics should I learn to solve problem D?

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

C does not use binary search as mentioned in the editorial, but some version of binary lifting

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

    Sorry, I've add binary search solution on it (Solution2)

»
3 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Good quality contest, thank you !

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

for B we can just say if n even then not possible and if odd

we can construct like this--

for 3 -->1 3 2 for 5 -->1 3 5 4 2

for 7 -->1 3 5 7 6 4 2

and so on

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

A super simple way to solve C:

Spoiler
»
3 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Awesome work! Love those general ideas!

»
3 months ago, # |
  Vote: I like it +6 Vote: I do not like it

D can be done with simple stack

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

First though of dp ,then greedy approach striked but wasnt able to implement it.

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

Can someone please help me figure out what is wrong in my soln to D link

In this:
I have a turn variable which tells us that we have to maximize or minimize the next element to be chosen.
A variable lst that keeps the last printed index.
A set st that keeps track of the elements that can be selected in future with their indices.
A map that keeps the count of elements that are left in the array and are not visited till now.

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

Does anyone have test cases for D? Looks like I'm failing somewhere on Test 3.

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

    I figured some out for my submission

    Here's one that I failed on:

    1
    7
    4 1 2 4 5 2 1
    

    Answer should be:

    4
    4 1 5 2
    

    An even simpler one I failed on:

    1
    5
    4 2 4 1 2 
    

    Answer should be

    3
    4 1 2
    
»
3 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

off-topic but quick question: why is my activity section different for everyone except me? i see a 15 day streak when logged in while in incognito mode i see an 11 day streak, is this normal?

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

    i think it shows it on your local time when you're not incognito, but when you use incognito, your local time defaults to whatever incognito is set to be. so for some time zones you didn't actually keep your streak.

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

      man i was trying making a 90 day streak, sad :(

      gotta start again now

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

        i wouldnt say you have to start again, youre bound to lose the streak on some timezones that are far from yours. good job on the streak so far though, i hope you'll reach your goal

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

          thanks, looks like you just turned expert too. congratulations!

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

Wasn't able to completed problem D during contest but I liked it.

And the general idea section is super useful.

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

Can someone please tell me what i did wrong in the 3rd question

https://codeforces.me/contest/2001/submission/277397815

It's been 1.5 hours and i have read many other solutions and even the official one, and i do not understand where my logic went wrong.

thanks

»
3 months ago, # |
Rev. 2   Vote: I like it -10 Vote: I do not like it

Dear tester, Kind request, when you write program to match the contestant's output, with correct output, Please give some meaningful errors, which can help the user in debugging the issue.

wrong answer 3919th numbers differ — expected: '1', found: '3'

How am I supposed to know, 3919th number is from which test case ????

It would have been great help, if you had simply put here the test case number, I could have used some tricks to find out where my solution is failing :| .

cc: Misuki

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

What is the difference between Code and Code 2 for the C problem? I tried and was not able to find the difference :(

Both look exactly the same. I mean Letter by Letter.

»
3 months ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

when i trying to hack this submission, it shows "Unexpected verdict".

here is gen:

#include<bits/stdc++.h>
using namespace std;
const int N=3e5-4;
int main() {
    cout << 1 << endl;
    cout << N+1 << endl;
    for(int i=1,l=1,r=N;i<=N/2;i++) {
        if(i%2==1) {cout << r << ' ';r--;}
        if(i%2==0) {cout << l << ' ';l++;}
    }
    cout << N/2 << ' ';
    for(int i=1,l=1,r=N;i<=N/2;i++) {
        if(i%2==1) {cout << r << " \n"[i==N/2];r--;}
        if(i%2==0) {cout << l << " \n"[i==N/2];l++;}
    }
}

It seems that some code that should be TLE is incorrectly tagger correctness in polygon, please check this.

upd. physics0523 seems facing same question?

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

    Maybe some intended solution on Polygon also gets hacked or validator is broken or something

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

      Turns out a tester's solution TLE on the hacked test, now it should be fixed.

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

        Let's share my generator:

        #include<bits/stdc++.h>
        
        using namespace std;
        
        int main(){
          ios::sync_with_stdio(false);
          cin.tie(nullptr);
          cout << "1\n";
          cout << "300000\n";
          for(int i=0;i<300000;i++){
            if(i){cout << " ";}
            int a;
            int j=i%100000;
            if(j%2){a=1+(j/2);}
            else{a=300000-(j/2);}
            if(100000<=i && i<200000){a=i;}
            cout << a;
          }cout << "\n";
          return 0;
        }
        

        Some false (and maybe too straight-forward simulation) solutions takes $$$O(N^2)$$$ in this case.

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

Am i missing something in D?

Here is what i did (ITS WRONG and idk y):

3 arrs:

Step 1
Step 2
Last step

this gave me wrong answer on pretest-2 meaning that it isn't the correct logic, i just want to know why

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

Thanks for the general ideas, hints, and fast editorial. Really appreciate it!!

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

I Think in problem D it is more intuitive to think about storing range min and max in a segment tree and once an element is taken update min value to 1e9 and max value to -1e9.

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

    Agreed, segtree was easier to think in this question.

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

    My solution-https://codeforces.me/contest/2001/submission/277423515 I have used 2 segment trees, it can be implemented in the same tree using a structure to store min and max or as a pair.

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

I still can't figure out why my submission to C is incorrect and giving wrong ans. Somebody please help ,my implementation is clean

My submission

Found it! I was randomly printing the ans at the end , didnt see that we have to print serial wise 1..n-1

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

For A , the hint encourages us to think about the lower bound of the answer . For me it is 0 (the case where all the elements in the array are equal ) , and that doesn't help in any way . What did the author expected as an answer when they gave us this hint ?

I know this is a very silly question perhaps even meaningless but any help is appreciated

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

    I mean the lower bound of the answer for any fixed $$$a$$$, not necessarily with all elements equal

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

I am new to interactive problems. My solutions got idleness limit exceeded. It is mentioned in the statement that this happens when you don't flush the output put I do. Can someone suggest what would be the problem?

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

    If you are using c++. then please refer to this.

    1. Don't use the cin.tie() or cout.tie()
    1. Define this in your headers.

    #define IOFLUSH fflush(stdin);fflush(stdout);

    Whenever you take input, or print any output. just write this statement before and after it, to avoid any sort of issues.

    IOFLUSH

    This should solve the issue.

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

      I would use cout<<flush or cout.flush() instead of fflush(stdout); the latter only flushes cout if you didn't set ios::sync_with_stdio(0), because stdout and cout are not the same thing (I'm assuming you use cin and cout for I/O). I'm also pretty sure flush(stdin) doesn't do anything, but I could be wrong about that.

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

        I got a bit confused now. If I am setting isos::sync_with_stdio(0) I should use cout << flush; or cout.flush(); ? another question doesn't cout << endl; do the work? I think after the contest when I upsolved the question I just used cout << endl; only

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

          cout<<flush and cout.flush() do the exact same thing, so it doesn't matter. As for cout<<endl, it flushes and outputs a newline at the same time, which is often desirable and it can be the only way your code flushes, but writing something like cout << answer << '\n'; cout << endl gives you an extra newline (though I'm not sure if that actually matters). So if you want to define something like IOFLUSH to use in the way comment above says, using cout<<endl would be weird and possibly wrong, but for flushing one line, it's perfectly fine to just write cout<<endl instead of cout<<'\n' whenever printing a newline.

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

Can someone hack my solution for problem D 277416865. The complexity is O(nlog²) and I think the worst case is :

n , 1 , n-1 , 2 , n-3 , 4 , n-4 , 5....

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

Can someone explain me B? I don't think I can understand the task properly(maybe cuz im dumb ;() but why can't i just go forward without returning on bot typewriters, or maybe thats not how pointer works?

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

    The problem states that, in a move operation:

    Such operation can be performed only if after the operation, $$$1≤i≤n$$$ holds.

    Hence, after moving to the last position, the pointer must return to its initial position to be able to write again.

    The way I understand this problem, a valid permutation should have the same number of inversions of consecutive numbers, going from left to right and from right to left. One way to achieve such a permutation is to start at the middle index and go back-and-forth in the array until it goes out of bounds (or vice-versa).

    277352967

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

Can anyone help me find error in my code? I'm trying to solve D and it is giving wrong answer on test case 3. Here is my submission: https://codeforces.me/contest/2001/submission/277428182

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

Can anyone find my error in problem C? This is my submission 277387198, which should be quite self explanatory. I tried to find the edges on the path $$$1---u$$$ for all undiscovered node $$$u$$$ by querying $$$(1,u)$$$. If it returns $$$x$$$, query $$$(1,x)$$$ and $$$(x, u)$$$. Skip the query $$$(1,x)$$$ if x is already discovered.

The solution looks ok to me, and I got a verdict saying WA on test $$$5$$$, but seems like test $$$5$$$ is a tree with edges $$$1-2,1-3,1-4$$$ which my solution can detect. Any help with the solution or a test case that fails will be helpful. Thanks.

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

I solve problem D using Lazy segment tree. My solution: 277441928

I hope it is helpful.

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

Problem D didn't have strong enough test cases a O(n^2) approach gets ac in main test, the triggering worst case test would have been n/2 1 n/2-1 2........ repeated twice.

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

    Came here to say that.

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

    Sorry about that, I didn't notice such bruteforce solution during preparation, I would take more care about such thing next time :(

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

I am not able to understand the last paragraph of the Editorial for Problem D. Can someone explain it in detail? Also How to solve it using segment trees?

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

    Hey,can you help me with C my solution,I used something similar to the editorial but it exceeds 15n queries however for any numbers of node it can only go upto 2^(ceil(log2(n))+1) operations. Code:277462404

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

In question D ,Accepted solutions of the contest are judged till only 30 test cases while judging is now taking place on more test cases. Matter of surprise is that many accepted solutions are now giving Time limit exceeded on test cases after 30.

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

Can anybody tell me why my code gives wrong answer on test case 3 for problem C

code link: https://codeforces.me/contest/2001/submission/277440400

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

problem C : code for solution 1 is the same as solution 2

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

can someone explain d&c wtih dsu solution in problem C

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

My solution with divide and conquer: Submission #277404397

Why the maximum query count does not exceed 15n?

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

I am confuse about problem B, maybe I am wrong, I thought for all odd case, I just need to swap(a[0],a[n//2]), for example: [3,2,1,4,5] -- > type 1: 1 -->2-->3,4,5; type 2: 1,2,3 -->4-->5

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

In Problem C I was getting idleness limit exceeded on testcase 2 but when i corrected the logic of the code the error was gone..so i wanted to ask that can idleness limit exceeded error occur also when your code's logic wrong?

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

I always get hints for problems rated high like D but don't know why I didn't able to solve the problems

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

Both codes for C are the same...

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

Thank you for the fast editorial and I love the General idea sections.

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

where did the binomial coef come from in problem E1

edit : i think i get it using the stars and bars method we can move the size — 1 to a next node or increase the value at the current node till the root

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

    For anyone else wondering about where the binomial coefficients come from, here's an alternate explanation.

    Let's try to find the number of unique max heaps using the $$$k$$$ operations without worrying about the deterministic conditions. We start with a max heap (since all elements are zero), and doing an operation maintains the max heap invariant. So, we only have to blindly apply the operation on nodes.

    Let $$$T = 2^{n} - 1$$$

    The first thought that comes to mind is to perform the first operation on a random node, and then recurse for the same tree, with $$$k - 1$$$ ops left, i.e, something like

    $$$f(k) = T\cdot f(k - 1)$$$

    However, this leads to overcounting. Consider

    • Configuration 1 : Node $$$x$$$ is chosen in round 1, and it's child $$$c$$$ is chosen in round 2.
    • Configuration 2 : Node $$$c$$$ is chosen in round 1, and it's parent $$$x$$$ is chosen in round 2.

    Notice that if $$$k = 2$$$, these configurations are essentially the same. Hence, we can deduce that round number at which a particular node participated is not important, what's important is how many rounds did it participate in.

    So, let's call the number of participation rounds for each node as $$$x_1, x_2 \dots x_T$$$, then, since there can only be $$$k$$$ different rounds, we should have

    $$$x_1 + x_2 + \dots x_T = k$$$

    So the number of unique max heaps is the non-negative integral solution for this equation, which is pretty well known via Stars and Bars to be $$$k + T - 1 \choose k$$$

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you explain the transitions for E1 in greater detail? I've been stuck trying to understand how the previous states are used to compute the next ones.

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

      First, let's find out the number of unique max heaps using the $$$k$$$ operations (Let's disregard deterministic properties).

      $$$dp[n][k]$$$ represents the number of unique max heaps on $$$n$$$ levels perfect binary tree with $$$k$$$ operations. Then, let's think about how many operations will we use at the root, $$$root \in [0, k]$$$, and the remaining number of operations is $$$remain = k - root$$$.

      Then, from the remaining number of operations, we need to distribute some operations to the left and right subtree. How many operations can left receive? $$$left \in [0, remain]$$$, Therefore, $$$right = remain - left$$$. After distributing the operations, the left and right subtree have become independent. Hence, the transitions are:

      $$$ dp[n][k] = \sum_{remain \in [0, k]} \sum_{left \in [0, remain]}(dp[n - 1][left]*dp[n - 1][right]) $$$

      Note that $$$dp[n][k]$$$ is $$$T + k - 1 \choose k$$$, as described in my earlier comment, but I just showed you a DP instead of a combinatorics approach.

      Now, how do we count unique deterministic max heaps? The first thought that comes to mind is to track the final value of each node, something like $$$dp[n][k][val]$$$. However, if you think about it, this value parameter can be inferred from other parameters. The root will always have $$$val = k$$$.

      Then, you might think about blocking the transitions when $$$left = right$$$. However, that is also incorrect, because left and right child are allowed to be equal if the node is not on the path defined in the problem. This means that we need to track another DP parameter, which would be a boolean.

      $$$dp[n][k][on\_path]$$$ is no. of unique max heaps on $$$n$$$ levels with $$$k$$$ operations such that $$$on\_path$$$ denotes whether root is on the path.

      But since 3D DP will be hard to visualize and optimize, let's remove the boolean parameter, and maintain two 2D DP. Define $$$indp[n][k]$$$ to be the number of unique deterministic max heaps when the root is in the defined path. Similarly, define $$$outdp[n][k]$$$ to the number of such configurations when root is not on the path.

      To perform the transitions,

      $$$ outdp[n][k] = \sum(outdp[n - 1][left]*outdp[n - 1][right]) $$$

      If $$$left > right$$$

      $$$ indp[n][k] = \sum(indp[n - 1][left]*outdp[n - 1][right]) $$$

      But if $$$left < right$$$

      $$$ indp[n][k] = \sum(outdp[n - 1][left]*indp[n - 1][right]) $$$

      There are $$$O(N \cdot K)$$$ states and transitions are $$$O(K^2)$$$. Hence, the time complexity is $$$O(N \cdot K^3)$$$.

      How to optimize it? Before we do that, let's consider the problem of finding the sum of pairwise product in an array

      $$$ \sum_{i < j} a[i] \cdot a[j] $$$

      You immediately know a 1D DP approach. But can you optimize this 2D DP. Why or why not?

      for gap in [1, n]:
      	for i in [1, n]:
      		j = i + gap
      		if j <= n:
      			ans += a[i]*a[j] 
      

      Optimization is not possible, because when a gap is fixed, there is no pattern, or any number that remains constant. However, we didn't really need to fix the gap, we could've fixed $$$a[i]$$$ and inferred all the possible gaps, and come up with $$$a[i]*suffix\_sum$$$.

      We will use the same trick here. Instead of fixing $$$root$$$ and then iterating through $$$left$$$, let's directly iterate through $$$left$$$ and notice its contribution. You'll realize that $$$indp$$$ only takes contribution from a subarray sum of the previous row of $$$outdp$$$. Hence, you can optimize using prefix sums.

      for left in [0, k]:
      	remain = k - left:
      	for right in [0, remain]:
      		outdp[n][k] += outdp[n - 1][left]*outdp[n - 1][right]
      	for right in [0, min(left - 1, remain)]:
      		indp[n][k] += indp[n - 1][left]*outdp[n - 1][right]
      	for right in [left + 1, remain]:
      		indp[n][k] += outdp[n - 1][left]*indp[n - 1][right]
      

      The time complexity is now $$$O(N \cdot K^2)$$$.

      Code

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Hey, thanks a lot for the quick reply and detailed explanation! I think I understand your solution, though I think there's a small typo where outdp[n — 1][k] is supposed to be outdp[n-1][left]. Would you also be able to explain the DP transition in the editorial solution?

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

          It's the same as the transitions in my DP, except it does the heavy lifting through combinatorics (which isn't really required, it can be offloaded to DP).

          Notice that my $$$outdp[n][k] = {n + T - 1 \choose k}$$$. (We can see from combinatorics above, but we also chose to calculate it using DP. Let's call it as $$$f(n, k)$$$ from now on.

          If you don't want to compute it explicitly, just remove the $$$outdp$$$ matrix altogether. Then, you'll notice that the $$$dp[n][k]$$$ in editorial's solution is same as my $$$indp[n][k]$$$. Then, take my old transitions,

          for left in [0, k]:
          	remain = k - left:
          	for right in [0, min(left - 1, remain)]:
          		indp[n][k] += indp[n - 1][left]*outdp[n - 1][right]
          	for right in [left + 1, remain]:
          		indp[n][k] += outdp[n - 1][left]*indp[n - 1][right]
          

          and let's remove all keywords that reference $$$outdp$$$ and use the combinatorics equivalent.

          for left in [0, k]:
          	remain = k - left:
          	for right in [0, min(left - 1, remain)]:
          		dp[n][k] += indp[n - 1][left]*f(n - 1, right)
          	for right in [left + 1, remain]:
          		dp[n][k] += f(n - 1, left)*dp[n - 1][right]
          

          The editorial's transitions are written in a fancy way using $$$x \in [0, j)$$$ $$$l \in [j + x, k]$$$ But my transitions with left and right are doing the same thing, except I use Receiving DP while editorial uses Distributing DP.

          If you want to visualize how trees are computed using editorial's, you can just visualize how trees are computed using left and right variables above, and apply the same thing there. The crucial idea here is that since you are calculating indp, one of the child would go to outdp, and one would remain for indp, hence that's why you see the product of binomial coefficients with DP. If you understand the above DP, you should be able to understand editorial's DP as well. Let me know if anything specific that you're confused about.

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Yup, that makes a lot of sense now. Thanks a lot!

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

can anyone help me figure out why this solution is failing? I have tried a few different things but Im stuck and can’t seem to find the problem 277468507

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

Hi, what might have gone wrong here? (Problem C)

-Thank you!

void dfs(int node,deque<int> adj[],deque<int>&vis1){
    vis1[node]=1;
    for(auto x:adj[node]){
        if(vis1[x]==0){
            cout<<node<<" "<<x<<" ";
            dfs(x,adj,vis1);
        }
    }
}
void solve(){
	int n;
	cin>>n;
	deque<int> v(n+1,0);
	for(int i=1;i<=n;i++){
        v[i]=i;
	}
	deque<int> adj[n+1];
	queue<pair<int,int>> q;
	map<pair<int,int>,int> vis;
 	for(int i=1;i<=n-1;i++){
        q.push({i,i+1});
            if(vis.count({i,i+1})){
                continue;
            }
        while(!q.empty()){
            char c='?';
            int x=q.front().first,y=q.front().second;
            if(x>y){
                swap(x,y);
            }
            q.pop();
            if(vis.count({x,y})){
                continue;
            }
            vis[{x,y}]=1;
            cout<<c<<" "<<x<<" "<<y;
            cout<<endl;
            int node;
            cin>>node;
            if(node==x || node==y){
                adj[x].pb(y);
                adj[y].pb(x);
            }
            else{
                q.push({min(x,node),max(x,node)});
                q.push({min(y,node),max(y,node)});
               }
           }
    }
    cout<<"! ";
    deque<int> vis1(n+1,0);
    dfs(1,adj,vis1);
    cout<<endl;
 
}
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Stuck with problem D still.

I get it that we wanted to greedily build the sequence by picking the best element within the set of element with the right number of distinct values goes after it,

What baffles me is that this is a changing quantity. Let's say the test case is

arr: [5,4,2,1,3,5,2,1]

we can easily construct cnt (cnt is the number of distinct values goes on or after it)

cnt: [5,5,4,4,4,3,2,1] 

At this point it is fairly obvious that we should choose 5 so that -5 is lexicographically smallest, but then the cnt changes to

arr: [5,4,2,1,3,5,2,1]
cnt: [x,4,3,3,3,x,2,1]

The change is that everything before the last occurrence of the removed element has to have their cnt subtracted by 1.

I don't understand how can we solve this with a priority queue (or a bunch of them).

  • »
    »
    3 months ago, # ^ |
    Rev. 5   Vote: I like it +4 Vote: I do not like it

    Video editorial for D

    You count array changes in each iteration, yes. But there's a smart way to do a lazy update of this count array in amortized $$$O(n)$$$.

    You have already deduced that something strange happens when an element appears for the last time. So, let's mark all such indices in RED. We will mark all the other indices as green.

    arr: [5, 4, 2, 1, 3, 5, 2, 1]

    col: [G, R, G, G, R, R, R, R]

    It's easy to see that the size of the answer is equal to the number of red indices. What more can you infer? Consider the first red index. Every green index to the left of it will have the maximum number of distinct elements to the right. Hence, all of them are possible candidates for the 1st element. However, notice that since this is the first red index, this is your last chance to take one copy of the element that it's representing. So you need to greedily construct subsequence from the prefix ending at red such that the value of the final element selected is equal to the value of the red element.

    So, suppose you take 5, of course, the count array changes, but the color array gives you the required info to track this change. Specifically, all elements between the last chosen element and the second occurrence of the red index would have the maximum number of distinct elements to the right that is possible and they are the only possible candidates for the second element. (Why? Because if you go past the second red index without taking it, you will lose one element forever).

    The crucial idea here is to notice that it's a hard task to update each element in the count array, so we instead focus only on the updated values of the possible candidates, and we also don't need to keep track of the number of distinct elements to the right, we only care about candidates that have the maximal number of distinct elements to the right which are not yet taken. And this can be easily maintained by that color array I showed you.

    Code implementing this idea

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

      Thanks, with your help, I finally get this accepted.

      I hope the code is clear — it is basically your idea by only keeping the valid candidates, no need to worry about the number of distinct elements of any other invalid ones.

      I think I might be able to simplify it a lot more if I delete the element more lazily, having to implement a priority queue that support deletion seems too much for a contest problem.

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

This is some text. I don't understand why I exceed time limit in problem B.Can someone please tell me?

// this is code
#include<cstdio>
using namespace std;

int main(){
	int t;
	scanf("%d",&t);
	int num;
	for(int i=0;i<t;t++)
	{
		scanf("%d",&num);
		if(num%2==0){
		printf("-1");
	}
		else 
	{
		for(int j=num;j>=1;j-=2)printf("%d ",j);
		for(int j=2;j<=num-1;j+=2)printf("%d ",j);
	}
		printf("\n");
	}
	return 0;
}

The rest of the text. close

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

Help needed in my C solution, according to the code as far as I can think my solution should have asked <15n queries but it isn't and is failing.someone please have a look,it's idea is somewhat similar to the editorial. Code:277462404

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

Here's an $$$O(n)$$$ stack solution for D.

277484094

The problem is very similar to the LeetCode problem 1081. Smallest Subsequence of Distinct Characters but this time we have two stacks, one for the even indices and odd ones.

Then, when checking to pop and replace an element in one of the stacks, we can only do so if both stacks' top elements appear later on in the sequence.$$$^{\star}$$$

There was a bit of annoying casework on the lengths of the stacks (the max stack length is always $$$\geqslant$$$ the min stack length) to get it all to work.

$$$^{\star}$$$ slightly oversimplified, if both stack sizes are equal and we wish to replace the min stack's top, we don't need to check the max stack's top since it for sure comes before the min stack's top. The max stack case is handled similarly.

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

    I also solved that LeetCode problem before and noticed that it's very similar (unfortunately I didn't look at D during the contest because of C), but for some reason my implementation is getting "wrong answer 119167th numbers differ" on test 4, not sure if anyone had a similar problem

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

      Take a look at Ticket 17481 from CF Stress for a counter example.

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

        Thank you very much, found the issue very quickly from there — I didn't skip the value if it's already in the stack.

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

No general idea given for C, here's my suggestion: Usually half/middle indicates binary search applies to the problem.

»
3 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Please continue this General idea thing for the upcoming contests on codeforces, they are really useful.

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

how does the calculation of NCR(x+2^i−2,x) work for E1? how to find (x+2^i-2)! %p or (2^i-2)! %p when i is up to 500?

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

    We can write C(x+sz-1,x) = fact[x+sz-1] * ifact[x] * ifact[sz-1] = sz*(sz+1)...*(sz+x-1) * ifact[x]

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

      sz can be up to 2^500??

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

        Ya but we only need sz%p which can be calculated using binary exponentiation

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

          I just tried to understand the formula and it made much more sense now. Thanks!

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

Finally solved C after 10 wrong submissions!

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

I could not understand the problem C.

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

Misuki

I think in E2, the first condition of the last picture's transition (the second case in counting) needs to be:

$$$L' > L > R'$$$ and $$$L' > L > R$$$

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

    Thanks you, I've fix it. the second one is $$$L' \ge L + R$$$ because the nature of the operation (i.e. whenever you add $$$1$$$ to a node, you would also add $$$1$$$ to its ancestors)

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

My solution for C:
https://codeforces.me/contest/2001/submission/277413728
Idea: root the tree at 1, find the path from all nodes to 1. Mark all nodes that have found the path to 1. Let c = query(a,b), if c==a then there is a is connected to b; else recursively query(a,c) and query(c,b), then mark a and mark b. If a and b having already been marked, that mean we already found the path from 1 to a and from 1 to b, there are already a path from a to b, so we don't need to find again.

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

277619651

this is my submission for D. Can anybody help in finding the issue.

My approach is very similiar to that of the editorial. I iterate over the pairs (last index of x, x), and maintain a multiset of elements of "a" between any two pairs, greedily picking max or min. (WA on tc3)

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

can anybody tells me if there are any problems?wa3,i am really sick of it ~~~~~ int ask(int x, int y) { cout << '?' << ' ' << x << ' ' << y << endl; cout.flush(); int res; cin >> res; return res; }

void dfs(int x, int y) { if (x == y)return; if (mp[{x, y}])return; mp[{x, y}] = 1; int ans = ask(x, y); if (ans == -1) { return; } if (ans == x || ans == y) { res.push_back({ x,y }); } else { dfs(x, ans); dfs(ans, y); } return; }

void solve() { mp.clear(); int n; cin >> n; for (int i = 2; i <= n; i++) { dfs(1, i); } cout.flush(); cout << '!' << ' '; for (auto item : res)cout << item.first << ' ' << item.second << ' '; cout << endl; mp.clear(); res.clear(); }

~~~~~

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

How to efficiently calculate combinatorics in E1? I thought it takes 2^i operations to calculate

  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it -8 Vote: I do not like it

    You will see we can calculate it with $$$O(X)$$$ if you see submissions or official code.

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

D is a tough problem but Shayan implementation is so clean and easy to understand! Thank you for your video tutorial!

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

Can someone help with this submission failure for problem D?

3rd test case is failing: wrong answer 7289th numbers differ - expected: '1', found: '2'

https://codeforces.me/contest/2001/submission/277681400

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

My solution for D gives me tle, but I don't think I should get tle

277711569

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

Help Needed with Problem D : Longest Max Min Subsequence (Codeforces Round 967 Div. 2)

Hi everyone,

I'm currently working on Problem D : Longest Max Min Subsequence from Codeforces Round 967 (Div. 2). You can find the problem here (https://codeforces.me/contest/2001/problem/D?mobile=true ).

I've been stuck with a "Wrong Answer" on test 4. You can check out my submission here(https://codeforces.me/contest/2001/submission/277854508).

The checker log says that the 79924th number is different than expected, with my code outputting '4' instead of the expected '3'. Would appreciate If someone could point out the bug or find the test case where my code is failing .

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

I am getting WA on test case 3

void query(int i,int j,vvi &ans,map<pi,int> &check){
	if(check.find({i,j})!=check.end())
		return;
	check[{i,j}]=1;
	cout<<"? "<<i<<" "<<j<<endl;
	cout<<flush;
	int temp;
	cin>>temp;
	cout<<flush;
	if(temp==i){
		ans.pb({i,j});
		return;
	}
	query(i,temp,ans,check);
	query(temp,j,ans,check);
}
 
void solve(){
    int n;
	cin>>n;
	map<pi,int> check;
	vvi ans;
	for(int i=2;i<=n;i++)
		query(1,i,ans,check);
	cout<<"!"<<" ";
	for(auto i:ans)
		cout<<i[0]<<" "<<i[1]<<" ";
	cout<<flush;
}

Someone please help

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

why this solution for C is giving TLE link

code
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It's a great solution and tutorial!! Thank you very much!!

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

E2 editorial is impossible to understand even if you've already solved the problem before. (or it's just me being weak)

UPD: nah, it's ok.

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

getting wrong ans in tc3 at last tc..can anyone explain whats wrong in this method bcoz that tc is at very end so its hidden!

#include<bits/stdc++.h>
using namespace std;
#define int long long int
const int mod = 1e9 + 7;
bool cmprt(pair<int,int>& a, pair<int,int>& b)
{
    if(a.first!=b.first) return a.first>b.first;
    else return a.second<b.second;
}
bool cmplft(pair<int,int>& a, pair<int,int>& b)
{
    if(a.first!=b.first) return a.first>b.first;
    else return a.second>b.second;
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
 
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
 
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        vector<int>v(n);
        for(auto &it:v) cin>>it;
        vector<int>dist(n);
        unordered_set<int>s;
        for(int i=n-1;i>=0;i--)
        {
            if(s.find(v[i])!=s.end()) s.erase(v[i]);
            dist[i] = s.size();
            s.insert(v[i]);
        }
        int len = s.size();
        deque<pair<int,int>>dq[len+1];
        for(int i=0;i<n;i++)
            dq[dist[i]].push_back({v[i],i});
        unordered_set<int>taken;
        int takemxi = 1;
        int cur = -1;
        vector<int>ans;
        for(int i=len;i>=0;i--)
        {
            while(!dq[i].empty())
            {
                if(takemxi)
                {
                    sort(dq[i].begin(),dq[i].end(),cmprt);
                    while(!dq[i].empty() && (taken.find(dq[i].front().first) !=taken.end() || dq[i].front().second<=cur))
                        dq[i].pop_front();
                    if(!dq[i].empty()){
                        ans.push_back(dq[i].front().first);
                        taken.insert(dq[i].front().first);
                        cur = dq[i].front().second;
                        takemxi = 0;
                    }
                }
                else{
                    sort(dq[i].begin(),dq[i].end(),cmplft);
                    while(!dq[i].empty() && (taken.find(dq[i].back().first) !=taken.end() || dq[i].back().second<=cur))
                        dq[i].pop_back();
                    if(!dq[i].empty()){
                        ans.push_back(dq[i].back().first);
                        taken.insert(dq[i].back().first);
                        cur = dq[i].back().second;
                        takemxi = 1;
                    }
                }
            }
        }
        cout<<len<<endl;
        for(auto &it:ans) cout<<it<<" ";
        cout<<endl;
    }
    return 0;
}