Codeforces Round 914 (Div. 2)

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

+11

C>D

→ Ответить

iiand

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

+17

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

→ Ответить

phukaoz

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

I should do D first T-T.

→ Ответить

tgp07

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

Cool problems and cool starting time

→ Ответить

Something.

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

A > C > B

→ Ответить

ismoilmirzouz

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

for me C>A>B

→ Ответить

blaze

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

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

→ Ответить

NovusStellachan

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

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

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

Yes, this ought to work.

→ Ответить

NovusStellachan

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

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

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

← Rev. 2 →

+14

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

→ Ответить

shenzihan

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

+15

datastructureforces

→ Ответить

Mayank_Pushpjeet

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

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

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

Congo man!

→ Ответить

Mayank_Pushpjeet

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

Thanks man !

→ Ответить

eyfmharb

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

+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

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

← Rev. 2 →

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

→ Ответить

alpha1215

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

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

→ Ответить

electric_boogaloo

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

← 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

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

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

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

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)

→ Ответить

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

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

→ Ответить

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

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

→ Ответить

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

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

→ Ответить

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

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

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

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

→ Ответить

vaal

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

+11

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

→ Ответить

vitosevskich

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

Yes it was. They could've announced it.

→ Ответить

tickbird

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

couldn't solve c

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

too unfortunate

→ Ответить

phsads

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

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

→ Ответить

RunAt

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

Wow A was unusually difficult to understand and implement.

→ Ответить

fernandezpalomojosue

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

Weak pretest on A

→ Ответить

bestial-42-centroids

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

← 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

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

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

→ Ответить

anil9717

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

‘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

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

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

→ Ответить

PiscesDream

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

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

→ Ответить

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

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

→ Ответить

PiscesDream

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

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.

→ Ответить

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

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

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

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)$$$

→ Ответить

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

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

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

maybe you can get a zero if any difference already exists

→ Ответить

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

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

→ Ответить

Suri429

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

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

→ Ответить

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

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

ok thanks alot

→ Ответить

fengyss

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

← 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

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

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

→ Ответить

kriepiekrollie

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

AdamantChicken2 didn't participate :(

→ Ответить

fengyss

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

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

→ Ответить

EN_SA

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

← 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

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

+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

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

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

→ Ответить

Sokol080808

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

+24

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

→ Ответить

oursaco

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

Sorry, we were not aware of this :(

→ Ответить

g2-g4

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

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

→ Ответить

shviv1

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

← Rev. 2 →

Nice problemset

→ Ответить

helpmeimprpve

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

is there a hack phase ?

→ Ответить

EN_SA

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

→ Ответить

Ladamalina

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

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

→ Ответить

arash.

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

E is a really standard problem

→ Ответить

ShivanshJ

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

Can you give a slight hint?

→ Ответить

arash.

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

+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

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

Anyone plz give the idea of A

→ Ответить

anil9717

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

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

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

True, couldn't find better way to implement this

→ Ответить

vstiff

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

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

→ Ответить

cf_my_gf

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

why my solution for B gets wrong

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

→ Ответить

Hasib.Nabid

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

Couldn’t solve A pajn. Nice problemset tho

→ Ответить

kyuukyuusha

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

+11

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

I feel like it shouldn't work.

→ Ответить

kriepiekrollie

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

I hacked it

→ Ответить

LaughingBuddha

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

How can we hack any solution now?

→ Ответить

aureliony

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

← Rev. 2 →

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

→ Ответить

mnasser02

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

Spoiler

→ Ответить

ALnQ417

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

+27

Skill issue tbh

→ Ответить

Charararar

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

→ Ответить

avighnakc

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

Np, happens

→ Ответить

Prajwalrayal

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

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.com/contest/1904/submission/236581716

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

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

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

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

→ Ответить

LaughingBuddha

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

System testing completed for this contest? Any idea anyone?

→ Ответить

great_fortune

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

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

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

+10

Hacked. Really weak test data in D2.

→ Ответить

great_fortune

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

Thanks TryingToBeEnough!

so....

REALLY weak D2 tests lol

→ Ответить

great_fortune

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

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

→ Ответить

oursaco

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

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

→ Ответить

aureliony

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

← Rev. 2 →

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

→ Ответить

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

Hacked. sorry

→ Ответить

Deep1809

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

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

→ Ответить

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

Hacked.

→ Ответить

Kawaii

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

-6

why problem A is so hard

→ Ответить

Rakesh_898

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

I think the given picture made it so hard

→ Ответить

biomat

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

← 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

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

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

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

Why do you look at pictures?)

I usually don't look at samples.

→ Ответить

defnotmee

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

+23

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

→ Ответить

cosenza

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

what was the corner case on C?

→ Ответить

Igor_Parfenov

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

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

→ Ответить

defnotmee

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

yeah, this

→ Ответить

LaughingBuddha

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

← Rev. 2 →

Can someone hack my D1? 236559856

Pretests were damn weak it seems.

Testcase —

→ Ответить

eklavya_k

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

5 solves for the first time in a div 2

→ Ответить

elseecay

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

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

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

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

→ Ответить

Blagoj

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

Surprisingly good contest! Good job!

→ Ответить

34z12000

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

It was kind of boring

→ Ответить

Blagoj

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

+20

Hey, anyone can have different opinions

→ Ответить

34z12000

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

-10

Yes, why not

→ Ответить

Jhin

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

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

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

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

→ Ответить

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

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

→ Ответить

EvenToWorldFinal

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

Great contest! Lost some ratings tho...

→ Ответить

dolphin2025

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

Why does my submission https://codeforces.com/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:

→ Ответить

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

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

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

Exactly ...

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

→ Ответить

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

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

→ Ответить

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

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

→ Ответить

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

← 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

→ Ответить