shanto_bangladesh's blog

By shanto_bangladesh, history, 22 months ago, In English

After solving this problem, I looked to some of other's code. In several codes, I found something like this (not exactly this, it's a simplified version of that):

int n = 10; 
for(int i = 1; i<=n; i+=i& - i;)
{
cout << i << " ";
}
 

Output: 1 2 4 8

I also tried for different values of n and the program outputs powers of 2 less than or equal to n.

But how is it working? What's exactly meant by i+=i&-i ?

Thanks for your patience and insight.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By shanto_bangladesh, history, 22 months ago, In English

In last Div. 4 contest, my solution for problem Problem F received TLE verdict in testcase 18 during the system test. Later on I found that, changing unordered_map to map works fine to achieve Accepted verdict.

Code:

void solve()
{   
 
int n, k; cin >> n >> k ; 
vi g; 
unordered_map<int, int> m; 
for(int i = 0; i<n; i++)
{
  int a; cin >> a; 
  m[a]++; 
}
 
for(auto &x: m)
{
  if(x.second>=k) 
  {
      g.pb(x.first); 
  }
}
 
if(g.size()==0) { cout << -1 << "\n"; return; }
 
 
Asort(g); 
 
int l = 0, r = -1, cl = g[0]; 
  n = g.size(); 
  for(int i = 1; i<n; i++)
  {
      if(g[i] - g[i-1]>1)
      {
        if(r - l <= g[i-1] - cl)
        {
          r = g[i-1]; 
          l = cl; 
        }
 
        cl = g[i]; 
      }
  }
 
 if(g[n-1] - cl >= r - l )
    {
      r = g[n-1]; l = cl; 
    }
 
    cout << l << " " << r << '\n'; 
 
}
 

So far I know, when we do not need the elements to be ordered, we should use unordered_map which is the case in this problem. So why std::map works better than std::unordered_map in terms of time complexity?

Thanks for your patience!

Full text and comments »

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

By shanto_bangladesh, history, 23 months ago, In English

I tried to solve the following interactive problem: Problem link

Please focus in the main() function:

bool testcase =          0               ;
void solve()
{   
int hi = 1000000, lo = 1, mid;
    string s; 
    while(lo+1<hi)
    {
        mid = (lo+hi)/2;
        cout << mid << "\n";
        fflush(stdout);
        cin >> s;
        if(s[0]=='<') { hi = mid-1; }
        else { lo = mid; }
    }
    cout << hi << "\n";
    fflush(stdout);
    cin >> s;
    if(s[0]=='>') cout << "! " << hi << "\n";
    else cout << "! " << lo << "\n";
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
   int t = 1; 
   if(testcase == true)
   {
  cin >> t;
   }
    while(t--)
   {
       solve();
   }
} 

When I ran the above piece of code in Visual Studio code terminal it didn't produce any output. Then I deleted those 2 lines in the main function.

  ios_base::sync_with_stdio(0);
    cin.tie(0);

Then it ran nicely producing desired output. Why it didn't work with those 2 lines of code?

Any insight will help a lot. Thanks for your patience.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By shanto_bangladesh, history, 2 years ago, In English

I tried to find the index of the upper_bound of an integer in a set.

set<int> s = {1,2,3,4,5};
int ind = s.upper_bound(2) - s.begin();
cout << ind << "\n";

But it's showing error. I did similar thing with vectors previously. Code looks like the following:

vector<int> v = {1,2,3,4,5};
int ind = upper_bound(v.begin(), v.end(), 2) - v.begin();
cout << ind << "\n;

The above code nicely executes the desired task. Why it's not working for set and multiset and what to do if we want to do the same task with a set or multiset without traversing the whole set?

Thanks for your patience!

Full text and comments »

By shanto_bangladesh, history, 2 years ago, In English

Among the features of Codeforces, one of which I don't understand is the rank table. But I'm not getting any suitable source to learn about those stuffs. Today I'm here to the community with my query. Notice the segment of the standings given below:

Click here...

Question 1: What is meant by the section penalty? I'm also curious to know how this number is calculated.

Question 2: What is meant by the + sign and the number written just below ( colored green) ?

Thanks for having patience to read this blog. I'll really appreciate your help.

Full text and comments »

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

By shanto_bangladesh, history, 2 years ago, In English

One of the feature of Codeforces I really wonder about is how the difficulty level of a problem is determined? Is it by any mathematical calculation, or manual estimation? Why the tags of a problem is not published just after the contest? Thanks for reading this blog. I will really appreciate your helps and insights.

Full text and comments »

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

By shanto_bangladesh, history, 2 years ago, In English

As a new user of codeforces, I'm really curious to know about the rating system. Any insight on this topic will help a lot. Thanks in advance.

Full text and comments »