Greetings from Dot Slash Community!
!
Dot Slash Community is back with another contest 
. So tighten your seat belts and be prepared 
with your skillset ‘Coz it’s high time for Fall For Code 3.0 where the champions will thrive but only a few will survive.
Setters:,@saurabhshadow,@cherry0697,@vivek9719,@hazardous120,@abhijeet010304,@sarthak_eddy.
Testers: @aert,@sauravsgrl,@parthw1,@huzaifa06,@fyter_112.
Contest link:- Contest link
Date:- 1st Feb 2020
Time:- 21:30 - 23:30 IST
Contest duration:- 2 hrs⏳
Number of questions:- 6(of varying difficulty)
Prizes:- Top 3 global winners will get 250 Codechef ladoos.
Meanwhile, you can have a look at our previous contest, Fall For Code 2.0.
Contact us: dotslash.communityiiitn@gmail.com or (+91) 9554630599 (Saurabh Yadav)
8 Likes
@hazardous120
Find Duplicates problem. Does it have too tight constraints ? or the time hasn’t been multiplied with appropriate factor for other languages ? I see all python submissions getting TLE. using same concept of segment tree with map having freq count at each node. O(26*nlogn)
Code. Since the contest has ended, I don’t know if anything can be done now, but if it can be done, please add suitable multipliers for other languages.
Why is my code giving TLE even when i’m using binary search
#include<iostream>
#include<bits/stdc++.h>
#define int long long
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
int32_t main()
{
fast;
string s;
cin >> s;
int n = s.size();
map<int,set<int>>v;
for(int i = 0 ; i < n ; i++ ){
v[s[i]-'a'].insert(i+1);
}
int q,type,l,r,pos;
char val;
cin >> q;
while(q--)
{
cin >> type;
if(type==1)
{
cin >> pos >> val;
v[val-'a'].insert(pos);
v[s[pos-1]-'a'].erase(pos);
s[pos-1]=val;
}
else
{
cin >> l >> r;
int c = 0;
for(int i = 0 ; i < 26 ; i++ )
{
if(v[i].size()>1){
set<int>::iterator it = lower_bound(v[i].begin(),v[i].end(),l);
if(it==v[i].end()){
continue;
}
int k = *it;
++it;
if(it==v[i].end()){
continue;
}
int k1 = *it;
if((k>=l && k<=r) && (k1>=l && k1<=r)){
c++;
}
}
}
cout<<c<<'\n';
}
}
}
1 Like
There is some problem with constraints/time-limit of this problem as pointed out by @anon31329220 and @harshraj22 . Segment-tree/binary-search times out. Only Fenwick gives AC. Weird 
2 Likes
and policy based data structures also gives right answer
2 Likes
Have you ever wondered despite having std::lower_bound in algorithms library, why std::set has a method lower_bound ? Read here, std::lower_bound is not O(logn) for tree based containers like set. It is rather linear. So your solution doesn’t uses binary search anymore ( the lower_bound part becomes linear).
Oooooohhh!! Got it bro !! . So , lower_bound works efficiently in case of vectors and arrays right !
2 Likes
@harshraj22
https://www.codechef.com/viewsolution/29292094
https://www.codechef.com/viewsolution/29292068
I submitted two solutions using set.lower_bound() . The first one gave me correct answer while the second one didn’t . The only difference in code is the order of operation . In first solution , in type1 query , i performed insert operation first and then erase operation . In second solution , i performed it vice versa . How is this effecting my solution ?
