abhinav700's blog

this is my solution for problem E from Codeforces round 731(div3).can anybody tell why it is giving me a wrong output(I have tried dry running all the test cases for my code, but I am not able to find any mistake)
By abhinav700, history, 3 years ago, In English 
#include "bits/stdc++.h"
using namespace std;
 
int main()
{
 long long int q;
 cin>>q;
 while(q--)
 {
     long long int n,k;
     cin>>n>>k;
     vector<long long int> pos(k);
     for(long long int i=1;i<=k;i++)
     {
         cin>>pos[i];
     }
     vector<long long int> temp(k);
     for(long long int i=1;i<=k;i++)
     cin>>temp[i];

    vector<long long int> output(n,1e8);
    
   for(long long int i=1;i<=n;i++)
   {
       for(long long int j=1;j<=k;j++)
       {
           output[i]=min(output[i],temp[j]+abs(pos[j]-i));
       }
   }

    for(long long int i=1;i<=n;i++)
    cout<<output[i]<<" ";

    cout<<endl;
     
 }   
 return 0;
}
  • Vote: I like it
  • -21
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
3 years ago, # |
← Rev. 2   Vote: I like it +7 Vote: I do not like it

There are two issues.

First, the size of your vectors is a bit less. For example, the size of pos is k but you have used indexing from 1 to k (instead of 0 to k-1). To solve this, you can simply assign it a size of k+1. The same holds for other vectors as well.

Second, the initial value in your output vector is just 1e8 which is too little, since the actual answer can go upto 1e9+3e5-1 according to the constraints.

However, even after these fixes, your code won't pass the testcases since currently its time complexity is O(nk).

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

    1)why should we assign it a size of k+1? I thought that we only need k blocks of memory and indexing will only change their numbering 2) I did those changes but still incorrect output for the sample test cases given (It took me a time to realize that it will not get accepted due to time complexity, but shouldn't it atleast give the correct output for sample test cases?)

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

Hey, Abhinav.

I believe you could benefit from watching this.

While Errichto uses bash, you could in principle do the same by just using C++ as well. As a side note — do keep in mind that the rand() function in C++ is sub-par in quality (as far as I've read), you could look for alternatives, maybe make use of this to generate the random numbers.

For finding the erroneous test case — you could just pick some AC-solution for that question, modify it to get a function that returns the answer, compare that answer to the answer generated by your code and print the specific test that resulted in a conflict. A good way to go about it is to generally set the bounds for the random values to be small so that your generator can cover 'different type' of inputs in a short amount of time. Some special generators for large/overflow-inducing values could be tested as well.

I won't get into too much detail though, you can figure out the rest :)

Also, when posting code, try to keep it within spoilers.

for c++, use ```cpp
for java, use ```java

As for learning how to add them, you could refer to this and this.

→ Reply