It's 2 years now and Atcoder, Codechef are having this option. Topcoder also allows through email (they deleted within 10 hours of my email). Why not Codeforces ?

Suppose we are given $$$n$$$ integers (anywhere from $$$1$$$ to $$$1e5$$$). We are then asked query weather if a number $$$x$$$ was given in input. Fastest way to solve this is using frequency array say $$$a$$$. We can do $$$++a[x]$$$ during input and check if $$$a[x]!=0$$$ while answering the query. Each query here can be answered in $$$O(1)$$$.

Now suppose I am given $$$n$$$ pairs of integers instead, let's say $$$n=5$$$ (their value can be from $$$1$$$ to $$$1e5$$$) and input are $$$(1,2),(10,11),(14,14),(1000,1320),(456,321)$$$. Now I am asked if $$$(10,11)$$$ was in the input, what is the fastest way to do it ? We can use map of pairs and we can answer each query in $$$O(logn)$$$. I wonder if there is any $$$O(1)$$$ method ?

Since Covid has felled a lot and colleges are opening, will ICPC 2021 prelims will also be delayed like 2020 ? Usually it happened during late October most of the time. Any updates on thus Balajiganapathi or Vichitr or anandoham ?

Hello, I am final year student. I spend my college days doing Competitive Programming and I am very bad in development. I am in fear when my job starts after a year they would fire me. What are the things i can do in my next one year to get good in development ? How people with habit of doing Competitive Programming regularly shifted to development ?

Competitive Programming helped to get lot of job interviews but that came with price of very less knowledge in development. I have 1 year left before starting job, so asking suggestion on how to get good in development.

I am sorry to ask this from my second account, but i fear of getting mocked by friends and thus asked using it.

Today I had Uber coding round.

There are $$$n$$$ buildings. We are given array $$$P$$$, which represents price of each building and array $$$a$$$, which represents area of each building. We need to choose $$$k$$$ buildings so that ratio of sum of prices and sum of areas is maximum.

For example :

$$$n=4,k=2$$$

Prices : 2 4 6 8

Area : 1 4 3 2

constraints $$$n<=1000; k<=n; p[i]<=1e6; a[i]<=1e6$$$

We can choose first and last building and ratio is (2+8)/(1+2)=3.3333 and it's maximum possible.

Source : Uber offcampus 2021

I am not able to solve 4th problem of coding round and need help to upsolve it. I put problem statement here also :

Given an array A consisting of N elements, you need to perform the following operations: – remove p elements from the array – remove q groups of consecutive elements of size 2 – remove r groups of consecutive elements of size 3 After performing the operations, the left and right array formed are merged. Output the maximum possible sum after performing the operations.

Constraint: 1 <= N <= 1e5, 1 <= p+2*q+3*r <= N

Example:

Input:

7 1 1 1 //N p q r

4 5 2 1 3 6 7

Output: 7

Explanation: For p=1, you can remove 1 from the array -> [4,5,2,3,6,7]

For q=1, you can remove 2 and 3 which is group of consecutive elements of size 2 -> [4,5,6,7]

For r=1, you can remove 4,5 and 6 which is group of consecutive elements of size 3 -> [7].The maximum possible sum of array equals to 7. (Note: There are other ways to remove elements which will give the same result)

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 ?

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 ?

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

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 ?

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.

“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 ?

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

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 .

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 !

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 .

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