Happy Holidays Codeforces! 🎅

mesanu, flamestorm and I are very excited to invite you to Codeforces Round 918 (Div. 4)! It starts on Dec/28/2023 17:35 (Moscow time).

The format of the event will be identical to Div. 3 rounds:

- 5-8 tasks;
- ICPC rules with a penalty of 10 minutes for an incorrect submission;
- 12-hour phase of open hacks after the end of the round (hacks do not give additional points)
- after the end of the open hacking phase, all solutions will be tested on the updated set of tests, and the ratings recalculated
- by default, only "trusted" participants are shown in the results table (but the rating will be recalculated for all with initial ratings less than 1400 or you are an unrated participant/newcomer).

We urge participants whose rating is 1400+ not to register new accounts for the purpose of narcissism but to take part unofficially. Please do not spoil the contest for the official participants.

Only *trusted participants of the fourth division* will be included in the official standings table. This is a forced measure for combating unsporting behavior. To qualify as *a trusted participant of the fourth division*, you must:

- take part in at least five rated rounds (and solve at least one problem in each of them),
- do not have a point of 1400 or higher in the rating.

**Regardless of whether you are a trusted participant of the fourth division or not, if your rating is less than 1400 (or you are a newcomer/unrated), then the round will be rated for you.**

Special thanks to the VIP testers: AlperenT, KrowSavcik!

Thanks a lot to the testers: Qualified, Kaushal_26, htetgm, MADE_IN_HEAVEN, sandry24, hbarp, Vladosiya, LucaLucaM, Gheal, tvladm, Dominater069, haochenkang, xiaowuc1, pashka, vrintle, BucketPotato!

And many thanks to Vladosiya for translating the statements!

We suggest reading all of the problems and hope you will find them interesting!

🎄 🎄 🎄 **Good luck to everyone and enjoy the holidays!!!** 🎄 🎄 🎄

Thank you

very handsome.

I promise to solve at least 4 problems.

P.S. Cool photo!

and you kept your promise!!

I kept my promise, I can die with a clear conscience.

This is my first out of competition and first unrated round

Legendary Grandmaster with 1435 Rating??

magic

Why not?=)

What's happened these months @_@

--- Oh it's MAGIC. Happy new year!

)

All the best bro

Thank you! Nice photo.

Every div 4 is good

Finally, this is my first unrated contest... I hope I will be able to solve all problems under contest time .... Merry Christmas and happy new year to all ....

`questions`

❌`problems`

✅Thank you mate for the correction...

why?? ps im new here

I think conducting the div4 contest is the best holidays gift for the people having rating less than 1400.

Hope to be a great contest before Christmas...

Christmas was on the 25th, it's the 28th now :)

(unless you're talking about Orthodox Christmas on the 7th of January :D)

Div4 should be arranged more frequently. Hoping for a great contest!

agreed

Are there watermarks on those Christmas hats?

Yes

thank you for this !I hope my rating will slightly increase. I was demotivated for a long time due to failures after failuresHopefully with this contest I can enter green :)

I hope to reach pupil after this contest, insha-allah.

i hope to retain the magic colour even after 10th jan with this round

looking forward to your success!

thanks mate!!

so handsome

It will be my first Div 4 participation ^_^

I would aim to solve >80% problems.

LMFAO!! What a noob

This contest is rated for you and not for me xD

Pupil! Pupil!

The cap on your head looks edited

looks pretty real to me

Its real, i clicked the photo

He's right, I was the camera

yeah, He is right, I was the cap

As a tester, Santa helped me test the contest

This will be my second participation at codeforces. Last was Div 3 I couldn't solve a single one.

I think I will be green this year, Insha Allah. Hopefully, this round will be great for me. I wish I could do it.

Wow! Dominater069 was a tester. That's great!

flamestorm face reveal!?!?!!

div 4 time yay! thank you for the div 4 contest!

I hope I will be pupil after this round

As an unemployed tester, I wish all participants happiness and employment.

As VIP testers, this was our testing room:

Photoi wanna be specialist on this contest :)

Good luck to everybody ;)

Best of luck to all participants!

I wish you all a happy game, and I wish you a good score.

As a tester, I changed my color.

Hi, can I do red testing for this round? (hehehehe)

thank you

Eh, 2022-2023 is over, it was not like 2020, which is good, but I remember it as one of the most important years, I hope that next year will be successful for you allI hope that for many every new year will only be betterMy first Div.4 participation too! As a noob, hope the questions are friendly to me so that I can solve questions that less than 1300 smoothly. good time!

Hoping I could reach specialist :D

Thank you!

Can't wait to get +ve delta

Merry Christmas!

The best ending of the

2023withdiv4. BTW nive picture!As a specialist, my first unrated contest,unfortunately I can't participate

****___After Long Time___****

Just hoping for +ve delta in this one

love it！

I hope the problems are as easy as it is to spot the fake caps in the picture ;)

Happy Holidays to everyone and Merry Christmas. Coding in holidays may not be possible for many but Respect to you if you are here

Thanks for the round!!

handsome photo, the last competition in 2023

Good luck everyone

This is the day i will say goodbye to my green name

do well everyone

in queue LOL

in the statement of Problem D:

mistake: 1<=n<=2*10^5 correction: 2<=n<=2*10^5

So many people have registered for this round that I had to wait 20 minutes to see the verdict for problem A.

Thanks for the round !!!

Loved the problems on this round <3

Awesome problems, guys! Keep it up!

Nice contest

Is the person replying to the questions during the contest a bot or online human???

human

Thanx...

Fun fact: $$$G$$$ can be solved using GPT $$$4$$$ without any hints.

Really? Can you send code

Check my sibmissions. (As you can see i participated unofficial, so it must mot be cheating or smth else:) )

How do you get it accepted with 170ms? I tried your code, and got 2000+ms. Where is the difference from?

I don't know how it is possible:)

Screencast and Solutions to all problems

SecondThread orz

Thanks a lot! It was really nice to see a different view on the tasks

This video is unlisted btw.

it's over,

I will never reach cyan 🤡

Is MO decomposition in F an overkill? :D

My solution: 239387414

might be, solved it using ordered sets, although i believe the author had a simpler solution for F of a Div 4!, btw what was your reasoning behind G?

Basically we clone each vertex $$$n$$$ times. Each clone will be a pair, where first element is number of vertex and second is bicycle we use after we visit this vertex. So, now we just use dijkstra algorithm to find min path to ($$$n$$$, $$$any$$$-$$$bicycle$$$). You just need to find some transitions when you start using different bicycle. Something like this.

You can compress the coordinates, sort the intervals and then use fenwick or segment tree to calculate the answer.

Yeah, it's just nlogn inversion count using merge sort

what is the idea of E? i felt its harder than F and evne G ( if i got the idea of G correct)

think about the prefix sums of the odd-index and even-index arrays. What can you say about the prefix sum values at the left and right endpoints of a good subarray?

Let $$$\mathrm{sum_{even}}$$$ denote the sum of values on even indices on our current subarray, and define $$$\mathrm{sum_{odd}}$$$ similarly.

$$$\mathrm{sum_{even}} = \mathrm{sum_{odd}}$$$

$$$\mathrm{sum_{even}} - \mathrm{sum_{odd}} = 0$$$

Now, multiply all values on odd indices by $$$-1$$$ in the original array. The condition now becomes

$$$\mathrm{sum_{even}} - (-1) \cdot \mathrm{sum_{odd}} = 0$$$

$$$\mathrm{sum_{even}} + \mathrm{sum_{odd}} = 0$$$

The left side is just the sum of the current subarray. Thus, we need to find a subarray with sum $$$0$$$ $$$\Leftrightarrow$$$ you need to find two equal prefix sums.

got it amazing problem and solution thanks alot !

Still clueless could you explain it to me?

What part of my comment did you not understand?

As to why we need that particular subarray where all the odd incidces sum up to zero and why do we need to use prefix sum here.

That's not what I said; odd indices shouldn't sum up to zero. Let me try to explain everything again with more details.

Let $$$\mathrm{sum_{even}}$$$ denote the sum of values on even indices on our current subarray, and define $$$\mathrm{sum_{odd}}$$$ similarly.

According to the problem statement, we need to find a subarray such that $$$\mathrm{sum_{even}} = \mathrm{sum_{odd}}$$$

Subtract $$$\mathrm{sum_{odd}}$$$ from both sides:

$$$\mathrm{sum_{even}} - \mathrm{sum_{odd}} = \mathrm{sum_{odd}} - \mathrm{sum_{odd}}$$$

$$$\mathrm{sum_{even}} - \mathrm{sum_{odd}} = 0$$$

Now, let's multiply all values on odd indices by $$$-1$$$ in the original array. Thus, $$$\mathrm{sum_{odd}}$$$ becomes $$$-\mathrm{sum_{odd}}$$$ in our new array.

This means that the required condition is now

$$$\mathrm{sum_{even}} - (-\mathrm{sum_{odd}}) = 0$$$

$$$\mathrm{sum_{even}} + \mathrm{sum_{odd}} = 0$$$

For any subarray, $$$\mathrm{sum_{even}} + \mathrm{sum_{odd}}$$$ is just the sum of that subarray. This is because every element in the subarray is either counted in $$$\mathrm{sum_{even}}$$$ or in $$$\mathrm{sum_{odd}}$$$.

Now, we just need to find a subarray with sum $$$0$$$.

Let $$$p_i = a_1 + a_2 + \dots + a_i$$$, i.e. the array $$$p = [p_1, p_2,\dots, p_n]$$$ is the

prefix sum arrayof $$$a_1, a_2,\dots, a_n$$$. Remember that this array $$$a$$$ is the one from input, with all values on odd indices multiplied by $$$-1$$$.Recall that $$$a_l + a_{l+1} + \dots + a_{r} = p_r - p_{l-1}$$$, i.e. the sum of a subarray of $$$a$$$ can be expressed as a difference of two prefix sums.

Since we need a subarray with sum $$$0$$$, we need two prefix sums $$$p_r$$$ and $$$p_{l-1}$$$ such that $$$p_r - p_{l-1} = 0$$$

Add $$$p_{l-1}$$$ on both sides:

$$$p_r - p_{l-1} + p_{l-1} = p_{l-1}$$$

$$$p_r = p_{l-1}$$$

This means that we just need to find two equal values in the prefix sum array. Remember to also include $$$p_0 = 0$$$ in your prefix sum array, since this might be needed when $$$l = 1\ \Leftrightarrow\ l-1 = 0$$$.

Got it.

Thank you for such detailed explanation.

a -> pref sum of odd indidces b -> pref sum of even indices for range l...r to be valid ar — al = br — bl -> (ar — br = bl — al) now you know how do it. it's similar to 2 sum problem

implemented the (ar-br) = (al-bl) through n^2 approach but got tle in 3rd TC , didnot get what is two sum problem mentioned in your post can you provide a reference for that i'll go through it O(n^2) approach

problem

I have done it once using hashset.

does solving this problem will help me understand E ?

yes the idea is same

hint : a + b = c => a = c — b think of bs. then further how can you optimes it

I'll try to do using this hint.

GL

solved it 239414558, initially I didnot get why 'two sum' in this question , but after knowing the 'subarray sum' problem got to know how two sum can be used to find a subarray of sum equals k, and I also read some post explaining about multilping -1 to alterntive ele. ThankYou for the help alpha1215

glad i could help you btw an advice never use unordered map in contest it can tle

any other alternative for map in this question, and also i tried solving F in O(n^2) considering a person meets every person whose staring and ending points are inside his starting and ending point, but the soln needs to be optimised

for first ques you can use simple map it's fine for F yo can sort the people based on their starting position now person i will meet every other person j such i < j < n if the j'th person has ending position less than i'th person after this observation it becomes a classic problem counting the inversions in array to do this there are many the method i know to do this is divide and conquer but during contest i used heap my 239336078

you can solve it with a set , make every even index element negative then loop on the array and insert the prefix sum till i in the set , and find if you have the same prefix already , if true then its a YES .

yeah thanks the implementation isn't a problem but the idea is really amazing i think i need to practice math or maybe need a brain transmission XD

can someone tell me if my approach for G is correct or not for every node i (min time to reach from 1 to i) + (min time to reach i to n) ans is min of all those nodes;

Trying same thing from hours but don't know why it's not working... I hope some explain flaw in this approach

I think the above approach assumes that the optimal route would involve a direct path from 1 to i and then i to n, and this surely is the case in the first sample test case. However, it may not always be the case as the minimum time route is a walk(not a path always) for the problem.

Consider the modified weights and bike slowness:

In this case you may observe that the optimum route goes as 1-2-3-2-4-2-5. So, the solution in this case is time(1,3) + time(3,4) + time(4,5). This can be generalized and you can make test cases where the optimum route is a combination of many simple paths, and so the assumption that

time(1,n) = min over i{time(1,i) + time(i,n)}fails.`The optimum route is a combination of many simple paths`

Thank you so much for explaining. :)

Loved the problemset. Solved 6 problems

can somebody say why 239395416 getting TLE on 21st testcase?

What is the time complexity of my code? Isn't it O(nlogn)? 239378769

distance is $$$O(n)$$$

I thought distance is faster, is there any alternative variation to what I wanted to do?

Time complexity of the distance method is O(N), which means your final complexity is O(N^2)

can I do F in PYTHON without use SortedList?

(Co-ordinate compression + segment Tree) will work too.

Could someone please explain how to approach problems like E? TIA

We just have to found the subarray (with certain sum x) whose sum of odd and even places is same. what we can do is if we multiply -1(either of the odd or even position) now we just have to find the contiguous subarray with 0 sum that can be done by maintaining a prefix sum and a set(basic hashing)...

You can take help by this video..

Can anyone explain ideas behind F and G?

For F, you can see that 2 intervals contribute to the answer only if 1 is completely into another. Noy you can compresd all the coordinates, sort the intervals by ascending xleft coordinate and use segment or fenwick tree to calculate the answer. Tou can see my code for more details.

for some reason, I am unable to view your submissions. Could you please share your code, or tell me how to maintain number of intervals between two coordinates l and r using segment tree?

Problem F can be soved using ordered set.239369576

can you explain it

I kept on thinking the entire contest that set can't count elements greater than an element in log(n) time. Didn't know that something like ordered_set exists in cpp. Thank you so much for your elegant solution.

Gosh these problem setters just made my day. You guys propably don't know how happy you've made me today with this contest. This is hands down the best contest I've ever participated in as newbie. The problems were not too too hard for a noob like me and by no means easy either. i Was able to solve A-C and i know if i had enough time, i would have cracked D (still going to try to crack that bi*ch anyways). B was the my best problem in this contest because it was the thoughest for me and it involved me using something I'm not quite used to(2D arrays). Thanks a lot for such a nice contest.

Bro really overthinking B

I did not over think it at all. I knew the solution to the problem but what took me time was the implementstion, cause like i stated earlier, I don't really know how to work with 2D arrays, heck i didn't even know you could sort a single row(that's how noobish i am), but I'm glad i learnt alot today, and im happy :)

Tell me one thing, did you copy C? Someone for whom traversing 2D array is tough, had template in C (but not in A and B where it might be useful) which was anyways not required.

i have used this code to count the no. of inversions i changed it little bit. so i hope this is not considered as cheating and my submissions will not be skipped as many participant may used the same code

read this blog

now it doesn't matter my F got hacked blind me couldn't see there is insertion operation on vector in worst case case it's O(n^2) but the article says O(n * log(n))

Better luck next time.

code` void dxt(int tc){ cin >> n >> s; set v,c; v.insert('a'); v.insert('e'); c.insert('b');c.insert('c');c.insert('d');

} `

I have no idea why this code is printing an additional character, and it costed me a good contest. Can anyone help me figuring out this?

Here, what if i + 2 >= n

Yeah got it, Thank you!

in problem F why the answer for this input is 9 ?

point(4,5) meet with (3,9) at 2nd sec ->count=1; point(2,6) meet with (4,5) at 3rd sec ->count=2; point(1,8) meet with (4,5) and (2,6) at 3rd,5th sec ->count=4; point (-2,100) meet with every other point at 7th,8th,10th,11th,12thsec ->count=4+5=9;

You must find all $$$a_i > a_j$$$ such that $$$b_i < b_j$$$.

The $$$(a_i, b_i)$$$ and $$$(a_j, b_j)$$$ pairs that meet this criteria are as follows:

So in total there are 9 greetings.

finally i'm LGM after this round

why

what

Can any one tell why my submission to G is giving WA ? Also a clarification i need, if Salvic is at city C and has bought some k bikes till now, then he can use any bike(1 to k) to travel to neighbouring cities of j right ?

My latest submission

He can only use bikes from the cities he has travelled through, i.e. only the bikes from the cities that lie on the path(or walk) from city 1 to city C.

right, then probably I understood problem right though late but still.. like the implementation above covers this fact !

Can someone please explain the test case 1 of problem G? how is 19 achieved?

1 -> 2 -> 3 -> 2 -> 4 -> 5

1 -> 2 time = 10 2 -> 3 time = 10 + 2 3 -> 2 time 10 + 2 + 1 2 -> 4 time = 10 + 2 + 1 + 5 4 -> 5 time = 10 + 2 + 1 + 5 + 1 total time = 19

I'll denote the fastest bike that we currently have by $$$b$$$.

The steps are as follows:

Elapsed time: $$$10 + 2 + 1 + 5 + 1 = 19$$$.

u look like kenzo tenma and johan liebert

Hello Everyone What is this trusted participant thing? I see the standings have a trusted participant tag. I participated after long tume. Will this round be unrated for me?

Amazing contest!!! Solved all except E lol. Ordered Multiset FTW in F.

Thanks for the great round SlavicG mesanu flamestorm and all testers.

you don't need Ordered Multiset for F.

Yes Fenwick tree is another option

my first impression on divs (^O^)/

Hoping to become a pupil. Also can anyone explain the test case for F? -10 10 -5 5 -12 12 -13 13 How is it 6?

Everyone greets each other. (-5,5) and (-10,10) meet at 5 (-5,5) and (-12,12) meet at 5 (-5,5) and (-13,13) meet at 5 (-10,10) and (-12,12) meet at 10 (-10,10) and (-13,13) meet at 10 (-12,12) and (-13,13) meet at 12

t = 0. A is at -5, B is at -10, C is at -12, D is at -13.

t = 10. A is at 5, B is at 0, C is at -2, D is at -3.

t = 15. B is at 5 and greets A. C is at 3, D is at 2. 1 greeting.

t = 17. C is at 5 and greets A. B is at 7, D is at 4. 2 greetings.

t = 18. D is at 5 and greets A. B is at 8, C is at 6. 3 greetings.

t = 20. B is at 10, C is at 8, D is at 7.

t = 22. C is at 10 and greets B. D is at 9. 4 greetings.

t = 23. D is at 10 and greets B. C is at 11. 5 greetings.

t = 24. C is at 12, D is at 11.

t = 25. D is at 12 and greets C. 6 greetings.

t = 26. D is at 13.

Thanks

my face when tourist got hacked ._.

what test was he hacked on?

I don't know. I think there is no way for us to know that right now

What was the idea of F? Segment trees?

dp[i][j] = shortest path from i -> j where s[j] is the smallest

my bad, i thought u were talking about G

F: https://cses.fi/problemset/task/2169

sort elements in terms of a[i], find the inversions of array b after sorting (this can be handled by ordered multiset, fenwick tree, segment tree or even merge sort)

hintsegments s1 e1 and s2 e2 giving s1 < s2 cant meet together unless e1 >= e2 ( forgot the equality too since they are all distinct)

hint2sort the intervals by start

Geothermal King of Div4 contests. He ACs the entire problemset so quickly lol.

stared at G for over 2 hours, ggs

How to solve E ? and someone can give me a countertest for 239242264

If you get the answer in the first 2 lines so that you don't input the next lines.

Not even a clue how to solve E by prefix sum and Why to find a zero prefix sum with the addition of sum being calculated with multiplying by -1 to odd indicies :(

sum_odd(l, r) = sum_even(l, r)

<=> sum_odd(l, r) — sum_even(l, r) = 0

or

<=> sum_even(l, r) — sum_odd(l, r) = 0

we can either pick sum of odd elements or even elements, and negate it, now it turns into the classical problem of finding out whether a subarray of sum 0 exists

handsome!

why this solution gets time limit on test 3: https://codeforces.com/contest/1915/submission/239385030

isn't time complexity of it O(n*log n)

distance works in O(n)

std::distance is O(n)

How to solve E and F? can anyone explain it easily! thanks in advance.

F is here: https://cses.fi/problemset/task/2169

Refer to this for E: https://codeforces.com/blog/entry/123876?#comment-1098564

Knew about them 30 minutes before the contest and now it's everywhereF is the worst problem I have faced till now, why did these tests allow O(n^2) solutions to squeeze in? I did not expect O(n^2) solutions to pass at all.

Can you link the O(n^2) submissions that passed?

https://codeforces.com/contest/1915/submission/239387707

where you seeing $$$O(n^2)$$$ ?

v.erase works in O(n) depending on the index of the element being erased. In worst case, it goes to O(n^2).

oh, I see. $$$5$$$ sec for $$$n = 2 * 10 ^ 5$$$ is really doubtful

They will probably face FST.

I think something like 0 1 0 2 0 3 .. will cause this code to give TLE.

std::distance works in O(n), so your code is O(n^2).

how to do then just subtraction shows error

You cannot subtract two rb tree iterators. Use an ordered multiset.

lol. tourist's solution of G got hacked.

what's lol in this??

div 4 should have more questions..like same number of questions like div2 after D considering as div 2 A

My screencast: https://youtu.be/1cdLQi_0_XQ?si=J7HiLQiXyFT0fe_u finished in 29 mins

I solved 4 problems and Iam a new comer and this contest is unrated for me. Can I know why?

I am not trying to be rude but can you please read the announcement blog again?

can someone try to hack my G solution? https://codeforces.com/contest/1915/submission/239320792

I feel like it should be able to get TLE. I followed an approach similar to bellman ford algorithm. I looped through j and used

dist[1 to i] = min(dist[1 to i], dist[i to j] + s[j]*greedy_dist[i to j])

to relax the nodes like in bellman ford

It seems like the time limit is enough for bellman ford. Try to come up with a case with maximum case and it only takes 2652 ms for your solution to pass.

can we solve f without fenwick tree

Yes, I used ordered set. 239405291

Can anyone please tell what is wrong in this method for problem G ?

dis[i][j] means minimum distance to reach ith node if the minimum slowness factor is j to reach node i.

because you are initializing that time to reach node $$$1$$$ for every slowness is $$$0$$$, which is wrong, since you can reach back to node $$$1$$$ after taking the slowness of some other node and then procees with that for further $$$optimal$$$ answer but you block it since when it reaches node $$$1$$$ its sees the time to be minimum($$$0$$$) already.

small test caseHope that helps !

everybody talking about tourist hacked problem, but

i got hacked on E for using unordered_map instead of map. it's the first and last time i got hacked for this.

Here a useful blog about that: https://codeforces.com/blog/entry/62393

Idk my solution to G was different from most so...

SolutionLet $$$dis[i][j] =$$$ minimum distance from $$$i \rightarrow j$$$ without considering bicycle slowness

$$$dis[i][j]$$$ is calculated by running dijsktra from every node

Let $$$dis2[i][j] =$$$ minimum distance from $$$i \rightarrow j$$$ such that we ONLY use bicycle $$$i$$$

$$$dis2[i][j] = dis[i][j] * slowness[i]$$$

We can form a new graph consisting of the original $$$N$$$ nodes such that there is an edge between all pairs of nodes and the weight of the edge $$$i \rightarrow j = dis2[i][j]$$$. Run Dijkstra on this new graph from node $$$1$$$ to get the answer.

Time Complexity: $$$O(NM\log{N})$$$

Submission

maybe i can say win998244353 and ah_shit_here_we_go_again both team worked acc.

They are committed in a completely chaotic order and have different code styles.

239194376 why is it TL? can some one pls look)

It's pyyyython baby. Use python 3 instead of pypy3-64

is python3 really faster than pypy??

at times yes, but mostly it's the other way around

Use fast IO.

`input = sys.stdin.readline`

My Screencast

Post contest discussion stream

I was thinking about this problem F, It's something like count the number of inversions in an array

I solved using ordered_set, binary trie and merge sort(Submission), and I know how to solve using Fenwick tree/Seg Tree.

I wanted to know if there is something easier I can do

If:

Walker 1 will greet walker 2.

This is true because if walker 1 starts in front of walker 2, it will reach walker 2's end before walker 1, and if walker 1 ends behind walker 2, it will stop before it reaches where walker 2 stopped.

So we can sort the starting points in ascending order, and then for each walker, we can count how many walkers greet them by counting how many of the walkers we've iterated through so far have an endpoint ahead of our current walker. The order statistic tree facilitates this very cleanly (and at 1/10th the speed). 239357334

It's not too slow, you can use this(Fast IO) to speed up your code

`ios_base::sync_with_stdio(false);`

`cin.tie(NULL);`

I submitted your code again: submission

It's running in 202ms

Thx

why O(nlogn) solution not pass problem F?

Why wouldn't it work? My solution is $$$O(n log (n))$$$

239429264 I do believe this is O(nlog(n)) if I'm not mistaken

The distance method's runtime is O(N). So your solution is O(N^2).

interesting, I've been thinking distance will always run in O(1)

my n*logn*logn solution passed for F using merge sort tree.

Hack this, please!

Solution is correct

Thank you for such fun round!

Can anyone please help me understand why 239392696 for problem E is hacked despite O(n)? Even 239438693 raised tl. TT

F can use sweep line?

can somebody explain it out why my code is getting error for question "CAN I SQbUARE"

for _ in range(int(input())): n = int(input()) x = list(map(int,input().split())) s = 0 for i in x : s+=i

It's not true that a number is a square number if $$$pow(s, 0.5) * pow(s, 0.5) = s$$$. That is only true if the result of $$$pow(s, 0.5)$$$ was an integer. Since the function returns a floating point number, that floating point number times itself will often be equal to s, so your solution will say "YES" for many non-square numbers.

can someone tell on which test case my solution of e got hacked

In short, you shouldn't use unordered_map in CodeForces (or other hackable contest), check this.

In problem E, unordered_map gives TLE, but map gives accepted verdict. Could anyone please let me know why?

Maybe 2e9lg2e5 steps usually runs faster than the limit of 1s; (# of testcases) * (nlgn) = (1e4) * (2e5 * lg2e5)..?

The sum of n over all test cases does not exceed 2⋅105

Thank you for the correction! Now I understood why it was accepted; nlgn <= 2e5lg2e5 runs faster than 1s. Good!

I still don't understand what is wrong with unordered_map which runs for O(const). Do test cases break hash table somehow? :(

https://codeforces.com/blog/entry/62393

My rating was 772 , and I haven't solve a single problem before in div4. But yesterday I solved two problems. It was supposed to increase my rating. But my rating remains the same. Why ? Can anyone explain please.Why this contest was unrated for me (:

Rating will be distributed soon. Good to see another fellow named "Nabid"

I have created account this account year before and I had given the first contest today. This was unrated for me and my contest rating is also showing as unrated. I solved four questions in this round. Can I know the rules of rating and why Iam not rated?

rated hasnt been released yet

In 1915F - Greetings,

I don't know why the First code get TLE, but the Second code passes. I'm not sure about the reason. Can you explain?

First java code : 239385944 — using Treeset, headtail method

Second java code : 239456229 — using ArrayList, BinarySearch method

Is there a significant difference in the time complexity between the two codes?

It's my first Div 4 participation

Why my rating has not increased after giving codeforces round 918 contest. I registered for it an hour before but it is showing unrated. My rating is below 1000

It will increase after the rating for contest get updated.

Have the tasks been retested yet?

I'm actually a bit confused regarding this round, as my rating is below 1400 and yet after solving 2 questions, my rating hasn't been increased. If anyone could please help me explain the situation please.

It will increase wait for few hours or a day

the point is that it's saying it is unrated

No, you are rated for this contest and most probably get a negative delta in this round...

ohk! thanks

Can anyone explain why me solution got AC? it has a time complexity of n^3 https://codeforces.com/contest/1915/submission/239328701

WOW, the size of vector d is 1e13..... I didn't know we could make a vector this big.

no idiot it's n sized vector with each element equal to 1e13

My bad :)

Why haven't our profile ratings changed ? My rating is 870. It should've boosted or decremented my rating

Will there be system testing for this round?

Is this contest Unrated?

mesanu

flamestorm

SlavicG

Where can I find the editorial? or is it unavailable

editorial

Hi, can I know when will be rated? I just participate this contest yesterday, but my profile rating didn't change til now

I don't know accurately but i think it Wil take 6-7 hours more

Thanks bro, maybe I should be more patient

thank you!

One person has been abusing me by sending messages because I hacked his/her solution in this contest. Is there a way to report that person?

For anyone who wants to know more about similar problems like G.

Here is a great blog on shortest path modelling:

https://codeforces.com/blog/entry/45897

Editorial when?

editorial

Thanks, where is it published. I cant find the link in Contest Announcement

They have not published it yet in this post NeverSpot gave me the link I can only find it through the contest author's blog

When will the rating get released?

I solved 5 out of 7 problems and they were accepted. Now it shows only 2 out of 7 were submitted ? What the hell. I just checked 3 hours ago it showed 5 out of 7 were accepted

don't worry system is retesting them again

I analysed and realised that any submission after 40 minutes was being ignored by the software system

system testing is going on, wait for sometime

Is it possible for a solution to be rejected due to TLE during system testing even if the submission was earlier accepted during the contest ?

Yes

During the contest I solved 4 questions but now it is showing that I solved only two questions somebody kindly help

System testing

I would like to ask why this submission receives a WA in the new testcases (C) https://codeforces.com/contest/1915/submission/239236542

You are typecasting to double, so it is possible that some value which is not perfect square can also match(due to precision issues). You had to typecast to long long. If it was a perfect square, then only it will match

Oh, it is quite a silly mistake lol. Thank you very much!

thank you!!

Bro rip lmao A-E was easily doable in an hour. Failed E because of using unordered_map and in C forgot to use long long once.