### supersonic11's blog

By supersonic11, 35 hours ago,

Today I had CodeNation coding round (on-campus):

question1 : Give an array $a$ of size $n$ where $1<=n<=1e5$ and $1<=a_i<=2e5$, we need to find out for each $i$ number of other $j$ such that either $a_imoda_j=0$ or $a_jmoda_i=0$.

Example : 4 2 1 3

output : 2 2 3 1

We can solve it in nlogn by using concept of harmonic series.

question2 : given tree of size $n$, $1<=n<=1e5$ indexed from 0,rooted at node 0 and each node having distinct value from 0 till n-1. Find mex of each subtree.

Example : n=3 , edges : (0,1),(0,2) and values : v[0]=0, v[1]=1, v[2]=2. Output : mex[0]=3,mex[1]=0,mex[2]=0.

Was able to solve partially in $O(n*n)$. can someone tell how to solve in better complexity ?

question3 : Given an array $a$ of size $n$, beauty from $l$ to $r$ is defined as $a_l+(-1)*a_{l+1}+a_{l+2}+(-1)*a_{l+3}....$repeating till r. $1<=n<=1e4$. There are $Q$ queries, $1<=Q<=1e5$. Either 1 i x, which means update a[i]=x, or 2 L R, which means maximum beauty among all subarrays in index range L to R. Note that $-1e9<=x,a[i]<=1e9$.

Example :n=2 a: 4 -2 7, two queries 1 2 1e9 and 2 1 3. answer for query is 7.

How to solve 2nd and 3rd one ?

• +39

By supersonic11, 4 months ago,

I am using Linux based operating system (Ubuntu) and chromium browser.

From past 2 days if i open codeforces on my laptop it's opening very slow whereas on my android phone it's loading fine.

Also i am getting lot of times message like "codeforces is not reachable or your connection is broken" .

Is this happening to anyone else ?

• +42

By supersonic11, 4 months ago,

problem

I read the editorial and i have understood the solution . Two key points in the solution are :

1.sorting on the basis of beauty.

2.observing that $max(c_i,a_j-a_i)=c_i+max(0,a_j-a_i-c_i)$.

After that finding solution is trivial.

I have personally solved problems with similar difficulties but i always wonder how the people who solved this in contest reached to such points. I can come up with such observations but it always take lot of time .

Can people who solved this during the contest share the thought process.

Thanks

• +30

By supersonic11, 4 months ago,

We know that using 1LL is necessary if we are shifting more than 32 bits but i have seen a lot of coders doing :

variable1 = (varialbe2+1LL)%mod

where variable1 and variable2 are in long long already.

Since we know that whenever we operate int and long long overall operations take place in long long . Then why most people do it ?

I mostly do it during contest to avoid penalty but afaik i never saw my program giving WA/TLE/RE if i do :

variable1 = (varialbe2+1)%mod

Has any one ever experienced that it's necessary to typecast operand which is in int to long long even if other operand is in long long already ?

• -13

By supersonic11, 4 months ago,

Suppose i have functions $f(x)=min(c_1,max(b_1,x+a_1))$ and $g(x)=min(c_2,max(b_2,x+a_2))$ , how to prove that $g(f(x))=min(c,max(b,x+a))$ . Here except $x$ all other values are constants.

Motivations of the problem : I was reading editorial of atcoder ABC 196 problem here but i am not able to understand how 3rd step came from 2nd in the proof.

• +12

By supersonic11, history, 5 months ago,

“Deciding what not to do is as important as deciding what to do” — Steve Jobs

So whenever you get tired of doing competitive programming , what you do in your free time ? What habits do you have which you think effects you positively ?

• +27

By supersonic11, 6 months ago,

Suppose i have rating x , then is practicing problem in rating range [x-300,x+300] better compared to practicing problems in range [x-300,x+600] ?

I can solve problems which are very difficult than my current rating during practice , but sometimes in contests in stuck on problems very below my rating ,

So what is most optimal way of practicing ? Practicing problems too difficult than your current rating or problems just around 300 above your rating ?

You can answer this from perspective of any level .

Any suggestions from your side will help me a lot .

Thanks

• -14

By supersonic11, history, 7 months ago,

I might be downvoted here heavily but i want to say , codechef which from past several years is unable to make well balanced problem set .It's server crashes every second contest and always had an issue with ICPC online in previous years ,.

Should codechef hold ICPC for next year or in future ? I think that the responsibility should be given to codeforces or atcoder .

• +94

By supersonic11, 10 months ago,

Given an binary string 100000... of size '$m$' on day 0 , For each subsequent day, the updated value at each index >= 1 is given by xor of the value of (i-1)th index and ith index on the previous day . Print the binary string on nth day . where $1<=n,m<=1e5$ .

I am able to see some pattern after writing down the string for several days but not able to make it concise .

Edit : Following is the link

Read the first question of coding round.

question is slightly different from the link given (since that question can be solved by brute force)

I asked this question and my contribution went from 0 to -15 . I agree that i am not helping someone but i thought people might find this problem interesting and i can get help . Also i tried for few hours before posting . Even small help from your side will motivate me to grow and work harder .

So many nice ideas provided . I want every one in comment section THANK YOU for helping !

• -11

By supersonic11, 14 months ago,

I am new to codeforces . I will be thankful if some one tells how to upload image on codeforces . When i click the image icon , it asks me for a link , but nothing appears when i enter the link and submit .following text automatically gets written  ![ ](https://imgur.com/2A2TrxE)  I went to previous post but i am too dumb to understand how to do . Please help .Thanks in advance.

Edit : Please do not downvote.Because if some one will visit my profile it will look like i am bad guy and write bad stuffs . I don't think i am negatively contributing to the community .

• +8

By supersonic11, 15 months ago,

Problem Link : CLEANRBT . I read here that problem can be solved by first finding all distances between each pair of dirty cells using BFS .That part i understood.

Now we need to find answer for each of the case where final position of the robot will be the i'th dirty cell and i we need to take minimum for all of them .I didn't understood how to do that . For example there are two dirty cells say b,c . Then we need to calculate $min(distance(o,a)+distance(a,b),distance(o,b)+distance(b,a))$ .Here 'o' is the starting position of the robot.How to do that ? What will be the transition formula ?

Thanks