Can anyone help me solve this problem. I have no idea how to do it. I thing its subarray problem. link

Before contest

Codeforces Round sponsored by NEAR (Div. 1 + Div. 2)

2 days

Register now »

Codeforces Round sponsored by NEAR (Div. 1 + Div. 2)

2 days

Register now »

*has extra registration

# | User | Rating |
---|---|---|

1 | tourist | 3803 |

2 | jiangly | 3707 |

3 | Benq | 3627 |

4 | ecnerwala | 3584 |

5 | orzdevinwang | 3573 |

6 | Geothermal | 3569 |

6 | cnnfls_csy | 3569 |

8 | Radewoosh | 3542 |

9 | jqdai0815 | 3532 |

10 | gyh20 | 3447 |

# | User | Contrib. |
---|---|---|

1 | awoo | 162 |

2 | maomao90 | 160 |

3 | adamant | 157 |

4 | maroonrk | 154 |

5 | -is-this-fft- | 149 |

6 | Petr | 148 |

6 | SecondThread | 148 |

8 | atcoder_official | 147 |

9 | TheScrasse | 145 |

9 | nor | 145 |

I was trying this question

and for some reason that i dont understand my code doesn't work that is following.

```
int rec(int n, vector<int>&v){
if(n == 0){
return 1;
}
if(v[n] != -1){
return v[n];
}
return v[n] = rec(floor(n/2),v) + rec(floor(n/3),v);
}
void solve() {
read(n);
vector<int>v(n+1,-1);
cout<<rec(n,v)<<endl;
}
```

but the following code which has the same logic works.

```
map<ll, ll> mp;
ll calc(ll x) {
if (x == 0)return 1;
if (mp.find(x) != mp.end())return mp[x];
ll res = calc(x / 2) + calc(x / 3);
return mp[x] = res;
}
void solve() {
ll n; cin >> n;
cout << calc(n) << "\n";
}
```

I was trying to the this question and during that, I used the following code.

```
void solve() {
read(n); read(x);
map<int,int>mp;
for(int i = 0; i< n; i++){
int a; cin>>a;
if(mp.find(a) != mp.end()){
int b = mp[a]+1;
cout<<b<<" "<<i+1<<endl;
return;
}
else{
mp[x-a] = i;
}
}
cout<<"IMPOSSIBLE"<<endl;
}
```

this did not give any tle error but when i used the following code

```
void solve() {
read(n); read(x);
unordered_map<int,int>mp;
for(int i = 0; i< n; i++){
int a; cin>>a;
if(mp.find(a) != mp.end()){
int b = mp[a]+1;
cout<<b<<" "<<i+1<<endl;
return;
}
else{
mp[x-a] = i;
}
}
cout<<"IMPOSSIBLE"<<endl;
}
```

it was giving tle in the test cases 23 and 24. now I know that both of them are the same except for the use of data structure, but the map should be slower than unordered_map but the opposite is true, why is this happening can anyone explain?

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/16/2024 11:58:48 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|