### sajalhsn13's blog

By sajalhsn13, history, 3 years ago, Recently I have solved this problem and here is my solution:

int n, target;
vector<int> values;
vector<tuple<int, int, int>> paired_sums;

int main() {
cin >> n >> target;
values.resize(n);
for(int &v: values) {
scanf("%d", &v);
}
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
paired_sums.push_back(make_tuple(values[i] + values[j], i, j));
}
}
sort(paired_sums.begin(), paired_sums.end());
int lo = 0, hi = paired_sums.size() - 1;
while(lo < hi) {
int lo_value, lo_i, lo_j;
int hi_value, hi_i, hi_j;
tie(lo_value, lo_i, lo_j) = paired_sums[lo];
tie(hi_value, hi_i, hi_j) = paired_sums[hi];
if(1LL * lo_value + hi_value > target) {
hi--;
}
else if(1LL * lo_value + hi_value < target) {
lo++;
}
else {
set<int> indexs;
indexs.insert(lo_i);
indexs.insert(lo_j);
indexs.insert(hi_i);
indexs.insert(hi_j);
if(indexs.size() != 4) {
break;
}
else {
printf("%d %d %d %d", ++lo_i, ++lo_j, ++hi_i, ++hi_j);
exit(0);
}
}
}
printf("IMPOSSIBLE");
}


After solving this I have come to realize that my code might not pass one test case. Suppose this paired_sums vector has some values ***** 2 3 3 4 **** (here * means other values). the target value is 6. so 2 + 4 is a potential answer. But if their indexes are not unique my code will say IMPOSSIBLE (breaks from the while loop). however, 3 + 3 is also and a potential answer and if the there indexes are unique my code will fail. But this code is accepted. I wonder how!!! Can anyone explain? Thanks in advance.

By sajalhsn13, history, 5 years ago, Hello everyone,

I am trying to solve this problem. If I can build the LCP array with O(n) complexity I can easily solve it. But building LCP array requires suffix array. I know the O(n*logn*longn) algorithm. But It will give me TLE in this problem. I need the O(n) algorithm to build suffix array. I searched for it and get a paper which is too complex to understand for me. Can anyone give me a simple and well explained tutorial to build suffix array with O(n) time? It will be great help for me.

Thank you.

By sajalhsn13, history, 5 years ago, Hello Everyone,

It was known to me that lookup time in unordered_map is faster than map in C++. When I have to lookup frequent than insertion I should use unordered_map. In this problem I used unordered_map because in my implementation lookup is more frequent than insertion. But I got TLE. In my implementation with map I got accepted. what is wrong here? Any explanation will be helpful.

Thank you.

By sajalhsn13, history, 6 years ago, I am trying to solve this problem. There is a tutorial but for me its not so clear. You can see that I am green. For me the state is [numberOfProgrammer][numberOfLine][maxBug] which is 500*500*500. The tutorial has a solution with state 2*500*500. It is very hard for me to understand the state elimination. Someone please explain the solution so that I(as a green) can understand.

By sajalhsn13, history, 6 years ago, Hello,

I am trying to solve this problem and getting TLE, and I think my code is the best thing I can do. Please help me solve the problem by any efficient idea or optimizing my code:

#include <bits/stdc++.h>

using namespace std;

#define MX 5000005
#define M 100000007
#define LL long long
#define dbg(x) cout<<#x<<" = "<<x<<"\n"

int n;
LL cnt[MX];
int b[MX];

int main(){
while(cin>>n){
if(n==0) break;
memset(b,0,sizeof(b));
for(int i=n,v=1;i>1;i--,v++){
cnt[i]=v;
}
for(int i=2;i<=n;i++){
if(b[i]==0){
for(int j=i*2;j<=n;j+=i){
b[j]=1;
int t=j;
int div=0;
while(t%i==0){
div++;
t/=i;
}
cnt[i]+=cnt[j]*div;
}
}
}
LL ans=1;
for(int i=2;i<=n;i++){
if(b[i]==0){
ans=(ans*(cnt[i]+1))%M;
}
}
printf("%lld\n",ans);
}
}

By sajalhsn13, history, 6 years ago, i don't know what is wrong with my idea. I tried many times but still wrong answer. can anyone tell me what is wrong?

By sajalhsn13, history, 7 years ago, KQUERY

How can i optimize my code?

#include <bits/stdc++.h>

using namespace std;

int n, m, a;
int bs;
vector<int> block;

int sqrtDecomposition(int l, int r, int v){
if(l / bs == r / bs){
int cnt = 0;
for(int i = l; i <= r; i++){
if(a[i] > v) cnt++;
}
return cnt;
}

int cnt = 0;
for(int i = l; i / bs == l / bs; i++){
if(a[i] > v) cnt++;
}
for(int i = r; r / bs == i / bs; i--){
if(a[i] > v) cnt++;
}
for(int i = l / bs + 1; i < r / bs; i++){
cnt += (block[i].end() - upper_bound(block[i].begin(), block[i].end(), v));
}
return cnt;
}

int main(){
cin >> n;
for(int i = 0; i < n; i++){
scanf("%d", a + i);
}
bs = sqrt(n);
for(int i = 0; i < n; i++){
block[i/bs].push_back(a[i]);
}
for(int i = 0; i < 300; i++){
sort(block[i].begin(), block[i].end());
}
cin >> m;
for(int i = 0; i < m; i++){
int l, r, v;
scanf("%d %d %d", &l, &r, &v);
l--; r--;
int ans = sqrtDecomposition(l, r, v);
printf("%d\n", ans);
}
}