Codeforces Round 914 (Div. 2)

11 месяцев назад, # |

+11

C>D

→ Ответить

iiand

11 месяцев назад, # |

+17

Cool problems, especially $$$C$$$(with idea that we must check only $$$K \leq 2$$$) and $$$D$$$.

→ Ответить

phukaoz

11 месяцев назад, # ^ |

I should do D first T-T.

→ Ответить

tgp07

11 месяцев назад, # |

Cool problems and cool starting time

→ Ответить

Something.

11 месяцев назад, # |

A > C > B

→ Ответить

ismoilmirzouz

11 месяцев назад, # ^ |

for me C>A>B

→ Ответить

blaze

11 месяцев назад, # |

Found the error in D1 one second after contest ended. Nice!

→ Ответить

NovusStellachan

11 месяцев назад, # |

Can anyone tell me if this works for F? I ran out of time to implement in contest.

First we build a directed graph $$$G$$$ whose vertices represent paths in the tree as follows:

For each vertex $$$u$$$ and number $$$0 \leq i \leq 20$$$ we construct a vertex corresponding to the path between $$$u$$$ and its $$$2^i-1$$$th ancestor along the path (LCA stuff). We draw directed edges from the "vertex" $$$[u, p^{2^i}(u))$$$ to vertices $$$[u, p^{2^{i-1}}(u))$$$ and $$$[p^{2^{i-1}}(u), p^{2^{i}-1}(u))$$$.

This directed graph $$$G$$$ has $$$\leq 20n$$$ vertices, each of which has at exactly two edges going outward. So the graph has at most $$$40n$$$ edges. Create another copy of such a graph, but now with edge directions reversed, call it $$$G'$$$. Finally consider the $$$1$$$-vertex paths in both graphs $$$G, G'$$$ and merge them (they are one single vertex now).

This new graph $$$G+G'$$$ has $$$\leq 40n$$$ vertices and $$$\leq 80n$$$ edges. Now for each of the $$$m$$$ conditions we do the following. Suppose that the condition is of the first kind, the second kind is analogous. Split the paths from $$$[a, c)$$$ and $$$(c, b]$$$ into at most $$$40$$$ vertices of $$$G$$$. Draw a directed edge from vertex $$$c$$$ to each of these $$$40$$$ vertices of $$$G$$$ (in the opposite direction if $$$G'$$$ were considered).

Now just check if the $$$G+G'$$$ graph has a topological sort. If it does, then the order of $$$1, 2, \dots, n$$$ in that is the answer, otherwise there is no answer at all. Time complexity of above is $$$\mathcal O((n+m)\log n)$$$

→ Ответить

willy108

11 месяцев назад, # ^ |

Yes, this ought to work.

→ Ответить

NovusStellachan

11 месяцев назад, # ^ |

ahghghgh thank you for confirming, after bricking C, D1, D2 I read F in last 30 min and figured this out but hands too slow ugugugughghh

→ Ответить

vitosevskich

11 месяцев назад, # |

← Rev. 2 →

+14

What? D1 is actually EJOI 2020 Day 1 Task "Exam" Subtask 6.

→ Ответить

shenzihan

11 месяцев назад, # |

+15

datastructureforces

→ Ответить

Mayank_Pushpjeet

11 месяцев назад, # |

C was cool, D1, D2 were also good, crossing 1800 barrier for the 1st time after so long from being stuck and lot of demotivation.

→ Ответить

Scyther_07

11 месяцев назад, # ^ |

Congo man!

→ Ответить

Mayank_Pushpjeet

11 месяцев назад, # ^ |

Thanks man !

→ Ответить

eyfmharb

11 месяцев назад, # |

+26

I absolutely totally did not stare at $$$C$$$ for $$$30$$$ minutes with no ideas until I realised you can make it $$$0$$$ in $$$3$$$ trials.

→ Ответить

Red0

11 месяцев назад, # ^ |

← Rev. 2 →

I absolutely did not spend 20 minutes staring at my solution for C without realizing that it works.

→ Ответить

alpha1215

11 месяцев назад, # |

nice contest i enjoyed the problem thanks to authors. First time solved 4 problems

→ Ответить

electric_boogaloo

11 месяцев назад, # |

← Rev. 2 →

C is such a troll problem with $$$K$$$ up to $$$10^9$$$, you could have taken it a step further and not include a case with $$$K = 3$$$ in the samples. Not a bad problem though.

D was okay, just hoping I don't get FSTed.

Looks like I didn't get FSTed after all. Is there an easier way to do D2?

What I did:

→ Ответить

ShivanshJ

11 месяцев назад, # ^ |

Yes there is an easier way, Let $$$R(i,x)$$$ denote the smallest index $$$j$$$ such that $$$j \ge i$$$ and $$$a[j] = x$$$, similarly $$$L(i,x)$$$ denotes the largest index $$$j$$$ such that $$$j \le i $$$ and $$$a[j] = x$$$.

Now, the answer is "YES" iff for every element $$$i$$$,

1) $$$Min(b[i],b[i+1]...b[R(i,b[i])] \ge b[i]$$$

2) $$$Max(a[i],a[i+1]...a[R(i,b[i])] \le b[i]$$$

1) $$$Min(b[i],b[i-1]...b[L(i,b[i])] \ge b[i]$$$

2) $$$Max(a[i],a[i-1]...a[L(i,b[i])] \le b[i]$$$

→ Ответить

electric_boogaloo

11 месяцев назад, # ^ |

Yeah, this looks like a more concise way to do it. Basically, in my solution I'm checking the same conditions, just in a more roundabout way (it was heavily influenced by my brute force solution of D1)

I'm curious what is the authors intended solution (it might as well be the same as the one that you have proposed)

→ Ответить

11 месяцев назад, # ^ |

236555393 Though I'm not sure about the time complexity.

→ Ответить

11 месяцев назад, # ^ |

Hacked. But I think you can optimized it a bit and pass.

→ Ответить

11 месяцев назад, # ^ |

I was thinking it's time complexity to be $$$O(n^{2})$$$ in worst case.

→ Ответить

11 месяцев назад, # ^ |

Your solution solved my test case in about 6 seconds while most of the N^2 solution takes more than 1 minutes.

That's why I think your solution might pass if you can somehow optimized it.

→ Ответить

tgp07

11 месяцев назад, # ^ |

I did something similar for D2. It barely passed in time lol

→ Ответить

vaal

11 месяцев назад, # |

+11

Was that for only me initially the diagram for problem A was incorrect?

→ Ответить

vitosevskich

11 месяцев назад, # ^ |

Yes it was. They could've announced it.

→ Ответить

tickbird

11 месяцев назад, # |

couldn't solve c

even though found case work k >= 3, k == 1, k == 2

too unfortunate

→ Ответить

phsads

11 месяцев назад, # |

A is miles harder than B and C for me lol (and maybe even D1 but i didnt have enough time)

→ Ответить

RunAt

11 месяцев назад, # |

Wow A was unusually difficult to understand and implement.

→ Ответить

fernandezpalomojosue

11 месяцев назад, # |

Weak pretest on A

→ Ответить

bestial-42-centroids

11 месяцев назад, # |

← Rev. 2 →

Congratulations to the authors for this great round :))

As usual, here is my advice about the problems (not correlated to my performance)

I think the only downside of this round is that the gap between D2 and E was quite high but I don't know if that's a really big deal as usually E don't get that many ACs anyway.

Looking forward to compete in another of your rounds :)

→ Ответить

oogerbooger

11 месяцев назад, # |

I couldn't do problem A, what a shame.

→ Ответить

anil9717

11 месяцев назад, # ^ |

‘Think of rising higher. Let it be your only thought. Even if your object be not attained, the thought itself will have raised you.’ — Thirukural

→ Ответить

BF_OF_Priety

11 месяцев назад, # ^ |

in last div-3 I couldn't solve $$$C$$$ sometimes these things happen

→ Ответить

PiscesDream

11 месяцев назад, # |

Not sure you feel the same. But for me, B > A and C > D. lol

→ Ответить

11 месяцев назад, # ^ |

Can you give me an edge case for this solution why it is not working B

→ Ответить

PiscesDream

11 месяцев назад, # ^ |

In general, I will write a data generator and a brutal force baseline solution to test it. I did that sometimes in the contest (like for the C today), not a good way but the last resort to self-debug.

→ Ответить

11 месяцев назад, # |

how to solve c when k = 2?

i tried to take every element of a with the nearest abs(a[i] — a[j]) but it gave wa

→ Ответить

iiand

11 месяцев назад, # ^ |

Just check all pairs. if you have $$$f = abs(a[i] - b[j])$$$, you current answer must be $$$answer = min(answer, f, \text{first_el_greater}(f) - f, f - \text{last_el_less}(f))$$$. The last two can be calculated using binary_search = std::lower_bound. So $$$O(n^2 \log n)$$$

→ Ответить

11 месяцев назад, # ^ |

oh thanks alot i tried to do this in one of my submissions but i was only looking for the adj elements thanks

→ Ответить

amos_aidoo

11 месяцев назад, # ^ |

maybe you can get a zero if any difference already exists

→ Ответить

11 месяцев назад, # ^ |

i already handled this by setting the default answer to be min absolute value

→ Ответить

Suri429

11 месяцев назад, # ^ |

make a binary search back in array for that (a[i]-a[j]) to find best move in next run.

→ Ответить

https://codeforces.net/contest/1904/submission/236573798

11 месяцев назад, # ^ |

ok thanks alot

→ Ответить

fengyss

11 месяцев назад, # ^ |

← Rev. 2 →

before it, sort(a),then try every s=(a[i]-a[j]), after it, look for minimize(a[i]-s). every step should update answer.

→ Ответить

alpha1215

11 месяцев назад, # ^ |

brute force every possible |Ai — Aj| think of bs

→ Ответить

kriepiekrollie

11 месяцев назад, # |

AdamantChicken2 didn't participate :(

→ Ответить

fengyss

11 месяцев назад, # |

I have to say it is a little late for me, but I outdo myself. Unbelievable!!!!

→ Ответить

EN_SA

11 месяцев назад, # |

← Rev. 2 →

+20

You changed the order of picture of problem A and didn't send a notification. Is it because it's not statement?

→ Ответить

EN_SA

11 месяцев назад, # ^ |

+11

Additionally, I feel that the description of the new way of movement of the knight in statement A is inappropriate.

I think we should write statement even someone who doesn't know how the knight in the original chess moves can understand how the knight moves with that statement alone.

I think the current statement is open to misunderstanding.

→ Ответить

RD_TheCoder

11 месяцев назад, # ^ |

I left the contest for this reason.. After some min i refreshed and saw the change (:

→ Ответить

Sokol080808

11 месяцев назад, # |

+24

oursaco https://ejoi2020.ge/static/assets/Day1/Problems/Exam.pdf Problem D is a subgroup of this task

→ Ответить

oursaco

11 месяцев назад, # ^ |

Sorry, we were not aware of this :(

→ Ответить

g2-g4

11 месяцев назад, # |

amazing problems! but E and F is too hard for div. 2 (

→ Ответить

shviv1

11 месяцев назад, # |

← Rev. 2 →

Nice problemset

→ Ответить

helpmeimprpve

11 месяцев назад, # |

is there a hack phase ?

→ Ответить

EN_SA

11 месяцев назад, # ^ |

→ Ответить

Ladamalina

11 месяцев назад, # |

Solved D1+D2 just 5 seconds after final :'(((

→ Ответить

arash.

11 месяцев назад, # |

E is a really standard problem

→ Ответить

ShivanshJ

11 месяцев назад, # ^ |

Can you give a slight hint?

→ Ответить

arash.

11 месяцев назад, # ^ |

+23

Solve it offline and do a dfs.

When you are in vertex v try to have a segment tree maintaining the distances of other vertices from v.

→ Ответить

BrAin

11 месяцев назад, # |

Anyone plz give the idea of A

→ Ответить

anil9717

11 месяцев назад, # ^ |

Let Sq be set of positions from where queen(xq,yq) can be attacked. (xq+a,xq-b) is one such postion. Let Sk be set of positions from where king(xk,yk) can be attacked.

Find the size of intersection set of Sq and Sk.

→ Ответить

ma_da_fa_ka

11 месяцев назад, # ^ |

True, couldn't find better way to implement this

→ Ответить

vstiff

11 месяцев назад, # ^ |

https://codeforces.net/contest/1904/submission/236576012 :)

→ Ответить

cf_my_gf

11 месяцев назад, # |

why my solution for B gets wrong

https://codeforces.net/contest/1904/submission/236570576

→ Ответить

Hasib.Nabid

11 месяцев назад, # |

Couldn’t solve A pajn. Nice problemset tho

→ Ответить

kyuukyuusha

11 месяцев назад, # |

+11

Can someone hack this $$$O(n^2)$$$ solution for D2? https://codeforces.net/contest/1904/submission/236575342

I feel like it shouldn't work.

→ Ответить

kriepiekrollie

11 месяцев назад, # ^ |

I hacked it

→ Ответить

LaughingBuddha

11 месяцев назад, # ^ |

How can we hack any solution now?

→ Ответить

aureliony

11 месяцев назад, # ^ |

← Rev. 2 →

Unfortunately they made uphacking available only for div1 participants (1900+)

→ Ответить

mnasser02

11 месяцев назад, # |

Spoiler

→ Ответить

ALnQ417

11 месяцев назад, # ^ |

+27

Skill issue tbh

→ Ответить

Charararar

11 месяцев назад, # ^ |

→ Ответить

avighnakc

11 месяцев назад, # ^ |

Np, happens

→ Ответить

Prajwalrayal

11 месяцев назад, # |

This failed on system testing Submission can anyone tell me what is the mistake? n^2logn solutions were not meant to pass for this problem or something else ?

→ Ответить

https://codeforces.net/contest/1904/submission/236581716

11 месяцев назад, # ^ |

just changing $$$j$$$ from $$$i+1$$$ to $$$n$$$ instead of $$$0$$$ to $$$n$$$ in case $$$k=2$$$. your code runs in 1400 ms. 236577461

→ Ответить

Prajwalrayal

11 месяцев назад, # ^ |

Bruh :) this small mistake took me from Rank 1700 to 2800, Thanks!!

→ Ответить

LaughingBuddha

11 месяцев назад, # |

System testing completed for this contest? Any idea anyone?

→ Ответить

great_fortune

11 месяцев назад, # |

236573136 I believe that my D1 solution shouldn't work in D2 (tl) on max test like this:

10 9 8 7 6 5 4 3 2 1

10 10 10 10 10 10 10 10 10 10

But it gets accepted with 187/4000ms

can someone try to hack it with

200000

200000 199999...

200000 200000... pls? I have some kind of problem with hacking.

→ Ответить

TryingToBeEnough

11 месяцев назад, # ^ |

+10

Hacked. Really weak test data in D2.

→ Ответить

great_fortune

11 месяцев назад, # ^ |

Thanks TryingToBeEnough!

so....

REALLY weak D2 tests lol

→ Ответить

great_fortune

11 месяцев назад, # ^ |

i wonder how many n^2 "solutions" got accepted

→ Ответить

oursaco

11 месяцев назад, # ^ |

Sorry for weak tests. We managed to kill some optimized n^2 solutions during testing, but seems it was not enough :(

→ Ответить

aureliony

11 месяцев назад, # ^ |

← Rev. 2 →

My O(n^2) solution works as well, should have submitted during contest :(

→ Ответить

11 месяцев назад, # ^ |

Hacked. sorry

→ Ответить

Deep1809

11 месяцев назад, # ^ |

I had same doubt, many O(n^2) solution worked in D2, example is 236567513

Can someone please verify if it can be hacked too with these given testcases

→ Ответить

11 месяцев назад, # ^ |

Hacked.

→ Ответить

Kawaii

11 месяцев назад, # |

-6

why problem A is so hard

→ Ответить

Rakesh_898

11 месяцев назад, # ^ |

I think the given picture made it so hard

→ Ответить

biomat

11 месяцев назад, # ^ |

← Rev. 2 →

I don't think it was that hard but I really started lauging when I understood I have fallen into the well set airhead trap...

→ Ответить

defnotmee

11 месяцев назад, # |

Didnt particularly like the contest, too structure heavy for me. A-D were easy and E was annoying. C also had a stupid corner that wasnt in the samples and A had the wrong picture. F also looks annoying but ill check edi to see if its cool.

→ Ответить

Igor_Parfenov

11 месяцев назад, # ^ |

Why do you look at pictures?)

I usually don't look at samples.

→ Ответить

defnotmee

11 месяцев назад, # ^ |

+23

My sol was bugged so i thought i misunderstood the problem, it ended up making me understand the problem less.

→ Ответить

cosenza

11 месяцев назад, # ^ |

what was the corner case on C?

→ Ответить

Igor_Parfenov

11 месяцев назад, # ^ |

For me it was "no operations, the answer is in initial array".

→ Ответить

defnotmee

11 месяцев назад, # ^ |

yeah, this

→ Ответить

LaughingBuddha

11 месяцев назад, # |

← Rev. 2 →

Can someone hack my D1? 236559856

Pretests were damn weak it seems.

Testcase —

→ Ответить

eklavya_k

11 месяцев назад, # |

5 solves for the first time in a div 2

→ Ответить

elseecay

11 месяцев назад, # |

Why doesnt work? C

    if (k == 2)
    {
        sort(fullrng(arr));
        i64 m = numeric_limits<i64>::max();
        
        update_min(m, *std::min_element(fullrng(arr)));

        for (int i = 1; i < arr.size(); ++i)
            update_min(m, arr[i] - arr[i - 1]);

        for (int i = 0; i < arr.size(); ++i)
        {
            for (int j = i + 1; j < arr.size(); ++j)
            {
                auto d = arr[j] - arr[i];
                auto lbnd = lower_bound(fullrng(arr), d);
                update_min(m, abs(d - *lbnd));
                if (++lbnd < arr.end())
                    update_min(m, abs(d - *lbnd));
            }
        }

        solved(m);
    }

→ Ответить

elseecay

11 месяцев назад, # ^ |

got it, if element not present lower bound returns element that greater

→ Ответить

Blagoj

11 месяцев назад, # |

Surprisingly good contest! Good job!

→ Ответить

34z12000

11 месяцев назад, # ^ |

It was kind of boring

→ Ответить

Blagoj

11 месяцев назад, # ^ |

+20

Hey, anyone can have different opinions

→ Ответить

34z12000

11 месяцев назад, # ^ |

-10

Yes, why not

→ Ответить

Jhin

11 месяцев назад, # |

Not sure why everyone thought B was that easy, I solved it but it took longer than A and C.

if they didn't mess up the photos in A I would have solved it faster, I stared at the wrong picture for 10 minutes wondering if I became so stupid to not understand an A problem after not solving problems for more than 2 months

→ Ответить

Blagoj

11 месяцев назад, # ^ |

Maybe B wasn't that easy but you just needed one observation to solve it

→ Ответить

11 месяцев назад, # ^ |

Can you give me an edge case for this solution why it is not working B

→ Ответить

EvenToWorldFinal

11 месяцев назад, # |

Great contest! Lost some ratings tho...

→ Ответить

dolphin2025

11 месяцев назад, # |

Why does my submission https://codeforces.net/contest/1904/submission/236601220 pass tests? It fails when the difference between two elements is exactly an element in the array. Example:

Input:

1
2 2
1 2

Output:

troll

Expected Output:

→ Ответить

11 месяцев назад, # ^ |

Seems like missing test cases.

If k is 2 and there exist three elements a, b, c in the list such that a + b = c, the answer should be 0.

→ Ответить

dolphin2025

11 месяцев назад, # ^ |

Exactly ...

BTW, how did hack it? I tried to but couldn't find an option anywhere.

→ Ответить

11 месяцев назад, # ^ |

I heard that it is only open to people with rating 1900+

→ Ответить

11 месяцев назад, # ^ |

Can you give me an edge case for this solution why it is not working B

→ Ответить

11 месяцев назад, # ^ |

← Rev. 2 →

You can try this case

1
6
1 1 1 1 3 6

The correct answer will be

5 5 5 5 5 5

→ Ответить