Codeforces Round #707 Editorial

4 years ago, # |

← Rev. 5 →

+15

I decompose 2C into several cases:

1) We have 4 copies of a value X (e.g. 1 1 1 1 2 3) => YES

2) We have 2 or 3 copies of a value X; and we have several such X (at least 2), (e.g 1 1 2 2 2 5 10) => YES

3) We have 2 or 3 copies of a value X; and there is exactly one X like that (e.g. 1 2 2 2 100 7 9) => two pointers for checking whether we have u and v such that u < X < v and u+v = 2*X => YES/NO.

If YES, it is ok. Otherwise, we remove duplicated elements and continue with case 4.

4) We have only distinct values (e.g. 1 2 5 9 11 13 ...)

If N*(N-1)/2 > 5*10^6: we will have two different pairs (x,y)and(z,t) that meets the condition; because of the Dirictle lemma. Just check bruto-force the first sqrt(10^7) elements.

Otherwise, perform O(n^2) algorithm to check.

→ Reply

_Ramba_

4 years ago, # ^ |

Can you elaborate on Dirictle lemma?

→ Reply

4 years ago, # ^ |

← Rev. 3 →

+16

It is something like : if you put N items into M boxes with N>M; you will have a box with at least 2 items.

So, given that we have an array of size N with distint non-negative values and we have n*(n-1)/2 pairs (u+v), and if n*(n-1)/2 > 5,000,000; we should have a YES answer.

→ Reply

hetp111

4 years ago, # ^ |

+14

Is it same as pigeon hole principle?

→ Reply

4 years ago, # ^ |

+13

Yes, it is the same. I just do not remember the name you mentioned.

→ Reply

Hz_

4 years ago, # ^ |

Great explanation! it helped me to completely understand why brute force sol. works.

Thanks.

→ Reply

dhruv7888

4 years ago, # ^ |

Why do we have to check only sqrt(10^7) no.s , Here we are on addition so shouldn't we check till 2.5*10^6 , for each loop

→ Reply

4 years ago, # ^ |

it is since using the first sqrt(10^7) elements of A, you create more than 5*10^6 values of form A[i]+A[j] with i<j.

→ Reply

dhruv7888

4 years ago, # ^ |

Okkk , Thanks , I got it

→ Reply

AzusaCat

4 years ago, # |

← Rev. 2 →

Can you unhide the main tests? I can't wait to find why I FSTed:(

→ Reply

4 years ago, # |

← Rev. 2 →

Div1 B can be solved in O(n log k). Crt and Gcd is not necessary .

→ Reply

4 years ago, # ^ |

← Rev. 2 →

-10

code:

Spoiler

/*
{
######################
#       Author       #
#        Gary        #
#        2021        #
######################
*/
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define check_min(a,b) a=min(a,b)
#define check_max(a,b) a=max(a,b)
using namespace std;
//inline int read(){
//    int x=0;
//    char ch=getchar();
//    while(ch<'0'||ch>'9'){
//        ch=getchar();
//    }
//    while(ch>='0'&&ch<='9'){
//        x=(x<<1)+(x<<3)+(ch^48);
//        ch=getchar();
//    }
//    return x;
//}
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
/*}
*/
const int MAXN=5e5+233;
int n,m;
LL k;
int q[MAXN];
int a[MAXN];
int b[MAXN];
map<int,int> pos;
vector<int> v;
bool vis[MAXN];
bool check(LL x){
	LL tur=x/m;
	LL Lm=x%m;
	LL sum=0;
	for(auto it:v){
		sum+=q[it];
	}
	if(tur/v.size()&&k/(tur/v.size())<sum){
		return 0;	
	}
	sum*=tur/v.size();
	tur%=v.size();
	rep(i,tur){
		sum+=q[v[i]]; 
	}
	int now=v[tur];
	rb(i,1,Lm){
		sum+=(a[(now+(i-1)-1)%n+1]!=b[i]);
	}
	return sum<k;
}
int main(){
	scanf("%d%d%lld",&n,&m,&k);
	rb(i,1,n) scanf("%d",&a[i]),pos[a[i]]=i;
	rb(i,1,m){
		scanf("%d",&b[i]);	
		if(pos.find(b[i])!=pos.end()){
			int I,J;
			I=pos[b[i]];
			J=i;
			I-=(J-1);
			I--;
			I+=n*2;
			I%=n;
			I++;
			q[I]++;
		}
	}
	rb(i,1,n) q[i]=m-q[i];
	int now=1;
	while(!vis[now]){
		vis[now]=1;
		v.PB(now);
		now+=m;
		now--;
		now%=n;
		now++;
	}
	LL l=0,r=1e18;
	while(l<r-1){
		LL mid=(l+r)>>1;
		if(check(mid)){
			l=mid;
		}
		else{
			r=mid;
		}
	}
	cout<<l+1<<endl;
	return 0;
}

Spoiler

→ Reply

4 years ago, # ^ |

Any tutorial?

→ Reply

4 years ago, # ^ |

Find the loop section and binary search

→ Reply

4 years ago, # ^ |

I don't understand. Do you mean precalculate length lcm(n,m) and find answer to k using binary search? I am a little dumb here becuz the loop section's collision might need O(nm) to find if n and m are coprime.

→ Reply

4 years ago, # ^ |

You can see the "while(!vis[now])" part in my code , it found all the loop section.

→ Reply

PedroBigMan

4 years ago, # ^ |

I might be wrong but I believe if one uses CRT, but not BS on the answer, it is O(NlogN). We compute the values mod mmc(N,M) that have the same color.

→ Reply

NaimSS

4 years ago, # ^ |

← Rev. 2 →

+18

It could be solved in O(N + M) to. Binary search is not necessary, one could just "simulate". In case someone is interested: code

→ Reply

Thallium54

4 years ago, # ^ |

your submission hype link is broken and no one found lol

→ Reply

NaimSS

4 years ago, # ^ |

Fixed. Sorry about that

→ Reply

brezhart

3 years ago, # ^ |

If my math is correct, it can be solved in O(N) (or smth like O(N+M+log(N+M)), but linear in general)

126387236

→ Reply

hhoppitree

4 years ago, # |

-53

This editorials is so fast that I'm be so surprised of it!

→ Reply

arujbansal

4 years ago, # |

I have a randomised solution for div2C/div1A and I'm not sure if I cheesed system tests or if it's supposed to pass. Can someone take a look at it and hack if possible? Otherwise, if it's supposed to pass, can someone tell me the probability of failure?

Submission: 109876872

→ Reply

some modifications will do

4 years ago, # ^ |

That is a nice try..

→ Reply

arujbansal

4 years ago, # ^ |

-8

And it did pass system tests :)

→ Reply

Retired_xryjr233

4 years ago, # |

I got a FST in Div1B.

But when I submit the code again after contest , it accepted (but 1981ms).

And when I submit the same code again with C++17(64) , it accepted and only ran 1653ms.

What a pity...

My submisson during contest:109857178

Submisson after contest:109891513

With C++17(64):109891826

→ Reply

akashiSan

4 years ago, # |

← Rev. 2 →

+13

I found the GFG page, but looking at it I thought it wouldn't pass. After the contest and reading some comments here, I thought it just might.

I tried, and it got AC. Smile in pain. Hehe.

GeeksForGeeks article

→ Reply

Ankush08

4 years ago, # |

Please can someone explain me this : During the contest I submitted ABC and there it said pretest passed and now it is showing -1 in A and C, saying WA in tc 6(for A) and TLE in C problem. How does this happen?Should not they show this during the contest, that i have done 2 questions wrong ?? Please if someone could help me understand what happened ? I am really frustrated rn

→ Reply

iaNTU

4 years ago, # ^ |

Since it would take too much time to run over all the testcases during the contest, Codeforces divides the testcases to be "pretests" and "system tests".

Passing the pretests doesn't mean that you solved the problem (though it should...).

→ Reply

xtqqwq

4 years ago, # |

+208

Good contest with strong pretests, especially in problem B and problem C.

What's more, the tl of problem B and the ml of problem D are very friendly. No one can get TLE or MLE on them.

→ Reply

Radewoosh

4 years ago, # ^ |

+76

I think that you should say clearly that it's a sarcasm, it might be hard to get it.

→ Reply

cip999

4 years ago, # ^ |

← Rev. 4 →

+53

Can't speak for D, but, unless my solution is very wrong and tests are extremely weak, binary search in div1B isn't needed at all. In fact, I solved it in $$$O((n + m)\log(n + m))$$$, where the $$$\log$$$ comes from a single sorting of a vector with up to $$$\min(n, \, m)$$$ elements.

Sketch of solution. Iterate over the colors and make a vector $$$s$$$ of all solutions to the system that you find (if for some color there are no solutions, ignore it). Then sort the vector. Now set $$$ans$$$ to $$$\displaystyle \text{lcm}(n, \, m) \cdot \left\lfloor \frac{k}{\text{lcm}(n, \, m) - \text{size}(s)} \right\rfloor$$$ and reduce $$$k \mod (\text{lcm}(n, \, m) - \text{size}(s))$$$. Finally, iterate over the elements of $$$s$$$ and stop at the first index $$$i$$$ such that $$$s[i] - i \ge k$$$. Then it is easy to update $$$ans$$$ to the correct value.

→ Reply

Zuciso

4 years ago, # |

How to solve Div1B/Div2D ?

→ Reply

Runtime_terror_

4 years ago, # |

-8

Can anybody please explain why this solution for div2 A is giving wrong answer https://codeforces.me/contest/1501/submission/109849523

→ Reply

TAImatem

4 years ago, # ^ |

← Rev. 12 →

nvm, you figured it out yourself either way

→ Reply

box

4 years ago, # |

109860426

Who wants to hack my randomized div1A?

For n <= 150, I use a quartic brute force.

For n > 150, I use MITM, where I partition the array into two halves, and randomly select 10^6 pairs from each half, and check for any common sums.

→ Reply

Swistakk

4 years ago, # |

← Rev. 2 →

ML in D was brutal. If only $$$q \le 9$$$ instead of $$$10$$$ or number of colors was up to $$$2\cdot 10^6$$$ instead of $$$2.25 \cdot 10^6$$$ it would really be easier xd

→ Reply

rakesh23

4 years ago, # |

← Rev. 2 →

Div-2 C solution in gfg:

→ Reply

AmmarDab3an

4 years ago, # ^ |

← Rev. 2 →

-7

→ Reply

AmmarDab3an

4 years ago, # ^ |

← Rev. 4 →

→ Reply

rng_X

4 years ago, # |

Shitty Round especially statement of problem DIV2A.

→ Reply

cppascalinux

4 years ago, # |

109889803
For 1500C - Сортировка матрицы , the $$$O(nm^2)$$$ approach could be optimized to $$$O(\frac{nm^2}{w})$$$ using bitset, which could pass the tests.

→ Reply

feecIe6418

4 years ago, # ^ |

Yes, that's what I did in the contest. I really think it's a good problem, but the limit seems quite tight. I douted whether it would pass before submitting (it passed though).

→ Reply

starusc

4 years ago, # ^ |

$$$O(nm^2)$$$ can be pass the tests too. So Incredible! 112190603

→ Reply

towrist

4 years ago, # |

← Rev. 2 →

+34

I had figured out a $$$O(nm^{2})$$$ solution for 1C, but now I don't even understand how the editorial reaches $$$O(nm^{2})$$$, let alone understanding optimising it to $$$O(nm)$$$. The editorial is hard to understand.

I think the optimising part made it too difficult a problem for its position as 1C ?!

In particular, can someone please explain this part:

If two rows are in the same class, then the columns that we applied had the same values. Then, we need to find a column that does not break the sequence between the rows inside each of the classes. Let's iterate through such a column every time.

What values are we talking about?

→ Reply

cip999

4 years ago, # |

+37

An alternative approach for Div1A.

Let us prove that if $$$n > \sqrt{8\max a} + 2$$$ then we can always find such a quadruple. Indeed, sort $$$a$$$ in ascending order and consider the differences $$$a_2 - a_1, \, a_4 - a_3, \, \dots, \, a_{2k} - a_{2k - 1}, \, \dots$$$ These are $$$\left\lfloor \frac{n}{2} \right\rfloor$$$, so there are two of them which are equal. If that weren't the case, we would have

$$$\displaystyle a_n \ge \sum_{k = 1}^{\left\lfloor \frac{n}{2} \right\rfloor} (a_{2k} - a_{2k - 1}) \ge 0 + 1 + \cdots + \left(\left\lfloor \frac{n}{2} \right\rfloor - 1\right) = \frac{\left\lfloor \frac{n}{2} \right\rfloor\left( \left\lfloor \frac{n}{2} \right\rfloor - 1 \right)}{2} > \max a.$$$

Let $$$i, \, j$$$ be such that $$$a_{2i} - a_{2i - 1} = a_{2j} - a_{2j - 1}$$$. Then $$$x = 2i$$$, $$$y = 2j - 1$$$, $$$z = 2j$$$, $$$w = 2i - 1$$$ is a solution.

Now we proceed as follows. We sort $$$a$$$, iterate over the even values of $$$k$$$ and check if two differences $$$a_{2k} - a_{2k - 1}$$$ are equal. If this is the case, we are done. Otherwise, $$$n < \sqrt{8\max a} + 2$$$ and we can bruteforce the answer in $$$O(n^2)$$$.

→ Reply

YangTY

4 years ago, # ^ |

sorry but I can't figure out how $$$n > \sqrt{8\max a} + 2$$$ is calculated, could you please give an explaination?

→ Reply

4 years ago, # ^ |

← Rev. 2 →

You gotta solve the equation $$$\frac{\left\lfloor \frac{n}{2} \right\rfloor\left( \left\lfloor \frac{n}{2} \right\rfloor - 1 \right)}{2} > \max a.$$$ to get this. The inference makes sense, however, I don't quite understand how you bruteforce the answer in $O(n^2)$。

UPD: I now understand, use the method as editorial. But then you don't need to do those survey beforehand :<

→ Reply

cip999

4 years ago, # ^ |

Exactly as in the editorial solution. Actually, I realize now that the first part isn't needed at all. Because of the proof in the editorial, the second part alone (bruteforce) is sufficient to solve the problem with the given constraints.

→ Reply

YangTY

4 years ago, # ^ |

Thx for the explaination and I also wonder how to bruteforce in $$$O(n^2)$$$

→ Reply

4 years ago, # |

1500A going home. I notice that ai<=2.5*10^6 but didn't investigate into that.. Indeed, $$$1<=ai+aj<=5*10^6$$$ for arbitrary i,j. And if we have n distinct elements, we will have $$$\frac{n*(n-1)}{2}$$$ pairs of different pair of (i,j). If $$$\frac{n*(n-1)}{2}>5*10^6 => n>=3162$$$ you are guaranteed to find an answer. Well, doesn't help to solve this problem.

→ Reply

4 years ago, # |

I feel like this approach for div1A/div2C is right but it FSTd. Can someone tell me why?

So first i rewrite the eqn as ax-az = aw-ay. Now I just need to find 2 pairs of indices such that their differences are the same.

For this, I store all elements in a frequency array and iterate over all differences.

for(int i=0;i<N;i++)
    for(int j=0;j+i<N;j+=i)
        //check if j and j+i are present in the freq array
        //Find 2 such pairs and that would be our answer

My submission

→ Reply

gupta_samarth

4 years ago, # ^ |

Did you make sure to not repeat some index? Maybe that is the case

→ Reply

4 years ago, # ^ |

Yes, if i take the pair {j, j+i} at one iteration, and if freq[j+i]==1, I make sure to not take it again, or else i consider the possibility that it can be taken again

→ Reply

jainnirav88

4 years ago, # ^ |

← Rev. 2 →

4 2 7 11 16

o/p : YES 1 4 2 3

your code's o/p : NO

→ Reply

4 years ago, # ^ |

Thanks a lot, I got my mistake

→ Reply

Perry_Prasad_Platypus

4 years ago, # |

+13

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

→ Reply

4 years ago, # ^ |

Yup I used a similar approach. Code

→ Reply

Perry_Prasad_Platypus

4 years ago, # ^ |

Yes, it is too similar lol.

→ Reply

Fawkes

4 years ago, # ^ |

Can anyone of you explain your submissions as it seems that some mathematical principles are hidden in some beautiful lines written out there. Thanks.

→ Reply

Perry_Prasad_Platypus

4 years ago, # ^ |

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.

→ Reply

vasu_kesharwani

4 years ago, # |

Can anyone explain why brute force worked in C (going home) even though the constraints are 4≤n≤200000? 2*10^5 should require an O(n) or O(nlog(n)) solution so how O(n^2) worked?

→ Reply

4 years ago, # ^ |

← Rev. 2 →

Because since 2.5*10^5 is the upper bound on every element the maximum sum of 2 elements can be 5*10^5. Now if you just iterate to get all possible sums they will all be below 5*10^5 and in 1 iteration you get 1 new sum, otherwise you break. So you will never TLE.

→ Reply

vasu_kesharwani

4 years ago, # ^ |

*upper bound on every element is 2.5*10^6

→ Reply

4 years ago, # ^ |

← Rev. 3 →

Alright, but it's still more than enough. The solution is actually O(n).

→ Reply

vasu_kesharwani

4 years ago, # ^ |

now i am more confused....

→ Reply

4 years ago, # ^ |

← Rev. 2 →

Ok imagine you have a million elements but upper bound is say 10, do you need to do O(n^2) over a million elements to confirm that you will get a repeating sum? No, as maximum possible sum of 2 elements is only 20 you will only have at maximum 20 different values of sum possible, this is the whole basis of this problem. As another user suggested this is known as pigeonhole principle.

→ Reply

rgnerdplayer

4 years ago, # |

What is the variable "y" in 1B's tutorial?

→ Reply

ShmilyTY

4 years ago, # |

Thanks for fast and clear editiorials!

I quickly(I hope so) solve two problems, when I come to think about C, I had a challange. But finally I solve it. And the great thing is I have a rank of 239! I'm really excited about that:-)

The problems are really great and I enjoyed it a lot, thanks!

→ Reply

rgnerdplayer

4 years ago, # ^ |

Nah the editorial is so confusing IMO

→ Reply

indresh_0903

4 years ago, # |

-10

In Div2 C ( Div1 A ) why the brute force using map and checking sum of 2 pair of indices passes the time limit. Its time complexity is O(n^2) still it passes. Code: https://codeforces.me/contest/1501/submission/109901974

→ Reply

4 years ago, # ^ |

← Rev. 2 →

I Misread...

→ Reply

indresh_0903

4 years ago, # ^ |

← Rev. 2 →

Actually i was trying to show that even using map, brute force O(n^2) is getting passed .. my question was- why is this getting passed through the time limit ?

→ Reply

4 years ago, # ^ |

Because maximum element is 2.5*10^6 so maximum sum of 2 elements is 5*10^6. So you can get at max 5*10^6 different values of sums before encountering a repetition. So once you find a sum again for different indices you can just break the iteration. That's why time complexity is given as min(O(n^2), O(n+C)).

→ Reply

s_r_f

4 years ago, # |

+53

My code for div1B got TLE result. submission

After using fread,it accepted. submission

The complexity of the code is $$$O((n+m)log(nm))$$$

So , why is the time limit so hard ?

→ Reply

real1

4 years ago, # |

again my A FST. is it weak pretest or my blunder? A Submission

→ Reply

Continuous

4 years ago, # ^ |

Both.

→ Reply

shaw_chick

4 years ago, # |

will someone tell me what is wrong with this code https://codeforces.me/contest/1501/submission/109882653 ? it is showing runtime error on test 8.

→ Reply

a.rjput

4 years ago, # |

Why aren't results for div 2 out yet?? I see div 1 results are already out.

→ Reply

_lowerBound

4 years ago, # |

[TWO CHANDELIERS] Can someone explain me over what variable you can do binary search? I don't get the solution at all :(

→ Reply

jimm89

4 years ago, # |

This could just be my own perception, but since restrictions on contest writers were tightened, I have found the contests much more difficult. Today I couldn't solve a single question in Div 1. I think that's the first time that's ever happened, but in general the recent contests have been tough.

→ Reply

https://pastebin.com/uhhe3c4v

4 years ago, # ^ |

← Rev. 2 →

:< Dude you are really hardworking. This used to be a complaint but it is now a comfort from me after checking your profile.

Keep up and do some problems that you never hear of. Wish you luck.

→ Reply

NiceClock

4 years ago, # |

+30

Very beautiful, careful and short solution by olympiad participant teraqqq. May help to understand the solution.

→ Reply

arvindr9

4 years ago, # ^ |

What exactly does vector<int> cut keep track of? Seems like it stores some kind of property for the rows?

→ Reply

NiceClock

4 years ago, # ^ |

In the final state of B, the equivalence classes are sub-arrays, so we store did we cut our classes or not.

→ Reply

Fawkes

4 years ago, # |

Sadly ch_egor have not authored any problem but suffered downwotes for managing the contest and problemset. It is not fair.

→ Reply

EvenX

4 years ago, # |

In Div2 C, I used an intuitive approach to solve that worked. Basically, I iterated over differences (ax — az) from 0 to k*C/N, where C = 2.5*10^6, N is the input size, and k is some constant (say 2) and then I checked whether four such indices exist or not. My question is how to prove that only checking first k*C/N differences works? Also, what is the tight lower bound for such k?

My Submission

→ Reply

ro777

4 years ago, # |

How are we expected to know that the actual value of n used in the main tests is much smaller than the given constraint in div2-C question? An O(n^2) solution should not be accepted according to the given constraints but many people got away with it due to weak test cases. This should be rectified somehow

→ Reply

4 years ago, # ^ |

Did you read the editorial? Time complexity is min(O(n^2,n+C)).

→ Reply

judgme_nt

4 years ago, # |

← Rev. 2 →

I have trouble understanding problem div1 A / div2 C

Why is the condition in the editorial sufficient? If we have 4 pairs such that their sum is equal then there is a solution. However, that doesn't imply that there will always be 4 such pairs if there is a solution to the problem.

In other words, what is the proof that there exists a solution to the problem if and only if there are these 4 pairs that are described in the editorial?

→ Reply

http://codeforces.me/contest/1500/submission/109859256

4 years ago, # |

← Rev. 2 →

-10

Here is the normal solution of d1a instead of the authors' unobvious solution:

If $$$n<10000$$$ run the $$$n^2$$$ solution, else sort the numbers and find the pair of pairs of adjacent numbers with the same difference, also the indices should be different. It always exists because $$$10000^2 > 2.5 \cdot 10^6$$$.

→ Reply

MoRanAirConditioner

4 years ago, # |

I submitted the code when the overall evaluation failed in the competition and passed it directly after the competition. The machine was too slow during the overall evaluation, which led to unfair treatment. Please restore it to me！！！！！

during

after

http://codeforces.me/contest/1500/submission/109932270 http://codeforces.me/contest/1500/submission/109931959 http://codeforces.me/contest/1500/submission/109931910

Quite the same

→ Reply

Yzm007

4 years ago, # |

← Rev. 2 →

How to construct a sequence of number for n = 1570 whose answer is "NO" for div1A/div2C ? I found that 4-th example is that situation, however, I can't construct it. Can someone give me an idea ?

→ Reply

4 years ago, # ^ |

← Rev. 3 →

$$$1, 2, 3, 5, 7, 10, 13 \dots$$$

→ Reply

4 years ago, # ^ |

← Rev. 2 →

The last element is approximately equal to $$$785^2$$$ and one can prove all the pairwise differences are different

→ Reply

dummybawa

4 years ago, # ^ |

Can you please elaborate on how you came up with this sequence?

→ Reply

jyoti360

4 years ago, # ^ |

Output will be YES. As, 5+7=2+10

→ Reply

https://cstheory.stackexchange.com/questions/32126/is-there-an-efficient-program-for-generating-a-sidon-sequence

4 years ago, # ^ |

oh sad let me fix it

→ Reply

wrg0ababd

4 years ago, # ^ |

Using the first answer you can construct sequence of size $$$\sqrt{C}$$$

→ Reply

CP_nii_krni

4 years ago, # |

DIV2 C question was hard to think how it works in N^2 approach even N was in that range which generally doesn't fit in N^2 approach .. many of those (not all of them) get accepted to that question without knowing proper reason.. LOL..

→ Reply

hossainzarif

4 years ago, # ^ |

Even absolute newcomers with just a little idea of complexity won't write O(N^2) solution at this constraints without reasoning. So, what are you talking about? They at least got the intuition and getting it isn't hard. It's just getting the fact that if you have large N, then you would have duplicates in sum simply because of so much options to choose sum and limited options for sum.
So, not actually many of them, only like 1-2% at most without knowing reason tried out O(N^2).

→ Reply

kutbilim.one

4 years ago, # |

Problem C. Going Home. In statement n is <= 200000. So why O(min(n^2,n+C)) doesnt have TLE?

→ Reply