Codeforcer's blog

By Codeforcer, history, 34 hours ago, In English

I was going through multiple blogs on Djikstra recently, viz Graph Modelling, K path skip and Eppstein algorithm. I came across many interesting problems which were just not possible for me to solve without prior knowledge of these concepts. I am still struggling to do these problems (at a rate of 1 per day). Came across some ingenious yet elegant problems as well. I would love to know more on the type of patterns that Djikstra can solve and if you guys know any cool tricks or problems like the one above.

Thanks!

Full text and comments »

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

By Codeforcer, history, 3 years ago, In English

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!

Thanks for reading !

Full text and comments »

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

By Codeforcer, history, 3 years ago, In English

I was attempting this problem :

https://codeforces.me/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!

Full text and comments »

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

By Codeforcer, history, 3 years ago, In English

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});
}

Full text and comments »

  • Vote: I like it
  • -25
  • Vote: I do not like it

By Codeforcer, history, 3 years ago, In English

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!

Full text and comments »

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

By Codeforcer, history, 4 years ago, In English

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.

Problem : https://codeforces.me/contest/1466/problem/E

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!

Full text and comments »

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

By Codeforcer, history, 4 years ago, In English

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://codeforces.me/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!

Full text and comments »

  • Vote: I like it
  • -7
  • Vote: I do not like it

By Codeforcer, history, 4 years ago, In English

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

Problem Link : https://codeforces.me/contest/1251/problem/C

Code

Thanks!

Full text and comments »

  • Vote: I like it
  • -1
  • Vote: I do not like it

By Codeforcer, history, 4 years ago, In English

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 :

Screenshot-106
No way am using geogebra for this

Apologize for the sketchy figure though.

Full text and comments »

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

By Codeforcer, history, 4 years ago, In English

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?

Full text and comments »

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

By Codeforcer, history, 4 years ago, In English

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

Full text and comments »

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