In this code:

if(m[sieve[j]]==2){
cout<<"YES\n";
return;
}

You are accessing m[sieve[j]] many times which takes much more time than simple O(1) operations.

Congrats :)

Channel name was CodeNCode

That content is no longer free.

"When you are good at something, never do it for free."

That channel owner was bought by some startup for providing dsa course as far as I know. That video was editorial for this problem.

Apart from the preliminary conditions, $$$p[i]+s[i]$$$ should be greater than $$$p[n]$$$ as $$$p[i]$$$ and $$$s[i]$$$ have one common element ( $$$ith$$$ ) atleast so it is counted twice both in $$$p[i]$$$ and $$$s[i]$$$ and when we merge those segment the number of distinct elements can't be more than their sum-1 (1 of them was counted twice). That gives us:

p[n]<=p[i]+s[i]-1

So if $$$p[i]+s[i] \lt =p[n]$$$ we would return false

Edit: Didn't tried to prove whether they are sufficient. I have a feeling that some additional conditions should have been there (In my solution, I put some more conditions). Is there anyone who has proved that these conditions were sufficient?

:(

looking for a clan?

Yeah, his handle also sounds like cheating

Those names of clubs XD

Don't know about that testcase but this your solution will fail on many testcases.

Answer should be "NO" but your code will output "YES"

You should start with B

If it's not fun and is becoming a stress for performing good, simply don't do it. Have some fun, learn new skills. Do cp as long as not doing it feels like something is missing.

prize comes with a wait

Seeing your post gives a good motivation to lots of us to solve more problems.

Don't trust this guy. Nobody will give that much of their time and efforts for free. Anyways this guy is not eligible. No offence.

Do you know why did you get TLE for tc 10 on div1 A? I am not able to find what's the problem with your code.

Yes

I got scared for a sec that should I click this lol

Great work guys

The ones who write "my code is working fine on ..(somewhere).. but is giving runtime error on codeforces"

The ones who don't solve problems but open codeforces everyday to just see these blogs.

Damn that's crazy. It would be better if you put your articles at gfg or something.

For 2nd task memory limit is quite tough, using long long was giving mle and int was giving ac.

Don't know about gaussian elimination although there is also another method to solve this problem using vector addition on xor (reference here )

It will allow us to solve in around $$$10^6$$$ iterations.

I just realized I was wrong in my approach. I wonder why I have upvotes lol. A number can be divided by two multiple times. For example 8 has 4 possible states {8,4,2,1}, So only 2 states thing was wrong. Every number can be be divided by 2, 0 to $$$log(n)$$$ times.

There must be some solution of this using set/multiset or an appropriate data structure. But without them it can also be solved.

Let's say we are given array a[n]. We will first make all the odd numbers even by multiplying by 2. Now, we will never multiply and only divide by 2 , all numbers are their highest states. Let's find minimum of the array. Let us represent it by min. For all numbers other than min, if they are even and dividing them by 2 won't change the min, we should divide them then. Because for the fixed min, it can only decrease max. Once we do this process, let's sort the array in descending order.

Let's have 2 pointers mx and mn, representing indexes of max and min element respectively. Initially mx=0 and mn=n-1, So, now we will iterate cyclically in the array from i=0 (at anytime i will represent mx and (i+n-1)%n will represent mn. We will update our answer at each step. So, if we will divide a[i] by 2, it will become new mn. and next i will become mx and if we can't divide it by 2 (it is odd), we will stop because if we can't decrease max element, no point of decreasing other elements.

//  Copyright © 2020 Kavish Lodha. All rights reserved.
#include <bits/stdc++.h>
using namespace std;
#define vll vector<long long>
#define vvll vector<vector<long long>>
#define mll map<long long,long long>
#define max(a,b) ((a>b)?a:b)
#define min(a,b) ((a>b)?b:a)
#define pb push_back
#define prll pair<long long,long long>
typedef long long ll;
typedef long double ld;
#define ff first
#define ss second
#define rep(i,a,n)   for(ll i=a; i<n; i++)
#define rrep(i,a,n)  for(ll i=n-1; i>=a; i--)
const ll mod=1e9 + 7;
int main(){
   ios_base::sync_with_stdio(false); 
   cin.tie(NULL);
   cout.tie(NULL);
   cout<<fixed<<setprecision(20);
   ll n;
   cin>>n;
   ll a[n];
   rep(i,0,n) cin>>a[i];
   rep(i,0,n) if(a[i]%2) a[i]*=2;
   sort(a,a+n);
   rep(i,1,n){
       while(a[i]%2==0&&a[i]>=2*a[0]) a[i]/=2;
   }
   sort(a,a+n,greater<ll>());
   ll ans=a[0]-a[n-1];
   ll mx=0,mn=n-1;
   while(1){
       ans=min(ans,a[mx]-a[mn]);
       if(a[mx]%2==0){
           a[mx]/=2;
           mx=(mx+1)%n;
           mn=(mn+1)%n;
       }
       else break; 
   }
   cout<<ans;
   return 0;
}

tourist and Benq competition is getting interesting nowadays. 2 months back Benq broke tourist record of highest rating ever on cf. This time tourist.

I had friend you because I frequently see you in comments.

And Leo Messi would be newbie.

Do we have to take consecutive towers? I didn't saw it mentioned anywhere. The author of the blog is talking about sorting the array too.

Binary search on lowest possible max height. We know the final sum heights d*m+h1+h2.....

We can check if we can achieve the sum while maintaining our maximum and increasing each number by atmost d.

#include <bits/stdc++.h>
using namespace std;
int main(){
   ios_base::sync_with_stdio(false); 
   cin.tie(NULL);
   int n,m,d,mx=0,sum=0;
   cin>>n>>m>>d;
   int h[n];
   for(int i=0;i<n;i++) cin>>h[i];
   for(int i=0;i<n;i++){
    mx=max(mx,h[i]);
    sum+=h[i];
   }
   cout<<mx+d<<" ";
   int lo=mx,hi=1e9;
   while(lo<hi){
    int mid=(lo+hi)/2;
    int s=0;
    for(int i=0;i<n;i++){
        s+=min(h[i]+d,mid);
    }
    if(s>=sum) hi=mid;
    else lo=mid+1;
   }
   cout<<lo<<"\n";
   return 0;
}

Or m1.google

And then guess the problem from it.

Read problem then read editorial.

Source?

Benq orz.

Damn, your username XD

Thanks

Damn bro, you are right only changing t=t+"0" to t+="0" gave AC. 118441663

But can anyone tell why that happens? I used to think, both are just different ways of writing.

I was getting TLE on D. I only suspect string concatenation. But why could that give TLE. Isn't it O(1) in C++.

My submission: 118431680.

Recursive a little bit slower but rarely it will matter.

You are wrong with that iterative thing. In my experience you rarely need to do iterative dp.

Btw I learned a lot from this video when I was learning dp.

You can see that in the solution of Coin Combination II, we are always using the coins with least value first. When you were starting the j loop in that solution, we were in some way assuming that we have only one coin of value 0. Now, when we have processed for j=0 and are starting processing for j=1 we can see that it's similar to the starting of loop j=0 with only difference that we have already a coin of value 0, c[0] ,2*c[0], 3*c[0].... and we are only using one of these at a time. The whole conclusion is to give you the intuition that in the second solution all coins of similar types are always used together and coins are used in ascending order of values so it is just like sorting the values used for forming x and then calculating the number of different ways. While in first solution the last used coin can be anything. So we can have any order of the coins. Hope it was useful.

I think there should have been DRAW case as it will only make it better. But it doesn't making quite sense printing TIE when not even mentioned anywhere.

Nice work COPS-IIT BHU team.

Store the array as its reverse and then use prefix sum.

Can you plz elaborate more, I didn't even get what is paragraph.

I want to check my solution. Can you link the problem? Or did you made it yourself? I am sure it can be solved in O(n).

Bro what do you want? Do you want candle march for you so that you can get justice XD

'%' operations are a lot slower. I just changed a line and it got ac 115016226

I think you got TLE because of using '%' operation. Simple boolean operations would pass your solution.

Can anyone try to hack 114954966. I think it should have given TLE.

Can you link a submission which got accepted with this?

Why don't you use inbuilt sqrt function or binary search for square root?

Also WA, TLE, RE will have much more effect if we consider classic 10 min penalty.

Try using carrot. Works fine.

Firstly, I am not defending my act and I already got my lesson. I don't cheat otherwise and will never cheat again.

Talking about codejam, I got some bugs in A and so I shifted to B. Then when I moved back to A there were just too many submissions and I thought something like this was asked before so I googled. And the first result was that YouTube video. If, it would have been any other round, I won't submit but it was codejam and cheaters won't be caught as usual and if I don't do it, I won't qualify. I have already regretted about it. Everyone makes mistakes and learn something. I have already told I don't cheat and I won't cheat so stop mentioning me again and again. There are 46 people in the list and I am one of the most mentioned.

In these last 2 days, I saw comments like "Another candidate master exposed", let me tell you I earned it without any cheating. And people abusing me through cf messages. Random newbies justifying why I they are still newbie because of me.

I have been ignoring these but now it's too much. Downvote as much as you can, I stopped caring.

You don't need to specify names again.

Only those who solve it should be able to vote. Good idea btw.

Suspicious, that's what a telegram cheater would say XD.

The solution was clean (not so long as expected) but I don't think we got something to learn, just some basic modulo arithmetic and a lot of thinking behind implementation.

Hope this helps

The fun part is this guy takes 2-3 wrong attempts and over one hour to solve A and then upload it without any try to solve B.

Problem B

I found a youtube channel that uploaded A solution of atleast today's and previous round A solution.

We can clearly see from this link a submission of the person from which I identified his profile.

Take some action against this guy.

I initially thought that Xor of array should be 0. I got wrong answer on pretest 3. I was thinking of a counter case and then realize of a countercase like this and corrected myself:

4

3 3 3 0

Guess what the above case was the hack XD.

link

When and how will we know the final ranks?

Why Just do it is added at the end moment. That too with non-understandable statement. Can you just clarify or remove it? Edit: It's removed.

As a helper, give me some contribution.

dp[i] is the contribution to the answer if we have i consecutive white cells in a row/column.

Let's take the case of row. If last cell if blue then it's equivalent to dp[i-1]. If last cell is red but 2nd last cell is blue it is equivalent to dp[i-2]. And the remaining case, if both last 2 cells are red, it is equivalent to dp[i-2] and a tile on last 2 positions. That tile will contribute for all the 1<<(i-2) states of the previous cells.

Hence, dp[i]=dp[i-1]+2*dp[i-2]+a[i-2] where a[x]=2^x.

That was the main intuition behind the solution.

112847614 You can look at this submission, it is quite neat.

Drinking is not Healthy.

First I made the 1st array greater than 2nd by swapping.

I have made an array named 'c' of size n, such that c[i] represents the no. of dismatches (a[i]!=b[j]) in the next m days if we start from a[i].

Mathematically, c[i] = no. of j's such that a[(i+j)%n]!=b[j] and j=0 to m-1

Initially all c[i]=m (we assumes all dismatches). Now we can iterate the 'b' array.

If b[i] is not present in array 'a', then b[i] won't cause any match irrespective of starting index (won't effect any c[j]). We will simply continue.

otherwise if b[i]==a[j] (you can use an additional array/map to find that), we should decrease c[(i-j)%n] by one because we will find a match when we start from (i-j)%n after j indexes.

Thus we obtain c array. Let x=0. Now we can just push_back c[x] in a vector and change x to (x+m)%n until it again reaches x=0 ( cycle formed)

after that it's just trivial.

Yes, it is too similar lol.

div-2D/1B can be solved in linear time. We just need to calculate for each starting position in 1st array, how many matches will be with 2nd array in next m indexes. Here's my AC: 109899040

Hii

Yeah, they added that modulo statement just now.

I also have the same query. Did you get the answer?

Atleast preview blog before posting.

Vulgar words when fst happens

I think, if you have no cp experience and straight off start giving contests on cf without much practice, anyone can become newbie irrespective of their potential. It is just that most of them (I have not checked all of their profiles) didn't remain newbie for a long time and learned quite fast.

For beginners, focus should be more on solving random 'not too hard' problems

What is that k in isPossible() function

Can you link the problem?

A good technique:

if you are looking for 1st position satisfying some condition do this:

mid=(left+right)/2;

if(some_condition()) left=mid+1;

else right=mid;

if you are looking for last position satisfying some condition do this:

mid=(left+right+1)/2;

if(some_condition()) left=mid;

else right=mid-1;

I just followed this.

And just had good mathematical background

A good technique:

if you are looking for 1st position satisfying some condition do this:

mid=(left+right)/2;

if(some_condition()) left=mid+1;

else right=mid;

if you are looking for last position satisfying some condition do this:

mid=(left+right+1)/2;

if(some_condition()) left=mid;

else right=mid-1;

I just find it took me 2 months to become expert with 2nd contest on 26 march (during 1st contest, I didn't even know how to take input XD) and becoming expert on 26 may.

Yeah for D, you can also have a look at Edu binary search step 4

People like me, who had seen Cf Edu Binary Search step 4, can easily get the intuition for D. Loved the problemset. D was savior.

abdstar

Also I was master before div1 round but CM before educational but I am shown div1 in the edu round and it's unrated as for me.

Also, another question if it's rated and it's rating change is being calculated, after rating change if someone has >= 2100 rating (and previously before educational round he/she had <2100 rating) will educational round still become unrated?

And they also didn't specify which p they are talking about, the changed one or original.

Yeah I wouldn't understand if there were no sample testcases.

Felt you

Damn! took me time to understand why array size becomes O(root n).

Btw final complexity should be O(nrootn) not O(krootn) but it doesn't even matter.

Hey, can you suggest some problems with non-asymptotic optimizations using bitsets or anything else?

Doesn't look like a competitive programming site logo XD

Maybe becoz his college semester is completed (most colleges in India had it during this period) and he got free and had enough time, can't draw any conclusions.