pritishn's blog

By pritishn, 2 weeks ago, In English

Hey, I have noticed that for the past few days I don't receive notification for new comments for blogs that I've written.
The notifications come to my email but not to the bell icon on codeforces.

bell icon

You can see that I got mail nilesh8757 and SuperJ6 have commented on my blog but I don't see it in 'recent notifications' .
Is there any setting for this? Did I disable it by mistake? Is everyone facing this issue?

MikeMirzayanov , can you please look into this if it's a bug?

Read more »

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

By pritishn, 3 weeks ago, In English

It was asked to my friend in google coding challenge and I'm unable to think of any approach.
Can anyone help?

Given a weighted undirected graph G that contains N nodes and M edges.
Each edge has a weight w associated with it.

Answer Q queries:
- x y W : Find if there exists a path between node x and node y such that the maximum weight on that path doesn't exceed W. If it exists print 1 or else print 0.

1<=T<=5
1<=N,M,Q,W,w<=10^5
1<=x,y<=N

Read more »

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

By pritishn, 3 weeks ago, In English

I know it's slightly off-topic but I couldn't find any answers on other sites.
I was actually doing a project in which I think using a trie will be really helpful for processing the queries.

But if I keep remaking the trie everytime from scratch when I load the app then it's gonna be slow. So is there anyway I can store the contents of a trie ( wrapped in a class) into a file and load it directly everytime I need it?

I have done something like this using classes before , but we know trie needs dynamic memory allocation. So will it work if I wrap it in a class and put it in a file?
Also can anyone who has development experience tell how do people generally handle these query-based data-structures in apps? Do they rebuild it on the database everytime?

Read more »

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

By pritishn, 4 weeks ago, In English

So, basically this problem can be considered as a simpler version of https://codeforces.com/blog/entry/74836 . I was wondering what can be the approach if we fix the size of the subset.

Given an array of size N , find the maximum bitwise or of elements in a subset of size K.

What can be the best(time complexity wise) possible approach for this problem apart from this ? Can anyone please help?

UPD: I had initially written Xor everywhere instead of Or. Sorry.

Read more »

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

By pritishn, history, 7 weeks ago, In English

One of my friends noticed a strange behaviour of .size() method.

Link to WA submission : https://codeforces.com/contest/1307/submission/88824759
Link to AC submission : https://codeforces.com/contest/1307/submission/88824749

The bug is in the line
LL x=a[i].size()*(a[i].size()-1)/2;

In C++17 , I guess there is overflow in that expression.
But in C++17(64) , it works fine.

So does that mean the .size() operator can hold larger numbers in 64bit version?
And also what other methods show this kind of varying behaviour when the compiler changes from 32bit to 64bit??
Can anyone explain this please??

Read more »

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

By pritishn, 3 months ago, In English

Hi,
I had made this problem( https://www.codechef.com/FTCF2020/problems/TRADE2 ) and the approach that I used to solve was make a segment tree over a multiset table of size 10^5. In that approach , table[i] would denote prices of phones with speed i. Segment tree would work on the .begin() values of the multiset tables.

I wanted to know if there's any alternate approach to this problem. Thanks in advance!

Read more »

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

By pritishn, 3 months ago, In English

Hi,
Somethings related to Competitive Programming (well, in a broader sense , Data Structures and Algorithms) have been on mind lately.

I know some people who haven't done Competitive Programming and also have very less knowledge of DSA but they never needed those. Example- Some of the seniors from my college are well-placed in good companies but they never properly explored DSA.

I know that being proficient in CP is not the only way to get good placements and I also realize that being proficient in CP also does NOT guarantee good placements.

Lately, my primary motivation to keep doing CP has shifted from "getting good placements" to "it's fun and exciting".
But along with that shift of mindset, I also find it harder to suggest others to start CP (knowing that most of them are just looking for an easier way to get well paying jobs).

So, I wanted to ask you guys.
If you'd ever suggest someone to start Competitive Programming, what would be your reasons to do so? I mean how would you convince someone to start CP ?

PS: I'm sorry if this has been asked before or if you find this useless.

Read more »

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

By pritishn, history, 3 months ago, In English

Hi,
I wanted to know how to make segment tree with
Lazy propagation for Range Assignment Updates (make elements in range L to R equals to update_Val) and Range Sum Queries.
I am not able to code it properly and also I couldn't find any proper tutorial for this specific set of operations.

Can anyone share the code for doing that?

Read more »

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

By pritishn, 3 months ago, In English

Hey everyone,
After watching tmwilliamlin's livestream I was a bit interested in the CSES problemset.
I wanted to ask "Who is it for?" and is it worth it to solve the entire problemset?

I was completing A2OJ ladders (currently in 1700-1800 ladder) till now.
Should I pause that and complete the CSES problemset?

Read more »

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

By pritishn, 3 months ago, In English

Hello everyone, This extension will modify the submit through file block in the problem page so that we can paste our code there and submit.

Of course , if you liked submitting through file then it's useless for you. It is made for those who have a habit of pasting code in the separate submit page.

Links to the extension :

It also redirects into a new tab and you don't have to open a new page every time you submit.
Thanks for reading and hope you like it.

UPD : I added the feature that now selects the code written in the text-area on clicking the submit button, So now it's easier to delete the previously written code.

UPD : I found link to another such tool : https://codeforces.com/blog/entry/66646

This extension is a much simplified version of the tool mentioned in the above blog.

Read more »

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

By pritishn, history, 4 months ago, In English

Me and my floormate(now roommate XD) had made this video in our first year of college.
We didn't know about Codeforces back then, and participated in Codechef only.

Hope you find it entertaining and relatable. :D

https://www.youtube.com/watch?v=J3z_u_kn8dM

Read more »

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

By pritishn, 4 months ago, In English

Problem Link:https://codeforces.com/problemset/problem/442/B

I have been trying to solve it using DP, but there always seems to be precision issues even when using long double.

My submissions : https://codeforces.com/contest/442/submission/81584010

In my approach
dp[i].first = the max probabilty obtainable by choosing 1 or more friends from index i to n-1.
dp[i].second = the product of complements of probablity of all chosen friends.
dp[i].second is helping me do the transition.

Can anyone solve it using such DP without failing due to precision issues?

Read more »

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

By pritishn, history, 5 months ago, In English

Wouldn't it be good if we have a Report Option to directly report plagiarized codes without having to create new blog/ comment on old blogs?

Many users nowadays are creating new accounts to report them through blogs. This can be avoided if we have a way to anonymously report cheaters without having to create blogs.

I think this feature will be helpful as some people who cheat are able to bypass MOSS undetected by using various methods. So if we ever come across such codes we can directly report them for checking.

MikeMirzayanov , please consider this.

Read more »

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

By pritishn, 5 months ago, In English

I checked one of my previous comments and found that the reply on that comment was missing.

I checked the profile of the guy who had replied and it still exists. I am sure that there was a reply on my comment but it isn't present anymore. I mean the profile is there but the reply isn't.

So is there any way to delete comments on blogs?

Read more »

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

By pritishn, history, 5 months ago, In English

I would like to know if there's any blog/article which lists all the DS and Algos required to be on a specific rank. I mean , For example, newbie ranked coders need not learn things like segment tree or sqrt decomposition, but should work on their basic implementation skills.

Similarly I want to know what are the things , coders from each category are expected to know ?

I had found this article but it just gives an overall summary... https://www.hackerearth.com/getstarted-competitive-programming/

PS: I want to know this because I feel like it will help me have a proper step-by-step approach to practice CP.

Read more »

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

By pritishn, history, 6 months ago, In English

Problem link : https://codeforces.com/problemset/problem/478/D

The editorials says that the max height is independent of the colors of the block and can be calculated directly through the total number of blocks.

I am not able to prove it. I need mathemetical/analytical proof of this.

Can anyone help please?

Read more »

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

By pritishn, 6 months ago, In English

Original Question Statement Link : https://pastebin.com/4jH5GJqk (test cases included )

The Question basically asks ,

Given $$$K$$$ Binary Trees each rooted at it's node 1.

We can traverse normally inside a tree.

And we can also move from $$$i_{th}$$$ tree to $$$(i+1)_{th}$$$ or $$$(i-1)_{th}$$$ tree through the root nodes of both i.e go from root node of one tree to the root node next or previous tree.

We can also move from the $$$0_{th}$$$ tree to the $$$(K-1)_{th}$$$ tree and vice versa.

$$$N_i$$$ denotes the number of nodes in the $$$i_{th}$$$ tree.

Find the number of edges in the longest simple path (each node is visited once) over the entire forest of trees.

Note: if we move from $$$i_{th}$$$ tree to $$$(i+1)_{th}$$$ tree via root, we have to increase the answer by 1 as if we have an edge between both the roots,

$$$3 \leq K \leq 10^5$$$

$$$1 \leq N_i \leq 10^5$$$

$$$3 \leq \sum_{i=0}^{K-1} N_i \leq 2,000,000$$$

Time Limit : 1 Sec


I can't think of any approach to solve this. Can anyone please help me?

Read more »

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