Codeforces Round #803 (Div. 2)

2 years ago, # |

+199

As a problemsetter, each upvote on this comment equals one time I'll roast saarang

→ Reply

speed__forces

2 years ago, # ^ |

-21

Nice but who asked

→ Reply

Botswana

2 years ago, # ^ |

+50

I and the entire citizen of botswana asked !!!

→ Reply

abcsumits

2 years ago, # ^ |

mine was 145th one excited to know how you roasted :)

→ Reply

2 years ago, # ^ |

← Rev. 4 →

+15

happily you got >=0 upvotes, otherwise saarang would roast you lol

→ Reply

2 years ago, # ^ |

Saarang does not have the power to roast me

→ Reply

k1r1t0

2 years ago, # |

-7

I just hope I can perform incredibly and get a Candidate Master...

→ Reply

_Vanilla_

2 years ago, # |

Why do I feel like I've seen this theme before...

→ Reply

Il9

2 years ago, # |

+77

As a tester, I’ve been told I get free internet points if I comment

→ Reply

jampm

2 years ago, # |

+29

As a tester, I can tell you this round is fire! yall should try it :)

→ Reply

Codula

2 years ago, # |

+32

As a tester I can tell problemsetters and coordinators have tried their best to keep the problemset as good as possible.
I Hope you guys enjoy it.

→ Reply

isirazeev

2 years ago, # |

"déjà vu", hmmm, something familiar

→ Reply

bever209

2 years ago, # |

Teach me the ways flame :orz:

→ Reply

Surprise_Me

2 years ago, # |

As a tester, I can assure you really good quality problems. The contest in worth spending time. All the setters and testers have put a lot of work and effort. Good luck everyone !!

→ Reply

2 years ago, # |

+11

Hoping I don't feel déjà vu while seeing my rating changes after this contest

→ Reply

k1r1t0

2 years ago, # ^ |

-11

but you had 1725...

→ Reply

2 years ago, # ^ |

I'm referring to the (-109) after said 1725 lol

→ Reply

2 years ago, # ^ |

pheww

→ Reply

amrataansh

2 years ago, # |

+24

On the contest page, duration is shown as 2hrs. Please correct it. flamestorm

→ Reply

PoPularPlusPlus

2 years ago, # |

Why are there at most 1 interactive problem and not 998244352

→ Reply

MohamedAboOkail

2 years ago, # ^ |

-22

I hate Interactive Problems

→ Reply

PoPularPlusPlus

2 years ago, # ^ |

← Rev. 2 →

+48

ok but i don't remember asking it

→ Reply

Xarma

2 years ago, # ^ |

Me too

→ Reply

Golovanov399

2 years ago, # |

+178

Déjà vu theme is a very convenient excuse in case if some of the problems turn out to be well known

→ Reply

2 years ago, # ^ |

+100

We did this intentionally, as it is well-known that all problems are well-known in China

→ Reply

newbie_2022

2 years ago, # |

-18

Score distribution is 250 for problem A, means problem A's difficulty level below 800?

→ Reply

Miyano_Shiho

2 years ago, # ^ |

It's probably gonna be easy, but I don't think it will be rated less than 800. I haven't seen any problems rated below that even if they are very easy

→ Reply

2 years ago, # |

← Rev. 2 →

I think E will be interactive

upd.: happily, it wasn't

→ Reply

rohitchak

2 years ago, # |

+37

→ Reply

Yangster

2 years ago, # |

+11

As a tester, I can snitch that the discord server icon is a picture of an anime girl.

→ Reply

2 years ago, # ^ |

Not just any anime girl.

→ Reply

Miyano_Shiho

2 years ago, # |

Excited!

→ Reply

roy.2

2 years ago, # ^ |

i am too!

→ Reply

Jahongir_hacking

2 years ago, # |

Good luck everyone :)

→ Reply

intrusiv

2 years ago, # |

thank god speedforces

→ Reply

tian_jun_cheng

2 years ago, # |

+11

This is my first time,I'm scard

→ Reply

Aftab_SundarSTEM

2 years ago, # |

← Rev. 2 →

-33

this round is much intresting

→ Reply

absolute-mess

2 years ago, # ^ |

8 downvotes. Does this mean Saarang roasted you?

→ Reply

Cyber_Snake

2 years ago, # |

← Rev. 2 →

-20

→ Reply

_endL

2 years ago, # ^ |

+11

Until you become pupil.

→ Reply

Bungmint

2 years ago, # ^ |

That's funny because I stopped using python for contests after I got out of pupil.

→ Reply

2 years ago, # ^ |

I got to orange in Python but even I gave in eventually

→ Reply

Saurabh_059

2 years ago, # |

Finally my exam is over. Hopefully I will able to solve 2 problem in this contest.

→ Reply

aRamen

2 years ago, # |

it's morbing time

→ Reply

Apoorv_Rathore

2 years ago, # ^ |

+10

hussenberg you seem kinda sus ngl

→ Reply

aRamen

2 years ago, # ^ |

← Rev. 2 →

nah I ain't,I'm just drunk

→ Reply

Apoorv_Rathore

2 years ago, # ^ |

+10

you sussy baka

→ Reply

aRamen

2 years ago, # ^ |

Lol, you sound like one of my friends Btw do you have discord or smth?

→ Reply

Abito

2 years ago, # ^ |

Maybe he's Hank?

→ Reply

dukhi_insaan

2 years ago, # |

How to attempt D question?

→ Reply

bugdone

2 years ago, # ^ |

+50

Read the problem.
Think hard.
Write down the solution.

→ Reply

eklavya_k

2 years ago, # |

whyl i can't register?

→ Reply

hunter_of_alts

2 years ago, # |

yet, another speedforces round?

→ Reply

2 years ago, # ^ |

-22

Competitive programming = speed + knowledge

→ Reply

Ari

2 years ago, # ^ |

+220

→ Reply

abcsumits

2 years ago, # |

I shocked for a sec after seeing 4th problem :)

→ Reply

demadog

2 years ago, # ^ |

Took me a long time to debug, though got the approach early.

→ Reply

abcsumits

2 years ago, # ^ |

i didn't attempted *_*, but after seeing so many submissions it's seems easy .

→ Reply

SalmaHatem_

2 years ago, # |

Problem A is a very greedy !!

→ Reply

Aging1986

2 years ago, # |

+11

Does not have any idea on F. Expect fast editorial.

→ Reply

i.am.pratik

2 years ago, # ^ |

+24

I would say the same for E.

→ Reply

monna4335

2 years ago, # |

+34

Problem A was a great scam :3

→ Reply

mohdikram

2 years ago, # |

← Rev. 3 →

Wanna problem C hint after the contest :(

seem like its hard for me :(

→ Reply

livingstone

2 years ago, # ^ |

i am hard stuck at C for the entire round. Need to learn how to move on to D.

→ Reply

opPO_fan

2 years ago, # ^ |

When you have more than 2 negative or more than 2 positive integers, the answer is NO (think why). Now you can save min(cnt0, 3) zeros and check the condition on array of size less than 10.

→ Reply

chiragxarora

2 years ago, # ^ |

I did the same thing, my logic was, answer is YES if there are >= n-2 zeroes (for n-2 case, sum of non zero ones should be zero). Other than that, only for n=3 and 4 answer is possible otherwise no. Can you give a counter example for this logic?

→ Reply

opPO_fan

2 years ago, # ^ |

I don't think that only for n = 3 and n = 4 the answer is possible.

→ Reply

opPO_fan

2 years ago, # ^ |

-2 -2 -2 you can check this by yourself in submission details.

→ Reply

average_treap_enjoyer

2 years ago, # |

+65

I hate this round

→ Reply

Only_Y

2 years ago, # ^ |

I hate this round!!!

→ Reply

Marky

2 years ago, # |

← Rev. 3 →

+15

What I did during the round. 1% of the time solving A and B - 99% of the time trying to figure out why C kept on failing.

→ Reply

2 years ago, # |

What was the idea behind D? I know it's a binary search, but non of my ideas on how to exclude segments were correct.

→ Reply

2 years ago, # ^ |

Probably it has to do something with a number of numbers that are in range (l, r) for a particular segment, but I couldn't elaborate this idea.

→ Reply

tanmay.raj.29

2 years ago, # ^ |

← Rev. 2 →

Query on segments like [1, x].
Let miss be count of integers between 1 and x, such that they are not present in query result.
For even and odd segment lengths, think about what should be the parity of miss if answer <= x and if answer > x

→ Reply

2 years ago, # ^ |

Explain it further, please, I have so many thoughts on D now and can hardly imagine anything :)

→ Reply

Ignut

2 years ago, # ^ |

My solution:

after each ask count numbers that potentially could be 'x'

let it be cnt

if cnt is odd => 'x' is in our half, otherwise — in second half

continue binary search until l != r

→ Reply

2 years ago, # ^ |

If you don't mind — link your solution, please. So I'll exactly see what is what.

→ Reply

Ignut

2 years ago, # ^ |

+10

Here it is: 162142911

but it is a bit messy so:

Solution

ll t;
cin >> t;
while (t --) {
    ll n;
    cin >> n;

    ll l = 1, r = n;
    while (l != r) {
        ll m = (l + r) / 2;
        ask(l, m);

        ll len = m - l + 1;
        ll cnt = 0;
        for (ll i = 0; i < len; i ++) {
            ll a;
            cin >> a;
            if (a >= l && a <= m)
                cnt ++;
        }

        if (cnt & 1)
            r = m;
        else
            l = m + 1;
    }

    answer(l);
}

→ Reply

2 years ago, # ^ |

Yeah, I see, thanks a lot. Was just a few steps away from observing that

→ Reply

Ignut

2 years ago, # ^ |

-10

thats great, wish you progress :)

→ Reply

2 years ago, # ^ |

Appreciate that!

→ Reply

Keven

2 years ago, # ^ |

binary search in [l, r], set k = (l + r) / 2, then check [l, k], if \sum_{i=l}^{k}[l<=a_i<=k] is odd(number of exchanges in [l, k] modulo 2 equal 1), answer will in [l, k], otherwise [k + 1, r]

→ Reply

2 years ago, # ^ |

Thank you!

→ Reply

Gurpreet_1

2 years ago, # |

-500 incoming

→ Reply

saideira

2 years ago, # |

How to solve problem C?

→ Reply

barun511

2 years ago, # ^ |

If 3 positive or 3 negative, answer is not possible.

Otherwise, brute force.

→ Reply

surbhijain93

2 years ago, # ^ |

I put that logic...still failed..can i show you the code now that the contest has ended?

→ Reply

surbhijain93

2 years ago, # ^ |

← Rev. 5 →

-17

sorry i didn't know there was a spoiler option. :(

→ Reply

MijPeter

2 years ago, # ^ |

+11

put it in spoiler

→ Reply

2 years ago, # ^ |

Hint:Notice that the number of non-zero numbers must be very small.

→ Reply

Hectonit

2 years ago, # ^ |

3sum-closed array has at most 2 negative numbers, and at most 2 positive numbers. Then reduce zeros to some small value, so we can iterate all i, j, k and check all sums.

→ Reply

bashkort

2 years ago, # |

C is pretty strange :)

I hope it will pass

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    map<int, int> mp;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        ++mp[a[i]];
    }
    vector<int> b;
    for (auto [x, y] : mp) {
        y = min(3, y);
        while (y--) {
            b.push_back(x);
        }
    }
    if (sz(b) < 100) {
        set st(all(b));
        for (int i = 0; i < sz(b); ++i) {
            for (int j = i + 1; j < sz(b); ++j) {
                for (int k = j + 1; k < sz(b); ++k) {
                    if (!st.count(b[i] + b[j] + b[k])) {
                        cout << "NO\n";
                        return;
                    }
                }
            }
        }
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}

→ Reply

MijPeter

2 years ago, # ^ |

Yea should pass, why not

→ Reply

jeal0uspengu1n

2 years ago, # ^ |

← Rev. 2 →

Umm... we can never have more than 2 positive/negative integers?? So if the count of odd or neg numbers is >2 then the answer will be "NO"

→ Reply

MijPeter

2 years ago, # ^ |

← Rev. 2 →

His/her brute force will catch it though :)

→ Reply

jeal0uspengu1n

2 years ago, # ^ |

Yeah, I mean ofc it will pass, I was just mentioning why his solution passed (^^ゞ

→ Reply

Aravind

2 years ago, # ^ |

I don't know C++ but it looks like he's applying Brute force only if size of array is less than 100 or else he is printing NO ig

→ Reply

physics0523

2 years ago, # |

+12

Harder Div2, I thought I was accidentally solving some D1Bs and D1Cs during the contest...

→ Reply

villizain6

2 years ago, # |

wandering here after solving a,b,c :P

→ Reply

why_I

2 years ago, # |

How to solve D?

→ Reply

2 years ago, # ^ |

Hint

→ Reply

mihir2808

2 years ago, # ^ |

can u point mistake in my code. Dude I did the same thing but showling TLE

→ Reply

2 years ago, # |

+27

How to solve E lol

→ Reply

2 years ago, # ^ |

← Rev. 3 →

+24

Hi! It's my first time for me solving E, i'm very happy, so lemme write my solution;)

Let's notice that if we are given a certain permutation b we can only change a to b when for each element a[i] if j is the position we should move a[i] to, b[j] <= a[i] + s:

If the condition is not true (for example for a[i], if a[i] should be on j-th place) — then we can't move a[i] to its needed place, because if we can, then we do it on move <=i therefore other element we swap (a[j]) has a difference with a[i] no more than s, but a[j] > a[i] + s (contradiction)

If the condition is true for each a[i], notice that we can consequently move a[i] to its needed position on a[i]-th move (legally).

So let's find all permutations which suit the condition:

Firstly, for each a[i] if b[i] is already not -1, then b[i] must be no more than a[i] + s (condition 1), otherwise answer is 0 (same reasons as in 2nd paragraph)

Assume 1st condition is true: lets say that we have c[1] < c[2] < ... < c[x] — elements of array a, under theis indexes in array B stand -1s. And we have d[1] < d[2] ... < d[x] — elements we have to insert in B on places of -1s.

After substracting s from each d[i], a suitable permutation will be when for every d[j] standing under element Y from A, y>=d[j]. (same reasons as in 2nd paragraph)

So for each d[i] we can find under how much elements of C it can stand (when I say stand under, i mean that they have same index, it's just my visualisation that array B stands under array A) using binary search Let's notice that if b[j] > b[i], on every position we can put b[j], we can also put b[i]. So let's choose a suitable permutation consequently choosing a place for d[1], then for d[2], and so on. if we can place d[i] onto z places, then if we already placed first i-1 elements of D, then we can choose a place for d[i] by z-(i-1) variants.

Let's notice that if we can put d[i] on z<i places, then we can place first i elements of D on z<i places (contradiction, so answer is 0) (condition 2)

In the other case, if d[i] can be put on e[i] places, answer is (e[1]-0) * (e[2] — 1) * ... * (e[i] — (i-1)) * ... * (e[n] — (n-1)) (mod 998244353).

Sorry for my bad english, of if you didn't understand something) i hope you will understand me))

→ Reply

2 years ago, # ^ |

With your explanation and code,I get it eventually :) Thank you so much!!

→ Reply

2 years ago, # ^ |

+23

You are welcome! I'm glad somebody understood me;))

→ Reply

TheHokage

2 years ago, # |

+25

interactive = binary search

→ Reply

hxu10

2 years ago, # |

+39

I learned three lessons from this contest

Read the problems carefully !

→ Reply

aufannn

2 years ago, # ^ |

I misread the problem C, I thought one fulfilling pair was enough.

→ Reply

hxu10

2 years ago, # ^ |

Me too. I misread problem C until the problem setter made the announcement. And, I misread problem E again. I solved problem E immediately after the contest.

→ Reply

bhoomikacherry

2 years ago, # |

Ok I need to know, what was déjà vu in this contest?

→ Reply

2 years ago, # ^ |

← Rev. 2 →

I think that the problems had classic prototypes like:

A — xoring to find the unique number

C — 2Sum or 3Sum problem

F — reversing an array via Implicit Treap

→ Reply

2 years ago, # ^ |

I am not sure though whether knowing about these prototypes can help you solve today's problems faster :)

→ Reply

bhoomikacherry

2 years ago, # ^ |

Oh ok, I see. Thanks

→ Reply

happy_new_year_2022

2 years ago, # ^ |

E — reversing an array using impicit treap

come again?

→ Reply

TimDee

2 years ago, # ^ |

3-SUM was reference to recent div4, PermutationForces was reference to one of recent problems too (don't remember the contest), pretty much sure all other problem names you could've meet before.

→ Reply

2 years ago, # ^ |

3Sum and 2Sum are old problems: https://leetcode.com/problems/3sum/, https://leetcode.com/problems/two-sum/

→ Reply

TimDee

2 years ago, # ^ |

Yes, but context was about recent div4 because Flamestorm was one of the setters, dude

→ Reply

2 years ago, # ^ |

My bad, I did not know

→ Reply

TimDee

2 years ago, # ^ |

no problems, congrats with performing great today :)

→ Reply

2 years ago, # ^ |

+25

We have too much dignity to use references to Leetcode problems.

→ Reply

Rudro25

2 years ago, # |

a is 3SUM-closed if for all integers..... anyone missed the all integer part like me.. That's created the problem more hard :'( even is that possible with the same constraints ?

→ Reply

bhoomikacherry

2 years ago, # ^ |

What else would it be? For even one such $$$i, j, k$$$?

→ Reply

Rudro25

2 years ago, # ^ |

how u find there have at least one i,j,k as if a[i]+a[j]+a[k] also exist in array. ?

→ Reply

wyhong3103

2 years ago, # ^ |

one hour is wasted on that thing, I really gotta read the problem statement carefully the next time.

→ Reply

sjc061031

2 years ago, # |

+64

I solve F while using only 2n operations. And I don't have any idea why the limit is n^2.

→ Reply

bashkort

2 years ago, # ^ |

it's very sad that your rating is 2100, not 2099

→ Reply

sjc061031

2 years ago, # ^ |

-39

I actually use sjcsjcsjc for Div1 contest.

2100 isn't my real rating lol.

(Sorry for violating the rules :( )

→ Reply

om1429888

2 years ago, # ^ |

+11

ded after looking at ur real rating.

→ Reply

sjc061031

2 years ago, # ^ |

+19

I waste too much time because of misreading the statement of E so that I didn't have time thinking about G.

Anyway, the problems are very impressive and a bit more difficult than normal Div2. Really like this contest.

→ Reply

OhLee

2 years ago, # |

← Rev. 2 →

It would be nice if someone could look at my submission for the interactive problem (Java). It was my first interactive problem and I think I did something wrong with the queries / flushing, my submission didn't do anything (my testing did work, think the solution was correct). 162145333

→ Reply

i.am.pratik

2 years ago, # |

+29

I liked problem D. Thanks to the authors for the contest.

→ Reply

prayas123

2 years ago, # ^ |

Good problem..but number of queries was a direct hint to binary search..If number of queries were hidden,it would have been a even better problem.

→ Reply

2 years ago, # ^ |

If they hid number of queries, one would just get WA without knowing why?

→ Reply

thesinhajee

2 years ago, # |

← Rev. 2 →

For C, there can be atmost 4 non-zero numbers(say m), for the given condition to satisfy.

For, m=4, there can be only 2 forms of numbers — a,-a,b,-b and 3a,a,-a,-a. Can there be any other kind of arrangement?

Thanks in advance :')

→ Reply

cleanser

2 years ago, # ^ |

Failed systest because I didn't see the 3a, a, -a, -a case. :(

→ Reply

thesinhajee

2 years ago, # ^ |

:'(

I was taking different cases for proving that there isn't any arrangement of 5 numbers possible and stumbled upon this case. Although, I skipped its implementation and applied a general implementation for n=4. Implementing different cases separately wasn't necessary

→ Reply

cleanser

2 years ago, # ^ |

Yea I didn't include the m=4 option at first and WA'd, then by messing around, found the -b, -a, a, b case and just submitted it and passed pretests so I didn't bother looking at it again.

→ Reply

JCLinux

2 years ago, # ^ |

So do I

→ Reply

dukhi_insaan

2 years ago, # ^ |

-3a -a a a

→ Reply

thesinhajee

2 years ago, # ^ |

Replace a with -a, this isn't a new case.

→ Reply

anucolo

2 years ago, # |

← Rev. 2 →

-10

#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

Why does the presence of this line give idleness limit exceeded?

→ Reply

2 years ago, # ^ |

Run your program with and without it and you will see

→ Reply

xericha

2 years ago, # ^ |

It shouldn't, however if you defined "endl" as "\n" it will because \n does not flush the stream and you were explicitly asked to flush your streams.

however, if you remove that def, the streams are flushed automatically https://stackoverflow.com/a/31165481/

→ Reply

l0TA

2 years ago, # |

+10

the problem statements robbed me (" _ ")

→ Reply

Yammer

2 years ago, # |

As a tester, I'm very glad to participate this contest,which tell me i am lacking for training

→ Reply

Heisenberg_71

2 years ago, # |

← Rev. 4 →

+19

Problem D:

Binary Search: Bro.

Interactive Problem: Yea, bro.

Binary Search: Close your eyes, bro.

Interactive Problem: Ok, bro.

Binary Search: What do you see, bro?

Interactive Problem: I see you, bro.

Binary Search: Broo!!

Interactive Problem: Bro.

→ Reply

Aravind

2 years ago, # |

For A why is it always first element? Although I used brute force after long time by seeing the constraints

→ Reply

HaccerKat

2 years ago, # ^ |

You can print any of the elements

→ Reply

snowysecret

2 years ago, # ^ |

I think it can be any element

→ Reply

Aravind

2 years ago, # ^ |

WHY???!!!

→ Reply

snowysecret

2 years ago, # ^ |

Let the xor of original array = $$$x$$$. After adding $$$x$$$, xor of the new array = $$$0$$$. Therefore for all inputs the xor of the array equals $$$0$$$.

So, now you want to find any $$$x$$$ such that $$$x$$$ = [xor of the rest of the array]. This is true for any $$$x$$$ present in the array because $$$x$$$ xor the rest of the array is $$$0$$$. Hope that helps.

→ Reply

EmilyBloom

2 years ago, # |

+13

I feel this was a perfect contest. Also problem A feels like a troll problem.

→ Reply

_TOBapNw_

2 years ago, # |

I spent even more time on B or C than D...

And I get many "WA 2"s

→ Reply

2 years ago, # |

← Rev. 2 →

For anyone wondering why they got TLE on test 13 of problem C, I suggest reading this and noting that A[0] = 107897 — commiserations if this is you and you've never heard of this phenomenon before; I guess you won't make that mistake again.

→ Reply

Jon_Snow

2 years ago, # ^ |

Can you elaborate a lil?

→ Reply

2 years ago, # ^ |

I don't know specifically what's changed from GCC 17 to GCC 20, but I can make an educated guess. From the blog I quote:

It turns out the right prime depends on the compiler version: for gcc 6 or earlier, 126271 does the job, and for gcc 7 or later, 107897 will work. Run the code below in Custom Invocation and see what output you get.

I suspect that the hash function for unordered map / unordered set has changed from GCC 17 to GCC 20, and now in order to hack it a different prime is required.

→ Reply

Yakumo_Ran

2 years ago, # |

← Rev. 2 →

I love problem D and E, they're quite nice. I enjoy the feeling of finding an interesting conclusion and solve the problem without a long code. However, I think B is not so good because of the weak samples. A k=1 sample can really help a lot. Anyway, love this round very much!

→ Reply

Jon_Snow

2 years ago, # |

My code for 3rd problem got accepted in C++20 but shows tle for the same code in c++17 I lost nearly 18 points due to this. What should I do?

→ Reply

Juanm1

2 years ago, # ^ |

+11

dont use unordered map

→ Reply

xvv

2 years ago, # |

Any hint for E? Spent more than an hour. Don't wanna ruin it by directly reading the solution.

→ Reply

2 years ago, # ^ |

Hint 1

Hint 2

→ Reply

mc_rodrix99

2 years ago, # |

Can anyone tell me why the testcase: n = 6 ar = [1,2,3,4,5,6] the answer is NO in the problem C? if 1 + 2 + 3 == 6

→ Reply

2 years ago, # ^ |

Because (for example) 4 + 5 + 6 = 15, and 15 is not in the array.

→ Reply

2 years ago, # ^ |

See the announcement during the round.

→ Reply

hxu10

2 years ago, # |

If problem C change the statement from "all (i,j,k) pairs must satisfy" to "one (i,j,k) is enough". What is the most optimal time complexity? Can this problems solve by O(n), O(nlgn) or O(n^2)?

→ Reply

tch1cherin

2 years ago, # ^ |

← Rev. 3 →

It's possible to solve it in $$$\mathcal{O}(n ^ 2 \log n)$$$ with std::map or $$$\mathcal{O}(n ^ 2)$$$ with std::unordered_map.

Iterate from the end. In the map $$$cnt$$$ for each possible $$$s$$$ store the number of pairs $$$(j, k)$$$ such that $$$j < k$$$, $$$a_j + a_k = s$$$ and $$$j > i$$$ where $$$i$$$ is the current position. Then, bruteforce $$$l$$$. If $$$cnt_{a_l - a_i} > 0$$$, print YES. If we haven't found such pair print NO.

UPD1.

Code

int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
    cin >> a[i];

bool good = false;
unordered_map<int, int> cnt;
for (int i = n - 1; i >= 0; i--) {
    for (int l = 0; l < n; l++)
        if (cnt[a[l] - a[i]] > 0)
            good = true;

    for (int j = i + 1; j < n; j++)
        cnt[a[i] + a[j]]++;
}

if (good)
    cout << "YES" << endl;
else
    cout << "NO" << endl;

UPD2. You can use bitset of size $$$2 \cdot 10^9$$$ instead of unordered_map and get better constant factor.

→ Reply

The_Alchemist

2 years ago, # |

Has anyone solved C just after the announcement during the contest?

→ Reply

save_earth

2 years ago, # |

-41

the third problems was wrong and how it impossible with 2e5 and t <= 1000 ??

→ Reply

adityagamer

2 years ago, # ^ |

Did you notice in last line of input format: "It is guaranteed that the sum of n across all test cases does not exceed 2*10^5" Its common in codeforces

→ Reply

save_earth

2 years ago, # ^ |

did you check testcases in problem C? there is t equal to 1, if t will be 1000 and each n will be equal 2e5 i sure that all solutions will be TLE)))

→ Reply

adityagamer

2 years ago, # ^ |

If t will be 1000 and all n be equal 2e5 then sum of n over all test cases will be 2e8 which is not possible due to constraints

→ Reply

save_earth

2 years ago, # |

-27

worst contest i have ever entered because the third problem's solution not logical

→ Reply

2 years ago, # ^ |

Why do you think the solution is wrong / not logical?

→ Reply