Educational Codeforces Round 124 [рейтинговый для Div. 2]

3 года назад, # |

Why such a huge difference between problem B and C, kinda unfair for pupil / specialists

→ Ответить

3 года назад, # ^ |

welcome

→ Ответить

3 года назад, # |

-6

Why such a huge difference between problem B and C, kinda unfair for pupil / specialists

→ Ответить

_Gilligan_

3 года назад, # ^ |

← Rev. 7 →

Actually it was not so unfair since you required just one observation for C.

Hint

Reason

→ Ответить

trickster0

3 года назад, # ^ |

I am sorry but ... shouldn't connecting any 2 pairs do it? I mean having 2 connections between 2 distinct pairs, this way if one fails the any other is reachable.

I spent about 30 minutes asking myself why the hell does the first test case need to connect 4 pairs.

→ Ответить

_Gilligan_

3 года назад, # ^ |

← Rev. 2 →

No it is not necessary.

Reason

→ Ответить

trickster0

3 года назад, # ^ |

← Rev. 2 →

Shouldn't they be reachable from the other functioning corner? Or you're saying connections are directed (one way)?

→ Ответить

_Gilligan_

3 года назад, # ^ |

No they wont be.

Why?

Hope it helps :)

→ Ответить

3 года назад, # ^ |

← Rev. 2 →

Actually I figured out all of this, but I don't know what I am missing, maybe I'll find out tomorrow, pretty stressed out from today's contest

→ Ответить

DaMiraCode

3 года назад, # ^ |

did you figure it out?

→ Ответить

3 года назад, # ^ |

yeah for the X, |X and X| type of cases, I was doing a loop from 1 to n — 1, but 0 to n — 1 works, I am not sure why, because I cant see the test cases. Maybe some corner cases were getting missed

→ Ответить

DaMiraCode

3 года назад, # ^ |

The idea is that if both a0b0 and a0bn-1 have the same distance, you might choose the wrong one i.e. if you pick a0b0, there might exist a smaller cost that requires you to pick a0bn-1

→ Ответить

3 года назад, # ^ |

Ahhh, you are making sense, damnit

→ Ответить

AliFarhat

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

I disagree with your opinion mira from aim

→ Ответить

gagan_sharma

3 года назад, # ^ |

I think most of the people got the approach but got messed up in corner cases, including me. :(

→ Ответить

3 года назад, # ^ |

Yes, same for me :(

→ Ответить

3 года назад, # ^ |

welcome

→ Ответить

Jhin

3 года назад, # |

← Rev. 3 →

I think i know my mistake in C but not enough time damn I wasted so much time thinking about stupid possibilities that doesn't help in anything

we could do it in three wires right ? like this

1 0 0 2 0 3
1 0 0 3 0 2

i tried only 2 wires or 4 but not 3.

→ Ответить

lingdsd

3 года назад, # ^ |

you just need 2 wires

link 1 1 and 3 2

make it a loop

→ Ответить

Jhin

3 года назад, # ^ |

That's not the values it's how it's possible to link it the ones with the same number are linked sorry it wasn't clear

→ Ответить

lingdsd

3 года назад, # ^ |

oh,yes

we need consider head-head,tail-tail,head-tail,and head-other,tail-other

possibly appear headA-headB + tailA-otherB + tailB+otherA

→ Ответить

silverfish

3 года назад, # |

+11

Experts and CMs after solving A-D:

Image

Btw Im writing this comment 23 minutes before the end of the contest. I have no idea what to do with all this time on my hand:))

→ Ответить

3 года назад, # ^ |

And some Ms, too

→ Ответить

MrOtter

3 года назад, # ^ |

I don't know what you are talking about...

→ Ответить

Hamroz_JONN

3 года назад, # ^ |

← Rev. 2 →

...

→ Ответить

3 года назад, # ^ |

shake hands...

→ Ответить

Anjaneyrai

3 года назад, # |

What was the testcase 2 in C ??

→ Ответить

pushkar31

3 года назад, # |

Isn't problem c only about first and last index of both arrays and finding optimum values in their counterpart arrays?

→ Ответить

3 года назад, # ^ |

Yes. But you need to take into account what happens, if you connect 2 of those 4 nodes to each other.

→ Ответить

3 года назад, # |

+16

hints for problem E pls

→ Ответить

3 года назад, # ^ |

← Rev. 4 →

Dlete

→ Ответить

Lain

3 года назад, # ^ |

Hint 1

Hint 2

Hint 3

→ Ответить

BARBARIANNNNN

3 года назад, # ^ |

hint

→ Ответить

nichke

3 года назад, # |

How to solve C and D?

→ Ответить

Rudro25

3 года назад, # ^ |

For C : a[0],a[n-1],b[0],b[n-1] all must have connection with other row any element efficiently..

→ Ответить

nichke

3 года назад, # ^ |

Lmao I can't believe I thought any 4 points work and now I see it's nowhere near correct. Thanks very much!

→ Ответить

3 года назад, # ^ |

I did BFS from the borders for D. Saving information in a map<pair<int,int>,...>

→ Ответить

Rudro25

3 года назад, # |

D can be solve by dfs.. right ?

and C statement was confusing for me :(

→ Ответить

3 года назад, # ^ |

My DFS failed, needed BFS. What do you do if your DFS has back edges?

→ Ответить

eashang1

3 года назад, # ^ |

I used BFS (from neighboring points not in the given set) and still got TLE. Is this not the idea? Or is there a way to speed up my BFS? 149168850

→ Ответить

3 года назад, # ^ |

← Rev. 2 →

Phew, just looked at your code, it looks ok in principle, your times seem to be ~1.5-2x slower than mine. Guess you need constant optimisation here maybe? In your first loop, when looking for borders, it seems that you can push solitary points 4x into the queue. You can put a continue; there in your ifs. Also you can mark them as used then already.

Yes, constant optimisation did the trick: 149174036

→ Ответить

eashang1

3 года назад, # ^ |

Ah, didn't think to optimize constants. That did the trick. Thanks!

→ Ответить

su1c1dalttb

3 года назад, # ^ |

I passed the pretest with dp and a lot of sortings.

→ Ответить

Anjaneyrai

3 года назад, # |

← Rev. 2 →

What was the 2nd testcase in C?? I tried all the cases can someone tell what I was missing?149157891

→ Ответить

FutureNewbie

3 года назад, # ^ |

In the last for loop of your code, you have written: aml=min(abs(a[0]-b[i]),amf); That should be: amf=min(abs(a[0]-b[i]),amf);

→ Ответить

GreenBamboo

3 года назад, # |

Is DP the correct approach for D? I tried to check the answers of my neighbours and pick the best for me but got TLE on test case 9 :(

→ Ответить

3 года назад, # ^ |

a topological sort to decide the distance of closest point

→ Ответить

vlam21

3 года назад, # ^ |

You can use a DP-like idea. The intuition for me was, for a point, the closest point to [x, y] must either have the same x value (so it's on the same vertical line), or it must be on a path through [x — 1, y] or [x + 1, y].

→ Ответить

_Silent._.Killer_

3 года назад, # ^ |

I tried your idea. Is this way is correct to implement it? 149191779
I got RE on testcase9.

→ Ответить

3 года назад, # ^ |

Failing testcase: Ticket 1708

What's so special about the testcase? It contains all points in the interval $$$[1,5] \times [1, 5]$$$

→ Ответить

_Silent._.Killer_

3 года назад, # ^ |

Thanks

→ Ответить

Alpha-Go

3 года назад, # |

How to solve D? I used dfs to transmit the nearest point but got wrong answer! :-(

→ Ответить

3 года назад, # ^ |

+16

I solved using multi-source BFS from all untaken points neighbouring taken points

→ Ответить

3 года назад, # ^ |

← Rev. 3 →

I tried something similar, but because i am not pro like it took some time for me to code it well. basically what i did is pushed all the points that has an direct answer into queue. (more like pushed the outer layer of points in queue first). then i translated outer layer's answers to inner layers. but i got Wrong answer on Test 9. can you help if you find anything sussy here?

Edit: no worries got accepted. it. was a minor issue :(.

→ Ответить

3 года назад, # ^ |

That's unlucky. I was trying to debug for you but couldn't understand the candidates things. In principle your idea is correct, and equivalent to what I described as multi-source BFS, except starting with the outermost points rather than untaken points. Should achieve the same result.

→ Ответить

3 года назад, # ^ |

thanks for trying your code is sooo clean.

→ Ответить

3 года назад, # ^ |

Thanks. Although actually your approach is quicker and less memory intensive as it doesn't require storing all of the neighbouring points (which can increase the size of the graph by a factor of 5).

→ Ответить

Rad_Forever

3 года назад, # ^ |

I used bfs and I got accepted

→ Ответить

Aoi_Hill

3 года назад, # ^ |

why does bfs not time out

→ Ответить

3 года назад, # ^ |

200k points, at most 800k unused neighbours. Graph has max size 10^6. Why would this time out?

→ Ответить

Aoi_Hill

3 года назад, # ^ |

yeah it won't , i didn't think in the neighbour direction

→ Ответить

lingdsd

3 года назад, # ^ |

I have the same problem as you

→ Ответить

pythoncrazy

3 года назад, # |

What was the technique for B? I wasted so much time on A due to a stupid typo.

→ Ответить

3 года назад, # ^ |

any pair of i, j must satisfy Ai * 3 <= Aj

→ Ответить

puffinmuffin

3 года назад, # ^ |

Powers of 3 work

→ Ответить

vlam21

3 года назад, # ^ |

Try writing the inequality that needs to be satisfied based on the pair you pick.

→ Ответить

Nuwaisir_Rabi

3 года назад, # ^ |

Suppose you'll do the operation on $$$x$$$ and $$$mx$$$ which are present in the array where $$$m \geq 1$$$. After the operation, $$$x$$$ and $$$mx$$$ will be replaced by $$$mx - x$$$, we want the change of the sum to be greater or equal to the previous sum, which implies $$$2(mx - x) \geq x + mx$$$ $$$\implies m \geq 3$$$

So, you build the array like this: $$$[1, 3, 9, 27, ...]$$$ until the array size is $$$n$$$ or the value gets higher than $$$10^9$$$. For the later case the output is $$$NO$$$.

→ Ответить

programmer963

3 года назад, # |

How to solve C? I tried with all 3 cases, but WA on tc2 149150730

→ Ответить

3 года назад, # ^ |

try link left and right end of A and B. either use optimal point in opposite array, or link two end points.

→ Ответить

3 года назад, # ^ |

Failing testcase: Ticket 1579

→ Ответить

starttoend

3 года назад, # |

In C my idea was that computers at end must be connected to some other computer, so we must find a way to minimize this. But for whole 1 hour I was not able to implement due to edge cases of computer at ends being connected to each other. I knew edge cases(like first computer of array A can be connected to first computer of B or last computer of B or both first and last computer of B etc.) but was not able to implement and deal with those.

Any tips on how to improve this ability? Sometimes I break down a problem in different edge cases and get overwhelmed by that.

→ Ответить

_OmarAbdo

3 года назад, # |

it really was an intersting contest i have solved C with topology :" which i have studied in CS

→ Ответить

WoNt_StOp

3 года назад, # ^ |

Same! Lmao maybe that's why they ask CS fundamentals in interviews

→ Ответить

akshat_porwal

3 года назад, # |

← Rev. 3 →

My approach for C

Still WA on test 2 :( 149166751

→ Ответить

barun511

3 года назад, # ^ |

I calculated all 7 cases.

    // Case 1: a1 to b1 and an to bn;
    ans = min(ans, a1_b1 + an_bn);
    // Case 2: a1 to b1, min bn, min an
    ans = min(ans, a1_b1 + a_n + b_n);
    // Case 3: a1min + b1min + bnmin + anmin
    ans = min(ans, a_1 + a_n + b_1 + b_n);
    // Case 4: a1min + b1an + bnmin
    ans = min(ans, a_1 + b1_an + b_n);
    // Case 5: a1 to min, b_1 to min, an bn
    ans = min(ans, a_1 + b_1 + an_bn);
    // Case 6: a1 to bn, an to b1
    ans = min(ans, a1_bn + b_1 + a_n);
    // Case 7: a1 to bn and b1 to an
    ans = min(ans, a1_bn + b1_an);

→ Ответить

3 года назад, # ^ |

← Rev. 2 →

[Updated] Failing testcase: Ticket 1699

→ Ответить

peek4b00

3 года назад, # |

How to solve D ? I got TLE on test 9.

→ Ответить

algobb

3 года назад, # ^ |

I think it's BFS + Dijkstra. If a point in the input is next to any empty point, then the answer is either 1 or 2. The other points must border at least some point in the input. From there you just BFS + Dijkstra to get the point with the least distance to empty point and populate the neighboors

→ Ответить

gesu

3 года назад, # |

Can anybody help me figure out what‘s wrong with my code149129168 in problem B？ it runs well on my computer but kept failing the preset when I submit, I was literally driven crazy during the contest (╥_╥)

→ Ответить

Sakura_mw

3 года назад, # ^ |

move "ios::sync_with_stdio(false);" to the very beginning of the main function.

maybe you can try to use CUSTOM TEST on Codeforces platform when you meet questions like this.

→ Ответить

Penguin07

3 года назад, # ^ |

Put

ios::sync_with_stdio(false);

before reading the inputs, not after.

→ Ответить

XGptw

3 года назад, # ^ |

-8

what happens if we put after, will it cause undefined behaviour

→ Ответить

EasonCookie197

3 года назад, # |

← Rev. 2 →

In problem D, I used a similar idea as This Atcoder Problem. For each point, i binary searched for the shortest distance and used merge-sort tree to check the number of points that has smaller distance than a certain number with that point. I noticed that the distance should be smaller than sqrt(n), so after finding the distance i brute forced through all possible points for the answer.

I think The final complexity is O(nlog^3 + n*sqrt(n)*log) but got TLE on test 9. This will be my 6th consecutive rating drop.(╥_╥)

upd: My contest submission

→ Ответить

_ragnar0k_

3 года назад, # |

my submission for D giving MLE... If anyone have experienced similar problem, please help me

→ Ответить

ShaurabhTiwari

3 года назад, # |

How to solve D?

→ Ответить

ShaurabhTiwari

3 года назад, # |

How to solve D?

→ Ответить

Rad_Forever

3 года назад, # ^ |

I used bfs，put the unused neighbours in the queue，and calc the answer when you meet a node which is not among the given $$$n$$$ points.

→ Ответить

TripleM5da

3 года назад, # |

← Rev. 2 →

Is $$$O(Nsqrt(NlgN))$$$ intended for problem F? I know that we can do pure $$$Nsqrt(N)$$$ if we solve for each block for each monster instead of for each monster for each block, but still, it sounds like a lot of work :(

→ Ответить

BledDest

3 года назад, # ^ |

Model solution is $$$O(N \log N)$$$, but we decided to allow slower solutions with good implementation pass (although $$$O(N \sqrt{N \log N})$$$ sounds kinda scary)

→ Ответить

Vercingetorix

3 года назад, # ^ |

Apparently even $$$O(N \sqrt{N} \log N)$$$ can pass :)

→ Ответить

BledDest

3 года назад, # ^ |

Well, the time limits were kinda generous in this problem (the model solution runs in something like 1s on 32-bit C++ compiler). Although 3931 ms out of 4000 sounds very scary

→ Ответить

TripleM5da

3 года назад, # ^ |

← Rev. 2 →

Not at all mine runs in 1.5 seconds which is kind of okay also it's really easy to write and you can argue that if written with prefix sum the operations would be simple enough that you wouldn't be able to differentiate between $$$O(NlgN)$$$ and $$$O(NsqrtN)$$$ "unless you go full Chinese on the constraints/test data ig".

→ Ответить

gen

3 года назад, # ^ |

← Rev. 2 →

I changed to unordered_map, so $$$O(N \sqrt N)$$$, and it passed, although 3899 ms. D:

→ Ответить

3 года назад, # |

+34

If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table to increase/decrease the constraints.

If you are not able to find a counter example even after changing the parameters, reply to this thread, mentioning the contest_id, problem_index and submission_id.

→ Ответить

tgp07

3 года назад, # ^ |

Thank you so much! This is amazing!

→ Ответить

beethoven97

3 года назад, # |

is cf_predictor give correct results? why it predicts low increasing values in this contest ? is rating in code forces changed?

→ Ответить

beethoven97

3 года назад, # |

is cf_predictor gives correct predicted values ? i think that there must much increasing points in rating than i see in standings.

→ Ответить

gagan_sharma

3 года назад, # ^ |

Yes, I have found the carrot chrome extension to be more accurate.

→ Ответить

algobb

3 года назад, # |

Screw C. Took more than an hr to solve it, and 40 minutes to finish D but not time to submit it

→ Ответить

decrypto96

3 года назад, # |

← Rev. 2 →

My approach for D:

Rotate coordinate space by 45 degree by transforming (x,y) with (x+y, x-y). Now, for a point X, observe that all 4 points at distance 1 form a square, then next 8 points at distance 2 form another square and so on. Each square will have 4D points here D is distance from X.

Since N is 2*10^5, D can be at most 350. So for each point, I checked number of input points in squares of length 1, 2...350. As soon as I get a square of length d which has less than 4d points, we need to search in this square.

Then its simply searching all points at distance d and returning any one excluded point.

Complexity: O( N*Sqrt(N)*log(N) ) Solution: 149223014

But solution TLE'd on test case 30. Would appreciate if someone can take a look at my code and suggest scope for optimization.

→ Ответить

EasonCookie197

3 года назад, # ^ |

How did you check the number of points in a square?

→ Ответить

Thallium54

3 года назад, # ^ |

I got TLE on test 30 149175151. I doubt the time complexity but also can't imagine what does the worst case look like.

→ Ответить

decrypto96

3 года назад, # ^ |

Yeah, I think theoretically the number of operations in the worst case would be around 5.6*10^9 [(2*10^5)*(350)*(20)*(4)]

→ Ответить

3 года назад, # ^ |

← Rev. 2 →

I was trying to use openmp's parallel functionality, does cf supports it? i am not getting any error nor can i observe any significate difference in execution time.

without pragma 149232334

with pragma 149233499

→ Ответить

changed your unordered set to set, because i guess performance of hash structure is complicated to guess.

3 года назад, # ^ |

can you find why it is printing an already existing point?

→ Ответить

decrypto96

3 года назад, # ^ |

Thanks. Fixed a silly bug. Updated the comment.

→ Ответить

ars9

3 года назад, # ^ |

You can eliminate use of set, you already have list of sorted point with respect to both dimensions.

→ Ответить

weakestOsuPlayer_244

3 года назад, # ^ |

I have a solution which barely passes and it was possible thanks to IceKnight1093 optimizing my previous code by omitting pairs.

It uses pragmas and shit so it's totally not safe for a contest submission.

Perhaps someone else can bother to optimize it further.

→ Ответить

dkg7888

3 года назад, # ^ |

I solved D considering/using that answer can never be greater than 700 . I made pair of interval for each coordinate of x from 0 to 2*10^5+1 which doesn't have a y coordinate . Then for point {x_i , y_i} it's just binary search the left nearest and right nearest value of y for each z s.t. ( z>=x-700 and z<=x+700)
It's ACs in approx 1 sec
Solution

→ Ответить

fonmagnus

3 года назад, # |

← Rev. 2 →

My ideas for D (not AC on contest) :

Pick a random unvisited point name it $$$p$$$ and mark this point as visited
Do floodfill to another points adjacent from $$$p$$$ and mark them all as visited (adjacent : manhattan distance is equal to 1)
So now from all the floodfilled points we form a connected component from $$$p$$$. Pick border points from this connected component (a point is called border if there's at least 1 adjacent point which doesn't exist in the input)
From all border points, we can get their respective "source" (i.e. the neighboring point which is not in the input)
Do multisource BFS from all border points and now you can get source for all non-border points by setting it to the source of their nearest border points

My implementation 149198396

I love the idea of the solution! Didn't quite like C (because caseworks), but this problem has a beautiful solution

→ Ответить

mihir01010

3 года назад, # |

chance to get specialist...

→ Ответить

dala_bilal

3 года назад, # |

I want to know how people know this formula for problem B :

(b — a) * 2 >= b + a

→ Ответить

treap_enjoyer

3 года назад, # ^ |

We need the next sum to be no less than the previous one. If we change a and b to |a — b| then their sum will be equal to |a — b| + |a — b|. We can expand the module and get (a — b) *2. And by condition, we want this sum to be at least a + b. => 2 * (a — b) >= a + b

→ Ответить

notblue

3 года назад, # |

when are the ratings going to update as it's past 12 hr already?

→ Ответить

wsyear

3 года назад, # |

-6

When will the rating be changed?

→ Ответить

rohanmitra2420

3 года назад, # ^ |

-9

same doubt its showing in unrated constest for now

→ Ответить

Haricane193

3 года назад, # ^ |

System testing just started

→ Ответить

prateek_saxena

3 года назад, # ^ |

How did you know that?

→ Ответить

Jadebo1

3 года назад, # ^ |

same question

→ Ответить

iamttm

3 года назад, # ^ |

+30

You did not participate in the contest, why do you care about it? This kind of question has been asked a ton of times for every Educational round.

→ Ответить

Rice_porridge

3 года назад, # |

The rating is still not updated......

→ Ответить

awoo

3 года назад, # |

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

→ Ответить

shiva1904

3 года назад, # |

I didn’t get rated yet ?? Why any idea

→ Ответить

shiva1904

3 года назад, # |

Hey does anyone know why I didn’t get rated yet is educational round ?

→ Ответить

Haricane193

3 года назад, # ^ |

No one got rated yet. The editorial has just been released so I would assume ratings will be updated soon too.

→ Ответить

ShubhamGarg

3 года назад, # |

Me here reloading the website every 10 seconds for +2 delta :/

→ Ответить

3 года назад, # |

In yesterday's competition, my code for question B was judged to be duplicate with others, but my code was submitted earlier, so there is no possibility of plagiarism at all. Plus, I want to score 2100 for this game, so there's no way I'm giving away my code to anyone else. Moreover, the solution shown in my code is a very general solution, and it is very easy to repeat it in a small amount of code. I don't think it's reasonable. Please check it carefully!

→ Ответить

3 года назад, # ^ |

MikeMirzayanov，I could have been a master, but now I'm an expert. Please check it! Thank you!

→ Ответить

Catalyst008

3 года назад, # ^ |

same with me bro i got plagiarism on A. how can it be possible problem A was one liner

→ Ответить

3 года назад, # ^ |

I hope for a reasonable explanation. This accident reduced my rating by 300 :(

→ Ответить

Catalyst008

3 года назад, # ^ |

I can understand bro but I don't think our issues will be responded

→ Ответить

3 года назад, # ^ |

Thank you for your comfort. I hope there will be no similar problems in the future. Good luck.

→ Ответить

sumitkushwaha188

3 года назад, # |

← Rev. 2 →

I had a coincidence of my solution(149124483) matching with solution(149099666) of Performanceartist for the problem 1651B . clearly it is a coincidence as he is a candidate master and i a newbie with no prior communication between us. He submitted his solution much before me. please look into it.Your text to link here...

he(performanceartist) has commented for the same problem.

→ Ответить