vishudon's blog

Really need help in understanding why my approach is wrong. Please help.
By vishudon, history, 3 years ago, In English

Hi there,

I hope you all are doing very good. I'm trying to solve rated 1600 problems, and recently got this interactive problem: Problem Link

For solving this problem, I followed this below approach:

Step1: I decided to ask these (n-1) queries: ? index n (for all index in [1, n-1]).

Step2: Then, I created an empty array remArray of size n for storing all the (n-1) remainder values provided by the judge of each query asked by the user. Obviously, judge will return values between [0, p[n]-1] in each query.

Step3: Now, once I took all the (n-1) remainder values, I stopped asking for remainder values input. I started my implementation following the below procedure:

a) Calculating maximum value in the remainder array so that I could identify which value needs to be present at nth index in the final result. I think that value must be present at the nth index is num (num = maximumValue in remainder array + 1).

b) Then, created adjacency list of size num for storing all the values from [1, n] after performing mod with num. i.e., 

            vector<int> adjList[num];
            for(int i=1;i<=n;i++){
                int rem = i%num;
                adjList[rem].push_back(i);
            }

c) Then, stored num in result[n]

d) After that, I filled resultant array result from [1, n-1] using the values present in the adjacency list at the remArray[i] position like this:

            for(int i=1;i<=n-1;i++){
                result[i] = adjList[remArray[i]].back();
                adjList[remArray[i]].pop_back();
            }

Step4: Final step is just to print the result[] array.

I tried very hard to understand why my above approach is failing, but couldn't understand. I tried to debug it many times on various test cases, but seems correct solution for me. As this is an interactive problem, I can't take much help from problem test cases too.

Here is my complete code

Kindly help me in resolving this issue. Please help me understanding why my above approach is wrong. Any help will be appreciated. Thanks in advance for your time and efforts. It means a lot to me.

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

Comments Comments (5)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If the correct permutation is $$$P$$$ and the permutation generated by your code is $$$Q$$$, then you are only ensuring that $$$P_i mod P_n=Q_i mod Q_n$$$ for all $$$i$$$. What you need to ensure is that $$$P_imodP_j = Q_imodQ_j$$$ for all $$$i,j$$$.

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

    But I think that problem statement is not much clear about the exact requirements. Problem statement just says:

    We hid from you a permutation p of length n, consisting of the elements from 1 to n. You want to guess it. To do that, you can give us 2 different indices i and j, and we will reply with pi mod pj (remainder of division pi by pj).

    We have enough patience to answer at most 2⋅n queries, so you should fit in this constraint. Can you do it?

    From this statement, I am not much convenienced about what you want to say, because judge was only expecting queries, and it will revert back with the mod answer, So, It's my choice what to ask from judge. I think that my perspective is also correct. What do you think?

    You are saying that: What you need to ensure is that Pi mod Pj = Qi mod Qj for all i,j,

    Can you tell me how have you ensured this?

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

      Basically you need to find the permutation that the jury hid, not just any permutation. Say, the jury hid [3,2,1]. According to your logic, you may output [2,3,1] which would be incorrect.

      Ensuring that $$$P_imodP_j=Q_imodQ_j$$$ is simple. Just note that you can find one element of the permutation in 2 queries. Ask the jury the queries $$$P_imodP_j$$$ and $$$P_jmodP_i$$$.

      If $$$P_imodP_j>P_jmodP_i$$$ then, $$$P_i=P_imodP_j$$$ Otherwise, $$$P_j=P_jmodP_i$$$.

      Since we have uniquely identified the permutation, we have basically ensured that $$$P_imodP_j$$$ is same as the hidden permutation for all $$$i,j$$$.

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

        Thanks for the explanation, I already understand the editorial and your solution. Just tell me one last thing. You said that:

        What you need to ensure is that Pi mod Pj = Qi mod Qj for all i,j,

        I just want to know how can you say that we need to find such solution which is valid for all i, j. Where is it written to find valid solution for all i, j.

        I mean that it is not written anywhere in the problem statement that the solution must be valid for all i, j. Then, why are we worried for all i, j?

        Note: Please don't mind I'm keep asking question from you, I'm just little bit confused about the problem statement, that's why keep asking. BTW, I really appreciate your time and support. Just answer one last above question and then we are good to go.

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

          This is because you need to find the permutation that the jury has hidden.

          → Reply