Hi there,

I hope you all are doing very good. Today, I had a discussion with my friend. He was asked below mathematical problem in his SDE interview by the technical team. But, he was not able to come up with any solution of that problem. Later, when he discussed that with me. I think I was able to solve 1st part of the problem, but I too got stuck on the 2nd part. So, Kindly help us in understanding what should be the solution of the 2nd part of the below problem.

Problem:

Given P = A*B*C, where A = 3y, B = 2y+1, and C = 2^y

Also, some value K is given, which is fixed. And, it is obvious that for all y>0, value of P will increase. So, we need to answer two parts:

• (i) Find the minimum value of y such that P>=K in O(logK) time.
• (ii) Find the minimum value of y such that P>=K in O(log(logK)) time.

My Solution of 1st part: Since for all y>0, value of P is increasing. So, we can apply binary search here. We will start range of y from 1 to infinity, and we will check if P>=K holds or not, for a particular value of y. In this way, we can find minimum value of y which satisfy the given property.

My views on 2nd part: If we further explore value of P like this:

• P = A * B * C
• P = A * B * (2^y)
• P/(AB) = 2^y // got stuck here

Here, at this step, I think if we apply log on both sides, something useful can come out. But, not able to solve it further. I'm not sure about this approach whether it is correct or not, but still tried hard to come up with the solution. But I couldn't solve. So, if possible, Please help me.

Anyone can suggest a solution for the same ? Any help will be appreciated. Thanks (in advance) for your time and support.

Hi there,

I hope you all are doing well. I recently solved this problem: Problem Link

But while solving this problem, I faced a weird issue. Although, I am able to solve this problem using Map STL in C++, but same solution with unordered_map is not getting accepted. Not understanding why is this happening.

I thought to notice the time difference in execution after switching from map to unordered_map. But faced weird WA verdict. My unordered_map solution is giving WA verdict on test case 2 (on test input 3rd), But it is working fine on both my C++ editor and on online editors too on the same test case. This is STRANGE for me.

Solution 1 (using map STL): https://codeforces.net/contest/1598/submission/155784539 (Accepted)

Solution 2 (using unordered_map STL): https://codeforces.net/contest/1598/submission/155784670 (WA verdict)

Note: Solution2 is completely same as Solution1 except I changed map STL to unordered_map STL.

Now, I am not able to understand what is the issue with my code. Why am I getting WA verdict on test case 2 (on test input 3rd)?

Kindly help me in resolving and understanding this issue. Any help will be appreciated. Thanks in advance for your time and efforts. It means a lot to me.

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.

int main(){
    int n;
    cin>>n;

    vector<int> result(n+1, 0);
    vector<int> remArray(n, 0);
    int query = 2*n;

    int index = 1;
    while(query--){
        cout << "? " << index << " " << n << endl;
        int modVal;
        cin>>modVal;
        cout.flush();
        if(modVal == -1){
            return 0;
        }
        remArray[index] = modVal;
        index++;
        if(index == n){
            int maxVal = *max_element(all(remArray));
            int num = maxVal+1;
            vector<int> adjList[num];
            for(int i=1;i<=n;i++){
                int rem = i%num;
                adjList[rem].push_back(i);
            }
            result[n] = num;
            for(int i=1;i<=n-1;i++){
                result[i] = adjList[remArray[i]].back();
                adjList[remArray[i]].pop_back();
            }
            cout << "! ";
            for(int i=1;i<=n;i++){
                cout << result[i] << " ";
            }
            cout << endl;
            return 0;
        }
    }
}

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.

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.

int main(){
    int n;
    cin>>n;

    vector<int> result(n+1, 0);
    vector<int> remArray(n, 0);
    int query = 2*n;

    int index = 1;
    while(query--){
        cout << "? " << index << " " << n << endl;
        int modVal;
        cin>>modVal;
        cout.flush();
        if(modVal == -1){
            return 0;
        }
        remArray[index] = modVal;
        index++;
        if(index == n){
            int maxVal = *max_element(all(remArray));
            int num = maxVal+1;
            vector<int> adjList[num];
            for(int i=1;i<=n;i++){
                int rem = i%num;
                adjList[rem].push_back(i);
            }
            result[n] = num;
            for(int i=1;i<=n-1;i++){
                result[i] = adjList[remArray[i]].back();
                adjList[remArray[i]].pop_back();
            }
            cout << "! ";
            for(int i=1;i<=n;i++){
                cout << result[i] << " ";
            }
            cout << endl;
            return 0;
        }
    }
}

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.

Hi,

Yesterday, I had a technical interview round with Amazon Team. In this round, I asked to solve one famous DP problem with some modifications.

Problem Statement: Given three strings S, x, and y. You have to return interweaving positions of x and y in S with noise symbol positions (which are not part of x and y). Output format will be like this: [S1, S2, S3] where S1 = interweaving positions of string x in S, S2 = interweaving positions of string y in S, S3 = remaining characters (which is noise) positions.

We say that a string S is an interweaving of x and y if its symbols can be partitioned into two (not necessarily contiguous) subsequence s' and s'' so that s' is a repetition of x and s'' is a repetition of y. There might be some noise in S as well.

Look at the test cases for better understandings:

Test Case 1: Input: S = "101010101010101", x = "101", y = "010".
Output: Here, S is an interweaving of x and y, [101|010|101|010|101].
So, we need to return [{1,2,3|7,8,9|13,14,15}, {4,5,6|10,11,12}, {}]. Here 3rd set S3 is empty because there is no noise in S.

Test Case 2: Input: S = "000000010101010101010111", x = "101", y = "010".
Output: Here, also, S is an interweaving of x and y, ignoring leading noise and trailing noise [000000|010|101|010|101|010|111].
So, we need to return [{10,11,12|16,17,18}, {7,8,9|13,14,15|19,20,21}, {1,2,3,4,5,6,22,23,24}]

Test Case 3: Input: S = "100110011001", x = "101", y = "010".
Output: Here, also, S is an interweaving of x and y, [{1,2,4 | 9,11,12}, {3,5,6 | 7,8,10}, {}]

Note: You can ignore | symbol if you want. I couldn't come out with a solution. I know that simple DP problem which contains only x and y in S (without any noise, and |x|+|y| = |S|), but couldn't solve this problem.

Anyone can suggest a solution for the same ? Any help will be appreciated. Thanks in advance.

Hello,

I am solving below problem, and I wrote a solution for the same. I can't understand on which test case or why/where it is giving runtime error. I tried very hard to debug this, but could not understand. I checked other's accepted solution for getting a test case on which my solution could fail, but still couldn't get such test case. Can someone please help me with this ? Any help will be appreciated. Thanks in advance.

Problem Link: https://codeforces.net/problemset/problem/1551/C

My solution: https://codeforces.net/contest/1551/submission/124854239 ( giving run time error on test case #2 )

Note: Also, please don't downvote if you can't help, I really tried very hard to debug my code.

UPD: I caught the issue, it is inside my comparator function. Never mind. Thanks

Hello,

I am solving below problem and I have already solved this problem using DFS, but then I tried to solve it using BFS too. I know that below problem can be solved using both BFS and DFS.

I have written a solution using BFS, but my solution is failing at #19 test case (not complete visible test case). I tried hard to debug my code, but can't understand where is the problem in my code. I checked many BFS solutions for this problem, but none of the solution could help me resolving issue in my code. Can someone please help me with this ? Any help will be appreciated. Thanks in advance.

Problem Link: https://codeforces.net/contest/510/problem/B

My Solution Link: https://codeforces.net/contest/510/submission/124016916 ( This solution is failing at #19 test case)

Dear community,

I hope you all are doing good and safe. I just want to know one thing. Recently I had a interview and the interviewer asked one question, how to solve inversion count problem.

I suggested two approaches to him (1. brute force, and 2. using merge sort). He was completely satisfied by my both the approaches.

But at last, he asked one question to me. Can we solve inversion count problem in O(n+k) where n <= k <= (n*n) ?

I couldn't suggest such approach to him. Also, my bad luck, I couldn't ask him about such approach. But, I am just curious to know is this really possible ? Can someone suggest some approach which could solve inversion count problem in O(n+k) where n <= k <= (n*n) ?

Thanks.

I was trying to solve a problem, but I encountered a weird error. I don't know why my code is giving me wrong output. Can someone help me what is wrong in my code ? Thanks in advance.

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

int main()
{
   int n,m;
   cin>>n>>m;
   
   map<string,int> mp1,mp2;
   
   for(int i=0;i<n;i++)
   {
      string s;
      cin>>s;
      mp1[s]++;
   }
   
   vector<string> common;
   for(int i=0;i<m;i++)
   {
      string s;
      cin>>s;
      if(mp1[s]!=0)                // line 1
         common.emplace_back(s);      // line 2
      mp2[s]++;
   }
   
   int len1 = (int)mp1.size();
   int len2 = (int)mp2.size();
   
   cout<<"len1 = "<<len1<<" , len2 = "<<len2<<"\n";
   
}

If I am giving this input :

1 2
abc
cdf
edf

then my code is giving me this output : len1 = 2 , len2 = 2 ( while len1 must be 1 )

Note : If I am removing that common string checking part — these two lines ( line1 and line2 ) from 2nd for loop, then it is giving me correct output as len1 = 1 , len2 = 2

Please help me.

Why this ( https://codeforces.net/profile/V--o_o--V ) profile is not available in top 10 rated users at codeforces ?