### Codeforcer's blog

By Codeforcer, history, 3 years ago,

Recently I solved this problem. Upon first reading this and before solving it, I thought of many other possible approaches like which would either TLE/MLE. One of them being to maintain a dp; Until I finally realized the retroactiveness the question demands. If you look at it closely it is the same as this task. Now I have a few "questions" on how to solve a more general version of it if...

1 The A was variable i.e. we are also given an array each having some A[i] with atmost one drink per day.

2 Instead of atmost 1 drink per day, We are allowed to choose any number of drinks per day with given A[i]'s

If you have any thoughts or ideas on this one please make sure to share. As for me, it is the first time I have seen such variations in such a problem with these constraints. Also can we even solve it in some efficient complexity ? I am very eager to know.

P.S I have used bugaboo, task, problem and question so that no one feels hurt!

• -13

By Codeforcer, history, 3 years ago,

I was attempting this problem :

https://mirror.codeforces.com/contest/706/problem/D

I tried using trie and it gives TLE. I saw solutions of other people but most of them have created a TRIE by using struct and pointers. I have done it using a 2d next array following the idea from Errichto topic video of trie. I cant figure out why there is TLE, maybe because of map ? Any help would be appreciated.

Here is my code :

D

UPD Got accepted!

Thanks!

• 0

By Codeforcer, history, 3 years ago,

When I try to use find by order using pairs in ordered_set of pbds it shows some error of no matching call as such. So how do I resolve it?

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll  long long
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define pi pair<int,int>
#define REP(i,n) for(int i=0;i<n;i++)
const int N = 2e5+2;
const ll mod = 1e9+7;
using namespace __gnu_pbds;

typedef tree<pi, null_type, less_equal<pi>, rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

ordered_set ord_set;

int main(){
int a;
cin >> a;
ord_set.insert({a,-1});
*ord_set.find_by_order(make_pair(a,-1)); //Why does this not work ?
ord_set.order_of_key({a,-1});
}


• -25

By Codeforcer, history, 3 years ago,

I was solving this : https://leetcode.com/problems/minimum-jumps-to-reach-home/ and wrote essentially 2 same solutions, just the way of calculating transitions is a bit different. I get AC in one and RE in the second. I am not getting the reason for such a difference in results. So please help me understand.

One which gives RE
One which gives AC
The difference

As you can see logically both are correct then why the difference ?

Thanks!

• 0

By Codeforcer, history, 3 years ago,

I cannot figure out why this code is getting TLE'd despite of everything being under order and constraint. I knew those mod operations were costly so I optimized them but still no luck.

Code

Update-1 : Resolved, It barely passed(1996 ms) after I changed some ll's to ints. Would still like to hear some advice or a good solution though!

Update-2 : The comments are absolute gold thanks guys! Made the necessary changes and made code more concise.

New Code

GNU C++17(64 bit) -> 453 ms

GNU C++17 ->1263 ms

Would still like to know more on the difference in time on the above 2 compilers.

Thanks!

• +7

By Codeforcer, history, 3 years ago,

Why do some solutions containing dp with memoization result in TLE but the same iterative version always passes? I have had this doubt for quite a while.

For example this problem : https://mirror.codeforces.com/contest/628/problem/D

DP+Memo->TLE

Checking the editorial they have done the same thing just iterative.

So my questions are this :

->What should be a good practice to write dp memoized or iterative?

->Can every memoized dp problem be converted to iterative ?

->What exactly goes wrong with memoized versions getting TLE'd ?

->How to resolve such TLE's ?

Thanks!

• -7

By Codeforcer, history, 3 years ago,

I cant figure out reason for TLE, code seems to be O(n) with some small constants, any help would be appreciated.

Code

Thanks!

• -1

By Codeforcer, history, 4 years ago,

So I was thinking of making some div2B/C level CP problems for my school contest and thought of this....

Here it goes....

Find the maximum number of squares of side length 'a' that can completely be inscribed in a circle of radius 'r' such that exactly one of the vertices of the square touches the circle and no 2 squares overlap each other. Note that all the squares have to be completely inside the circle.

I cant figure this out..ended up taking too many variables which I cant eliminate...any thoughts or hints ?

The figure will look something like this :

Apologize for the sketchy figure though.

• +4

By Codeforcer, history, 4 years ago,

I wanted to do a runtime analysis of B. It got AC even though I doubted it as it looked worst case O(n^2). Basically I just simulated what was asked. It is also mentioned in the editorial that simulation would take too much time. I am now really interested in the runtime of my code.

ARC-105_B

Also any ideas on D?

• 0

By Codeforcer, history, 4 years ago,

Why was CF down for a day? Is there some new feature that has been implemented or just maintanance?

• +158