Comments
On Anshul_Johri → C++ Debug Template!, 3 years ago
0

I have written a blog on using a debugging template quite some time back. You all can have a look at it as well: https://cs-mshah.github.io/getting_started_with_cp/#debugging
+23

Check DMOJ. Here are the docs: DMOJ Documentation
On kompo → IDE for cp, 4 years ago
0

CP Editor, as it automates a lot of stuff. Here is a blog I wrote for a good setup: https://cs-mshah.github.io/posts/getting_started_with_cp/
0

here you are able to print using dbg(..); and can easily see the output in stderr. you can even submit the code without worrying about removing the dbg statements. Its certainly better than using a gdb.
+10

One stop to debug template and its usage:

https://cs-mshah.github.io/getting_started_with_cp/#debugging
+8

Nice blog!
Pretty similar to my blog where I had written about debugging, inputs/outputs and other cool stuff:
getting started with CP
On aryan12 → Bridge Trees [Tutorial], 5 years ago
+7

Amazing blog!

The blog by -is-this-fft- : [Tutorial] The DFS tree and its applications: how I found out I really didn't understand bridges is an amazing blog on bridges.
It has the explanation to the problem: 231E — Cactus which can be solved using the bridge tree approach.

There a small correction too: in the pseudo-code, it should be dfs(next, component_number);
0

It would be nice if you could add more features like time taken for every test case, comparing floats with various precisions, yes/no checker. Basically a few more arguments for more features. Also make the diff checker ignore trailing/leading spaces/newlines.
+1

Here is what I use and found to be the simplest: link to my comment
On andrewtam → Do You Use a Debugger?, 5 years ago
+1

This is what I use: cf comment.
These are my debug flags:
g++ -std=c++1z -D_GLIBCXX_DEBUG -D_GLIBCXX_DEBUG_PEDANTIC -g -fsanitize=undefined
0

what do you mean by propagating? You need to have starred some blogs to see them under favourite blogs. They will appear in a collapsed form.
For all submission, clicking it will get you to that page. By propagating if you mean the background effect on hover(for all submissions), then I don't know why that event didn't get copied, but in some time I can add a custom css similar to what cf has, to simulate the hover with a background.
+4

The idea sounds great! But to do that would be equivalent to designing a new website and there is a site just for this purpose!
codehunt.
Here you need to enter a user. So any user from the standing in problemset can be selected. This might still not cover all problems, but then in that case one can make a bot user and submit a compilation error to every problem, making it perfect for the kind of filter you want and which codehunt supports.
On cip999 → Editorial of Global Round 15, 5 years ago
+49

One of the finest rounds on codeforces. kudos to the problem-setters!
+9

I did an overkill for C. I used an ordered_multiset. Though I feel a bit stupid, I think the template I used is pretty amazing : 122832592.
This would actually be useful in solving a more general problem: lets say instead of predicting in how many minimum moves we can win, the game continues with different scores being added to each and we need to find the move at which our score will be atleast the opponent's. In this case we would require (or atleast this is one way) order statistics on our multiset.

0

Here's a template that can be used for debugging, which supports colours:

Template

The functionality of this is similar to what I've mentioned here: comment
+1

I tried to compile and it threw several errors. Am I missing something?
[edit] fixed : I was not using c++17
+18

I did some research and searched for very good debugging techniques and templates. So this is what I felt is the best method for debugging, and this works for several stl containers including maps and even policy based data structures.

Here is the template:

myprettyprint.hpp

Now, you might be feel that this would make my default template a lot more scary and confusing. So a solution to that is to use the #ifndef ONLINE_JUDGE preprocessor directive, and include the debug template as a .hpp file.

main template

Results:

output

note: the myprettyprint.hpp should be placed in a directory so that it is in the search path when compiling.
in ubuntu, I placed it here: /usr/include/c++/9/myprettyprint.hpp. I hope this helps!

original source: link1, link2

-15

neal
I just wanted to know how should we modify the custom hash so that it works for
unordered_map<ll, vector<ll> >
unordered_map<string, vector<ll> >
unordered_map<pair<ll,ll>, ll >
as these are required in some problems.
+41

Me after reading C:
"I will never play rock paper scissors ever again!"
0

Can someone tell me why my D is wrong? link
Here's a brief description of what I thought —

  1. We know who will be the person to place the token on every square. (in particular the last square).
  2. So I defined 2 dp's — dp1[i][j]: max score(difference of scores) that P1 gets when on (i,j).
    We play the game in a reversed manner.
    dp2[i][j]: max score(difference of scores) that P2 gets when on (i,j).

So the transitions are basically what is the best path to arrive at that square(in reverse). The recurrence and transitions are in the code.

I don't know why this gave WA for 3 test cases. What am I missing?? Is the DP wrong or have I made some mistake in transitions or base cases??
Help would be appreciated
+21

Balajiganapathi can you create an option to give virtuals on codedrills so that those who have missed a practice contest can still give?
+8

The idea is absolutely wonderful. One suggestion: you could add something like folders. So if I have lets say dfs related problems, then I could make a dfs folder and place the notes of those problems in that particular folder.
0

yes this generally should work
0

just recent bad contests. once i cross 1500, hopefully won't dip again
0

Manan_shah
0

Very nice method. Very well explained. Got interesting things to learn.
0

very well explained. I really wish if editorials explain it so well.
On Baba → Indian Programming Camp 2020, 6 years ago
+1

Do we receive an email on registration? Because I don't think I got one.
+3

I_will_come_back you explained really well! I really wish that the editorials are written in great detail so that everyone understands.
0

Problem C of div2 can also be done using binary search on the ans.
Here is my submission 97456070
0

How did you use method 7 in the problem 1? I used the method of difference array and prefix sum.
+3

Currently I am facing this very similar issue, but in my case I am not practicing sufficiently. Also my major weakness is constructive ad-hoc problems. I'll try your method and see if it works. Do tell me if there is anything else I should do
+3

Rachmaninoff piano concerto no.2
This is by a Russian pianist. It is absolutely amazing!
0

I thought of the exact same idea but it gave WA.
check this: https://atcoder.jp/contests/abc178/submissions/16969818
Can you help me to find what is wrong? I think this method isn't right.
0

Generalisation of problem B has already been asked quite recently on atcoder
Here's the link: atcoder ABC 173 E
0

Can you explain the rounding in E. By using simple ceil(a[i]/m), it doesn't work. But in the equation, we have a[i]/m<=ki and we want sum of all ki<=k. How to handle these things as they might occur in different problems.
On RASEL_MEYA → [Two Pointer], 6 years ago
0

I used binary search though
-6

This will be my first time watching a tourist live stream. Am really excited!
0

There are a few suggestions: I wasn't able to see the problems which I did in a mashup in green colour. So you could add a possibility of manually doing it or automate that for gyms. Also you could add a feature to add multiple handles and showing the number of them who did a problem below it, so that we could design mashups for our friends. Something like sorting by lists in codeforces.
+37

Lol I was in bad mood after reading the long statement of C. Missed it by one case
0

I was wondering how to solve D if there were multiple stocks. I think this would be quite hard.

+22

When I was in 9th grade, I independently discovered a link between the pascal's triangle and the fibonacci series:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1

Now if you see diagonally, you will see the fibonacci sequence. It is easy to prove using induction.

On Bur → Quick code typing, 6 years ago
0

You could practice on KTouch if using ubuntu!
-14

YES! upsolving higher rated probs teaches several new concepts. So for learning, +500-700 would be great. You might not be able to solve on your own, but can learn a lot from editorials, others' solns.
0

Wonderful soln. could you just add some comments and send the soln so that I can understand 100%. Mainly what are the first second things and how is the @ thing being checked!
Thanks a lot secundus
0

nice contest!!
0

I really wanted to write a blog on this concept as I was completely shocked by this trick when I solved this problem:
D. Constant Palindrome Sum.
You have done a great job!!
0

i was wondering if it was possible to use a comparator function in B. If someone has done it, please share the solution.

+45

The statement of D was very bad. It took me 15mins to understand.
0

says invalid email
On zeyad_alaa → atcoder knapsack 2, 6 years ago
0 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<long,long> pl;
typedef pair<ll,ll> pll;
typedef vector<long> vl;
typedef vector<bool> vb;
typedef vector<ll> vll;
typedef vector<vl> vvl;
typedef vector<vb> vvb;
typedef vector<vll> vvll;
typedef vector<pll> vpll;
typedef vector<string> vs;

#define FOR(i,a,b) for(long long i=a;i<b;++i)
#define REV(i,a,b) for(long long i=a;i>=b;i--)
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define all(v) v.begin(),v.end()
#define tc ll t;cin>>t;while(t--)
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define coutv(v) for(auto it: (v))cout<<it<<" ";newl;
#define cout2d(v) for(auto it: (v)) {for(auto j:it) cout<<j<<" ";newl;}
#define cinv(v,n) vll (v)(n);FOR(i,0,(n)){cin>>v[i];}
#define cinvg(v,n) (v).resize(n);FOR(i,0,(n)){cin>>v[i];}
#define cin2d(v,n,m) vvll (v)(n,vll(m,0));FOR(i,0,n){FOR(j,0,m){cin>>v[i][j];}}
#define cin2dg(v,n,m) (v).resize(n,vll(m));FOR(i,0,n){FOR(j,0,m){cin>>v[i][j];}}
#define newl cout<<"\n"
#define mod 1000000007
#define INF 1e18

int main()
{
	io;
	ll n,W,V=0,ans=-1;
	cin>>n>>W;
	vll w(n+1),v(n+1);
	FOR(i,1,n+1)
	{
		cin>>w[i]>>v[i];
		V+=v[i];
	}
	
	vvll dp(n+1,vll(V+1,INF));
	dp[0][0]=0;
	FOR(i,0,V+1)
	{
		dp[0][i]=0;
	}
	
	FOR(i,1,n+1)
	{
		FOR(j,1,V+1)
		{
			dp[i][j]=dp[i-1][j];
			if(j-v[i]>=0){dp[i][j]=min(dp[i][j],dp[i-1][j-v[i]]+w[i]);}
		}
	}
	
	REV(i,V,1)
	{
		if(dp[n][i]<=W){ans=max(ans,i);}
	}
	cout<<ans;
	return 0;
}

Can someone tell me what is wrong with this. I am unable to see the initialisation
-48

Haw re baba
0

You dont need comparator function. just use negative value see this 80158855
0

our main idea is to select the leaves but now if we have more to select, we will pick one level above the leaves. So, which ones should we pick? We pick the ones having maximum happiness. Now if we pick one,we know that it will add happiness by the level of that node, but as we have picked all in its subtree before its picking,we need to subtract the number of nodes in its subtree as while travelling up, the current node won't count.
so, finally we just sort all the values(level-no. in subtree)(net happiness which every node would provide)
Hope this helped.
On himanshujaju → 0-1 BFS [Tutorial], 6 years ago
0

TIMUS-Ivan's Car
This is a very good problem on 0-1 bfs and modification.
0 
void dijk(ll p)
{
	//vector<ll> dist(n,INF);//out
	priority_queue<pll,vpll,greater<pll>> q;
	dist[p]=0;
	q.push({0,p});
	while(!q.empty())
	{
		ll a=q.top().S,d=q.top().F;
		q.pop();
		if(-d!=dist[a]){continue;}//checking visited
 
		for(auto v: g[a])
		{
			ll b=v.F,w=v.S;
			if(dist[a]+w<dist[b])
			{
				dist[b]=dist[a]+w;
				par[b]=a;
				q.push({dist[b],b});
			}
		}
	}
}


I think this is the simplest implementation and it also reduces space as there is no need to keep a visited array.

0

actually my solution is the same as the editorial. 76863601
The cnt is maintaining the no. of nodes in the subtree of a node including that node. Our approach would be to select the leaves, but if the value of k is greater than that, then we need to select other nodes that are at levels above the leaves and contribute to happiness.
A crucial observation is that when a node is selected, it would decrease the happiness of all the other which are in the subtree. And as we have selected the nodes in the subtree already, the happiness would increase by the depth(level)-nodes in subree.
So we sort the array of level-no. in subtree and select the largest k.

I noticed that I could have computed level by dfs also as presented in the editorial. I had the bfs approach in mind first and then I noticed that it isn't the only thing so I had to use dfs.

0

For competitive companion, go to chrome extensions and add it. Set the port to 10045 in extension options of competitive companion.

For CF Tool, download latest zip and extract. Now move the file to the PATH by typing sudo mv cf ~/usr/bin on the terminal. Be sure to be in the directory of cf by cd.
Now in the terminal, type cf config, 0: to login, 1:add template.
In template, after selecting the language,just enter the path to your default code. just type the other suffixes, press enter in the optional stuff and write the path to your .exe or a.out of your default code.

after this u are good to go and submit through CP EDITOR!!
Feel free to ask and do upvote!
+1

What Floyd Warshal does in every iteration is that it picks a vertex and for all pairs of points,it updates the shortest distance between them passing through the iteration point and thus after all iteration, the adjacency matrix will have the min distance between i,j.

In our problem,we only have one other edge i.e x,y so, instead of taking iterations over all points, we only consider them through that edge and the main path. Thus,we only have 2 loops and one statement inside them instead of the third loop.
I hope this helped.
+2

For D, we can use Floyd Warshal with a little modification.
https://atcoder.jp/contests/abc160/submissions/11317101
E can be done with a greedy approach.
https://atcoder.jp/contests/abc160/submissions/11318492
0

K is a t max 2*10^9. So n would be < 2*sqrt(2*10^9) which is approximately 89000. And as we had n*(n-1), i took 8*10^5 in the estimate. You could have put a higher value.

+2

I have a different approach for B.
We know that after n*(n-1)/2 permutations, both b's will be together. So we can basically make an array of all such numbers (1,3,6,10,..),and for a given k, we can find an n s.t n*(n-1)/2<=k (by binary search). Let j be the pos of that n. We can clearly see that for this value the no. of a's after the 2 b's will be exactly j (i.e, we can determine that particular permutation).
So, from that permutation, we can lexicographically check next permutations till we reach k and print that kth permutation.

C++ soln:74461692

On mohabamr → Recommender, 7 years ago
0

It says something went wrong
On HosseinYousefi → C++ Tricks, 7 years ago
0

Another useful thing would be to precompile the <bits/stdc++.h> header to reduce the compilation time. Just compile it as you normally compile in the folder having that file. The compiled file would have a .gch extension.
+4

Thank you for the wonderful contest. I really liked problem C of div2. The trick was to see what the operation is exactly doing!

0

Happy valentine's day in advance everyone!!
+13

Thank You very much for the problems.Learnt to think for basic things first in easy problems rather than taking cases and complicating.
On ChaosAngel → XYZForces, 7 years ago
-34

why are there so many down votes? This hampers my contribution. Pls up vote.

On ChaosAngel → XYZForces, 7 years ago
+3

div3VovuhForces
On ChaosAngel → XYZForces, 7 years ago
+4

basecaseforces,WAforces
0

yep even i have done something very similar. 69899087.
0

here is my submission:69550598. I ran bfs once and stored the parents and the no.of direct children for every node. Then,i made a queue and a counter j. the no. extracted from the queue is the current parent. so i check the next children no. of nodes in the input from j. if any of them does not have p as its parent,it would not have been added by any way of dfs traversal and thus we answer No. If it is a child then add it to the queue. If the loop runs successfully,we increment j by the no. of children so that we can check for the children of the next parent. I hope this explains my code.
+3

nice explanation. Thank You
+1

Can you add support for competitive companion so that we can automatically run the test cases. You could also add a submit soln button using cf tools.
0

Is there a problem with indentation as whenever I open the braces and press enter, the cursor does not indent after the braces and I have to press tab. This does not happen once but for every statement, I need to use tab for proper indentation. Also,it would be great if there was a feature for autocomplete

0

How would we solve the problem C if an additional condition of k members in a team is imposed
0

I actually got it by using sudo and then pasting in /usr/bin
0

It says permission denied when i try to move it to /usr/bin even when i have allowed the execution as a program
0

yep...thanks,it worked
+1

why does this 68940816 for prob A fail on test 50! I have used the values of x that would give minimum.
0

It gives an error-unable to access jarfile Hightail. Can You please give a detailed procedure to use hightail after downloading and extracting the zip file. It would be highly appreciated if you make a video. Thank You
0

if dp[i]=min cost to buy first I items,how is it that that is the optimal way to buy max no. of items? I understood your dp, but I would like to have a proof. My dp is quite poor.
0

my one also got accepted with ifs now 68356480 THANKS
0

yeah,sorry for the complexity,but what should i do to optimise then?should i write using ifs?
0

even i am getting TLE on test case 10 for 68349376
0

for problem B, why does 68349376 give TLE inspite of being n^2logn?
0

looks very cool!!
0

Ok i kind of got it now
0

can please you explain 1a & 1b a bit more clearly and what about going to the left? thanks for your kind help
0

Please explain D,i still don't understand.