Hello Codeforces. Hoping you're having a wonderful day! ^_^

# DYTECHLAB Cup 2022

This October, we invite you to the **first ever Dytechlab Cup 2022** that will start on Oct/07/2022 17:35 (Moscow time). The problems were prepared by members of our company who *share a passion for Competitive Programming*. It is an open and rated round for both divisions.

The round will consist of **7 problems** and will be **150 minutes** long. We wish everyone good luck and have a positive delta!

### Prizes

- 1st place:
**US$200**cash prize - 2nd place:
**US$100**cash prize - 3rd place:
**US$50**cash prize

Also, we understand that contestants like dope **MERCHANDISE**, so we are giving away lots of them!

**Top 20**will get a merchandise package which will include: a t-shirt**with your Codeforces handle on it**, a notebook, 2 pens, and a sports bag.**30 merchandise packages**, each including a t-shirt & 2 pens will be*randomly distributed*to 30 contestants ranking 21-200.**100 merchandise packages**, each including a sports bag & 2 pens will be*randomly distributed*to 100 contestants ranking 201-1500.

All packages will include stickers in it, so you can stick them to your laptop and show your friends how hardworking you've been :p

### Our appreciation goes to

- MikeMirzayanov for the Codeforces and the Polygon platform.
- DmitryGrigorev for coordination of the round.
- magnified for one of the problems and your enthusiastic support in preparing the round.
- tlsdydaud1 for one problem that fills in the gap to finalize the contest.
- ngfam_kongu, MofK, ladpro98 and every other Dynamic Technology Lab member who helped in coordination, was spot-on while we were working together in the office and helped me come up with ideas for problems.
- The list of testers (still updating): KAN, Elite_Vanor, HmmOrange, Kuroni, .DucAnh., LetterC67, nguyentien_zzz, VanIOImaster153, ngd.nam, nigus, hank55663, BacHoCuuPikachu, ocortez, kieusontungcva, baguettes, stevenkplus, MagentaCobra, dorijanlendvaj, djq_cpp, ugly2333, gyh20, TomiokapEace, SSerxhs, jeroenodb, willy108, abc864197532, -skyline-, tlsdydaud1, ak2006, satyam343, Andreasyan, emorgan5289.

**Wish you the best and a very positive delta in this round!**

**UPD:** score distribution is: $$$500 - 1000 - 1500 - 2000 - 2750 - 3500 - 3750$$$.

**UPD2:** Scripts to generate ranks of random prize winners. Seed $$$x$$$ will be the **sum of score of the top 10 participants**:

`./genrandom_winners x`

**Scripts (genrandom_winners.cpp)**

**UPD3**: Editorial.

The total score of top 10 is: $$$11460 + 9086 + 8829 + 8609 + 8380 + 8354 + 7511 + 6874 + 6775 + 6755 = 82633$$$. The **list of ranks** of prize winners is fixed and you can check using the published code above, using the total above as a seed. I will make a list the following days and contact the prizes winners! PLEASE NOTE that the list of real winners only finalized after the system detect & remove cheaters!

**Congratulations to everyone and HAVE A GOOD WEEKEND!**

**UPD4:** standings

**Winners:**

Place | Participant |
---|---|

1 | tourist |

2 | ksun48 |

3 | orzdevinwang |

4 | inaFSTream |

5 | heno239 |

**First to solve:**

Task | Participant |
---|---|

A | manish17_ |

B | tourist |

C | Y25t |

D | platelets |

E | EternalAlexander |

F | gisp_zjz |

G | rainboy |

# About Dytechlab & Job Opportunities

*If you are interested in employment opportunities in Eastern Europe, Dubai, or South East Asia, please fill out the contact form below*:

**We are Dynamic Technology Lab, Pte Ltd. (DTL)**, a *quantitative hedge fund* engaging in global securities trading with multiple asset classes. Since our founding in 2009, from humble beginnings in a home garage, we are now a **sizable**, **well-established financial institution** with offices in **Singapore**, **Shanghai**, **Beijing**, and **Hanoi**. Our success is fueled by some of the most inquisitive minds who are relentless in their pursuit of innovation.

As a **tech-focused Licensed Fund Management Company** under the Monetary Authority of Singapore, DTL is dedicated to producing strong consistent returns for its investors by relying on mathematical and statistical models to drive its investment process.

Right now, we are looking for lots and lots of Engineering positions and are ready to bring opportunities to work in a quantitative trading environment for Engineers of all levels, all around the world!

Auto comment: topic has been updated by low_ (previous revision, new revision, compare).Auto comment: topic has been updated by low_ (previous revision, new revision, compare).As a tester, I can assure that the problems are original and interesting. Good luck :)

May the contest good, bro

As a coauthor, wish you the best and a very positive delta in this round!As a tester and not a co-author, the problemset is very amazing and you should participate in the contest!

ok bro

problems are

SpoilerSo you spent 28 minutes slove a?

Around 15-20 minutes actually since I was interrupted while testing. I did suggest the setter add 1 more problem before A as it is pretty hard for A. But personally, I find this problem not as bad as others say, just misplaced.

Sir, a genuine question.

i don't have experience. i am currently a fresher.

Can i still apply for the job?

what are the things that you are looking in a candidate. Does codeforces ratings matters?

Please reply sir a humble request.

Hi! Unfortunately, contest coincides with BOI (balkan OI) (and RMI) contest day 2/closing ceremony.

I really would like to participate, and I think some other participants too.

Is it somehow possible for contest to be shifted 1-2 days? Or any other posibilities of participating for BOI/RMI participants?

TIA

Why is this getting downvoted?

People downvoted me so i downvoted him.

Success makes so many people hate you. I wish it wasn't that way. It would be wonderful to enjoy success without seeing envy in the eyes of those around you.

TimDeeSooo trueee!!

btw who are you?

cadmiumky

bIeahbIeah

Marinush

Sorry if you are a successful person i didn't know it.

neoromantic social fresco

i tried but couldn't understand what you said

Hi. I'm so sorry your comment got downvoted so much. It has a great point!

However since there are so many things going on around the world, contests conflicts are very unavoidable. We've spent a lot of thoughts on the contest dates, and found out that Oct 7th is the best option.

Once again, I'm sorry that you (and a lot of contestants) are not going to make it because of BOI or RMI. We, at Dytechlab, really hope that you can virtual participate our contest afterwards.

Good luck at BOI and RMI to all contestants involved ^_^

Daniel.

Thanks both for your wish and for answer! I'm sorry too that I can't participate, but thanks for your job for contest and good luck in hosting your contest :D

Tim :)

The contest takes place during working hours for people in the American time zones. Given how rare contests rated Div. 1s are (the next one is in a month), it would make more sense to schedule it on a weekend, when more people can participate.

Weekend conflicts with Meta Hacker Cup round 3 and many other big contests like AtCoder's regular. Nevertheless, I'm very sorry for you or anyone won't be able to participate in ours!

Thank you for your amazing work!

Contest problems have a wonderful quality :)

Auto comment: topic has been updated by low_ (previous revision, new revision, compare).Auto comment: topic has been updated by low_ (previous revision, new revision, compare).As a tester, I hope everyone will like the problems as much as I do. Good luck winning some cash and merch!!

Auto comment: topic has been updated by low_ (previous revision, new revision, compare).How much rank is needed to get an interview call?

1

They are not answering the important questions.

Auto comment: topic has been updated by low_ (previous revision, new revision, compare).The contest wait for 2 months to launch

We like to make early moves :D

What about the score distribution ?

Will be announced later today :p

How to determine the random prize winner?

We were gonna just use random scripts with time seed to randomize winner indices on the sorted array of prize winners in each session.

I think you should publish the seed to ensure transparency, and also select the seed in a way that ensures that it is not biased (i.e. the last submission number)

I noticed, many programmers like anime. Right?

Not me :smile_sweat:. How does it relevant to this blog?

Sorry for irrelevancy. It was just curiosity.

Auto comment: topic has been updated by low_ (previous revision, new revision, compare).As a guest setter and tester, I leave no comment about the round.

Thank you for your contribution! =)

Auto comment: topic has been updated by low_ (previous revision, new revision, compare).I like this Score Distribution : 500 — 1000 — 1500

Is it rated??

Yes, Read the statement carefully. It is an open and rated round for both divisions.

Yes, of course, see the title:

## [Rated, Prizes!] DYTECHLAB Cup 2022 Round Announcement [Div.1 + Div.2]

so, it will be very:

## nice!

Is is going to be rated?

Yes, of course, see the title:

## [Rated, Prizes!] DYTECHLAB Cup 2022 Round Announcement [Div.1 + Div.2]

so, it will be very:

## nice!

Hope the statements would be clear this time!

What kind of contests is this? And what is its level??

It's the DYTECHLAB Cup 2022, from which you can infer that it is sponsored by DYTECHLAB

Title says Div.1 + Div.2. Basically it's rated just like any other combined/global rounds.

Good luck everyone :)

there is interactive, isn't it? pray for "no interactive" :orz:

Auto comment: topic has been updated by low_ (previous revision, new revision, compare).More DP problems can be expected form DTL?

What with prizes in Russia?

Any guess who is winning this round with the competition being so stiff these days for the first position . Let's enjoy this round as well !!. Good luck to everyone !!

My stakes are on legendary Um_nik :>

As a participant, good luck to everyone. Hope the problemset will be great!

Just focus on first three problems for me. XD Good luck for everyone！

Can’t participate because I’m in school, but good luck to everyone participating!!!

Auto comment: topic has been updated by low_ (previous revision, new revision, compare).Around $$$10$$$ minutes left. The method of finding prize winners randomly is PUBLISHED.

Please check them out!

Problems are hard for me ;(

I'm sorry but currently C is the worst problem I've seen.

fact

I know what to do but can't code , what a shame on me ;-;

Why super long statements? Don't even want to read

Thanks for the round, hate it

Bad Python, Bad Python!

In Problem E -> For each position in the line, calculate the probability that the ant begins in that position and survives. What do you mean by for each position?

At this point C is making me question my entire life

you should remove "+ Div.2" from title

They forgot to prepare "a" problem

Why Problem C???

from what i saw in the comments thanks for putting A problem it was a good indicator for me to quit ( don't say its bad round so, but for sure this one of most toughest rounds i saw)

I couldn't code A, XD. given that i am able to solve div 2 C somewhat comfortably.

agree i don't say im good enough but thinking for more than 45 minutes in how to implement A made me leave the contest even after i thought i was near to solve it in my opinion A wasn't in its place and i was lucky to not participate

same, read the statement for 10 minutes.

yep same, thank god i quit

C might be the worst problem I have ever encountered, Problem A way too difficult for its position. Bad contest.

pure div1 round in the name of div2

POV: You join this company and you don't even understand your tasks

i might get down voted for saying this but i don't really care at this point.

this was by far the worst contest i have ever participated in.

i also think that round should be at least unrated for Div2, i think more than half of the people who registered saw problem A and left.

When i first saw $$$A$$$ I was scared, but it ended up being easy (because I managed to understand it quickly)

The statement is a bit complicated, I don't know why..

Sorry, but this is the worst contest I've ever participated in.

Also, C is the worst problem I've ever seen in a Codeforces contest. And A is the hardest A I've encountered.

How have you arrived at your conclusion that C is worst?

reading forces.

bye bye

Div 1.00001

Did Ela not participate in the problemsetting :thonk:

Ela definitely did a great job that day and made her family, her boss, her company and the whole community proud!

difficult "A" forces

POV: writing solution for C in 10 minutes, then looking for a bug in code for an hour and a half (mixed up $$$x$$$ and $$$y$$$ somewhere)

There are so few people in the contest. Why is that？

because of 'a' problem.

A Is the question really that difficult?

No, but words like "MEX of a multiset consisting of letters" prolly made newbies skip this round

Good first 3 tasks but too hard for being first 3. In C tried to handle not squared board case and lost 20 minutes XD

speedforces again

Problems are standard for Div 1 but relatively hard for Div 2 :(

(deleted)

I can tell it here. Do you want to know?

I used to think that switching to Python from C++ in a competition would be almost impossible to happen.

This contest made me change my mind.

p.s. I think I have a partial solution to F, but I would have needed the whole 150 minutes for solving it completely

solved A, B, C. D was not clear to me sadly. I did not even understand the theory of reconnecting wires after 40min. I don't understand why the solution for the 3rd testcase is 154.

it uses the edge weighted 22 repeatly

Can anyone give some hints to solve D? I was sensing some kind of DP in it.

For case 3 in problem D,who knows how to get 154?

Same experience as you

Re-wire the edge of weight 22 as follows:

2-5 -> 2-6 -> 2-7 -> 7-7 -> 7-4 -> 7-8 -> 1-8

Then move along 1-8, these are 6 re-wirings and one movement along the edge of weight 22 = 7*22 = 154.

Then send the data over the (1,8) link for 154.

22*7 just think

Hint : $$$22 \times 7 = 154$$$

(Prime) factorizationing of solution is sometime useful

You can cut the edge $$$[2,5]$$$ and link $$$2$$$ to $$$6,7,1$$$ successively. Then cut $$$[1,2]$$$ and link $$$1$$$ to $$$7,4,8$$$. After that you got edge $$$[1,8,22]$$$ and the tot cost is $$$7 * 22$$$

Can't even solve one question. :(

What's the meaning of D? I can't calculate the answer of the third sample over 2h .

C is a chore to do :( D was pretty cool

.

Nice problem I liked problem b let's hope for no fst

Didn't have enough time, but again E seems waaaay easier than D. Also is using built-in sqrt causing WA in B???

That might be the case because of numbers till 10^18. Use sqrtl(n) for long integers.

Nope, my submission works perfectly fine.

Yes, my submission got FST because of that.

Test Case: 1 1e18-1 1e18

About B, yes, I just changed my code from

`sqrt`

to`sqrtl`

after the contest, and it got acceptedYou can also use

`sqrt(x+0.5)`

for calculating square root of x for even x be in long long int. It will removing error from square root function. I just use this and got Aced. This will even help in large number where sqrt fails due to large calculation and help in such case with this small adjustment gives you right answer.That's why i got it only an hour after i actually solved it :)

Yes i struggled to debug because of this builtin sqrt function.

initial submission : https://codeforces.com/contest/1737/submission/175034571

final correct submission afer using sqrtl : https://codeforces.com/contest/1737/submission/175036179

I'll say politely :

Spoiler" I HATE SQRT FUNC WITH

999999999999999999!!"It took me about 30 minutes to figure out that sqrt in C++ does not give me what I want.

Yupp Same.it really hurts when you reach to solution's idea ,then a hardly observable wrong prevents u to get it in 1st time :""

## define sqrt(n) sqrt((long double) n)

Such define can help)

I do not know if other people share my opinion, but I feel like problem A has become much harder than it should be. Problem A, in my opinion, should be solved by most people; otherwise, people might start getting discouraged, and this is of course not the intention of the people who prepare the contests.

Problem B: https://oeis.org/search?q=1%2C2%2C3%2C4%2C6%2C8%2C9%2C12%2C15%2C16%2C20&language=english&go=Search

...I think consulting the OEIS actually makes it harder than to simply exploit the property that there are exactly two luxury numbers between consecutive square roots. Proof: $$$(a + 1)^2 = a^2 + 2a + 1$$$, so the luxury numbers between $$$a^2$$$ and $$$(a + 1)^2$$$ are only $$$a^2 + a$$$ and $$$a^2 + 2a$$$.

I suppose the OEIS might help with observing the pattern to begin with.

On the topic of B, I hate precision errors in the C++ built-in

`sqrt()`

function >_>I just added up the floored values of the inverse functions, which are $$$\lfloor \sqrt{x} \rfloor$$$, $$$\lfloor \frac{\sqrt{4x+1}-1}{2} \rfloor$$$ and $$$\lfloor \sqrt{x+1}-1 \rfloor$$$. In this sense, it definitely helped.

This is exactly why I used Python for B, there's the

`isqrt`

function for $$$\lfloor \sqrt{x} \rfloor$$$ and it always works ;) Next time you see it, you'll know it!Or you could just use sqrtl function in c++ smh

wrong answer b problem pretest 4 cause using c++20 instead of c++17 wasted alot of time i want the c++20 submissions fixed to gain the rightful rank in the contest

yes it should not be hacked

Did you use a function like

`sqrt`

(or`sqrtf`

,`sqrtl`

)?yes i did

pretest 4 was annoying, happened in Java as well. In java it was caused by imprecision of double for big numbers.

For small numbers this works:

for big numbers you have to adjust:

(this took me 20min, very annoying. I have no clue why the input is chosen in such a way, that some languages have an additional barrier)

Is there any language in which this barrier does not happen?

mostafag649.mg said he did not have the problem in C++20, I assumed some c++ library was handling that case.

i found it is problem with sqrt we should use sqrtl if passed by compiler c17 for for pretests but gives wrong in test case 11 please handle this problem

you have to handle the problem lol. Test case 11 has nothing to do with sqrt.

Here is a fix for your solution: https://codeforces.com/contest/1737/submission/175036144

https://codeforces.com/contest/1737/submission/175013307

here is an AC submission for C++17

then how come it is accepted by using sqrtl

and another thing these code wont get accepted by c20 if you try

https://codeforces.com/contest/1737/submission/175036760 see this is your code and wrong using c20 so please anyone handle these problems and try to compensate us!!

why are you asking me. I don't care, I don't organize the contests and if anything, it is your responsibility to solve it.

rude reply!!

how about you fix the contest

Chill bro, don't cry for few internet points. You'll gain +ve delta in some other contest.

In problem $$$B$$$, am I the only one who got WA and wasted a lot time because of using built_in sqrt() function instead of binary search ?

Just figure it out in last 3 min but it says wrong answer not TLE as sqrt take root(x) time to compute then TLE should be there na

I think the problem description of this competition is very unfriendly. I spent a lot of time reading the questions instead of solving them.

Can somebody please show me a case where I got the WA :((( 175029197. I got the WA on pretest 4 :(( Sorry for my bad English :(((

Anyone in B probelm is getting mistake at pretest 4 anyone did face same problem iam also not able to figure it out where it goes wrong

You can try using sqrtl instead of sqrt. Better, use binary search to find square root.

I wouldn't trust

`sqrtl`

either, although it seems to be precise enough. Use binary search to get the square root of a number.isqrt gives integer square root

...in Python.

sorry, my bad, braindead moment

I never expected to get WA because of sqrt(), but I learned a good lesson, and I will use binary search next time.

It was a very strange round to me

Please don't do contests anymore.

Whats the logic behind problem A?

First, count the number of occurrences of each letter.

Then for each compartment, try to fit in one book of each letter, starting with

aand moving up. Decrease the count accordingly. If you reach a letter with a count of 0, then that letter is the largest possible MEX for this compartment (there's no way to get a higher MEX if this letter is completely absent by the time you arrive at this compartment). Then move to the next compartment (even if you didn't finish filling up the previous one, since the MEX would not change and you want more books available for later compartments).If you were able to fill up a compartment (i.e., with the first $$$n/k$$$ letters), then the $$$(n/k + 1)$$$-th letter is the largest possible MEX for this compartment.

My submission: 174993937

Thanks

just make a function to find mex for n/k length substring ,find minimum character which you can't make at any index or stack as per question and just add n/k mex into new string and output it.

Bruh, They are making A so bad these days that B seems easy to understand and solve. Why complicate with such a big problem statement for a starting problem and involve all sort of confusing stuff.

Why the number of participants is so low? How is this going to affect rating range?

On question F, I mistakenly thought that 1 is also a prime number, and I didn't have time to revise it in the end.

WTF is pretest 3 for C??

I don't know, since I got AC in my first attempt, but an edge case to consider is when the corner of the L-shape is in the corner of the board. Then no diagonal jumps are possible, and the only reachable tiles are in either the common row or the common column of the three locusts.

Aside from that, there aren't really any other edge cases, I think. As long as L-corner isn't a board corner, the reachable locations are those whose row number or column number have the same parity as the common row or common column respectively of the locusts, or locations that have the same chessboard color as the cells of the diagonally-aligned locusts. Maybe some cases here weren't covered in pretest 2?

That's exactly what i did...XD Btw..congrates on getting AC!

Consider the case where locusts are placed on (1,1), (1,2), (2,2) in a board of let's say, 6*6. Note that, the statement: "the only reachable tiles are in either the common row or the common column of the three locusts" won't be true here, even when "one of the three locusts is in the corner of the board".

The only edge case is when "there is no diagonal jump possible". Only then this statement: "the only reachable tiles are in either the common row or the common column of the three locusts" holds true.

Hope that helps you.

My bad, I actually meant that the corner locust is in the corner of the board. Thank you for pointing this out.

in (1,1), (1,2), (2,1) what should be the next move as here nor the diagonal movement is possible nor the "plus" movement as it would lead to its distortion. Please guide me if I am wrong.

holy f**k I doubted myself on that the three locusts could totally disband into two locusts and one apart. sad thing...

I got all of those cases right but still WA 3 >:<

Take a look at Ticket 16252 from

CF Stressfor a counter example.Are we supposed to know that the built-in square root function does not work as intended? Spent over an hour thinking of ll overflow and wrong solution and whatnot, was an extremely unenjoyable two hours for me

True.. I even stress tested B until I convinced myself to do a binary search instead

never trust floats. I calculated it like this with no binsearch:

It doesn't get tle because sqrt is precise enough, but probably is better to have some sqrt with binary search implemented

Kept getting WA in problem B because of $$$sqrt()$$$ 🥲

The only time I do well, my solution to B FST...

:(

How are we getting 154 in sample 3 of problem D?

B hacked due to inbuit sqrt fuction

Using the inbuilt sqrt function is incorrect since it is not precise enough. Incorrect code

shouldbe hacked.yes you are right , I will learn from it for future contests.

Hello sir, can you please check out this comment. I tried to hack one solution and I think there is still some problem in system tests of problem B. Correct me if I am wrong.

Sir many people have done the same mistake,they will not be hacked as contest is now over.

Hacks get added to the system test.

Is system testing completed ? Because the test case on which my solution hacked is also giving wrong ans on other person and that has not been hacked .

example : https://codeforces.com/contest/1737/submission/174997699

caseforces

Such a ride!

I'm humbled for your support & participation for today's contest!

I've read all of your comments, one by one, and took them with my head held up high. It's a great experience and pleasure to serve the community with this Rated-for-everyone contest.

There's a lot to learn from from this experience, so all I could say now is thanks to all who were with me throughout the long journey, and see y'all next time!

Have a good night, haven't slept properly for days :icant:

Good job, thanks for making the contest.

Everyone's experience is subjective, but unsatisfied people would be more prone to share it, so don't take it to heart if there are more negative than positive comments. Other than problem C, I found it a pretty cool contest and I thank you for making it. Get some well-deserved sleep.

Hello sir, can you please check out this comment. I tried to hack one solution and I think there is still some problem in system tests of problem B. Correct me if I am wrong.

Apologies for repeated comment.

Did you missed a problem between E and F and a problem before A ?

I think they accidentally swapped A and B.

Tasks A and C were very unpleasant. So much casework...

A is slightly annoying, but I don't see any casework.

Finally won't be a specialist after 10 months.

What should be the right answer for following testcase for problem B

In my opinion correct answer should be 2999999996. I tried to hack solution 174996872 on above testcase. The above submission is giving 2999999997. But still it gave me unsuccessful hack verdict.

Yes , my answer is also 2999999996.

2999999997 is the correct answer

I don't know why the solution give 2999999996 in codeforces's judgement.

what's problem with java in problem B. i have wrote same code in C++(Accepted) and java(WA). wasted 40min :/

C++ solution: https://codeforces.com/contest/1737/submission/175008748

Java Solution: https://codeforces.com/contest/1737/submission/174996178

Since the precision of the double type in Java is guaranteed to be at most 15 digits, there may be cases where digits are dropped.(I got the same WA.)

For example Math.sqrt(999999999999999999L) → output : 1.0E8.

Problem D and E are great , I think.

Problem A is very boring I think , it just tests foreign participants's English reading abilities，and take long time to solve it , and it's harder than B . That's confusing to put this problem at A.

And why not to put explanation to sample 3 in D ? Very petty ! It helps a lot to participants。

(As a Chinese student , my English is bad. TaT)

I got stuck on sample 3 of problem D for almost two hours.

The Problem E is copied from a Chinese OJ.

https://noip.ac/rs/show_problem/3225

(The problem isn't available for everyone,so I post the image of the statement)

Only the output format is not the same.

You may calculate the input result with n=5 in the input with the method of output.

So the contest is unfair and it should be unrated.

Problem B was also copied from AMC math competition. I will send link here once I find it.

https://oeis.org/search?q=1%2C2%2C3%2C4%2C6%2C8%2C9%2C12%2C15%2C16%2C20&language=english&go=Search

Make it unrated due to problem theft MikeMirzayanov

It sounds reasonable.

But I don't know why people are downvoting you.

But if there is no evidence that the problem was intentionally copied, the round is unlikely to be unrated .

Is the sample input the same? The OJ doesn't load for me.

No , the output format is not the same. And it is single test.

The input and output format not same.

Why is the problem not available for everyone?

That's from a contest of a course that is not free.

Oh. I really don't like contests that are not free :(

That is common in China :(

The author is not from china, is other place this problem?

Actually this problem is almost the same as UVALive7505. It seems to come from Asia ec final 2015 but I’m not sure because I can’t get the problem set from icpc.global.

I believe the writer didn’t mean to copy this problem and I’ll feel sad if the contest is unrated. If it happens, it will be the second time for me to participate in a round unrated for unsolved problem for me, and in just few weeks.

This is a private online judge.

Maybe the problem writer might not mean to copy the problem.But some people have seen this problem.

Cant blame the author for Chinese problem database already having all problems in advance that will appear in next 10 years

what do you mean by your last statement?

Nice experience :)

C was a crap

Problem B was copied from a math contest

Provide the link please

I don't think this will make difference.

It feels like this idea is very common.

Then why include the question? I feel like the question is more of a knowledge check that we know sqrtl (which frankly, I didn't), than a math problem.

These knowledge checks are really annoying (ex. checking parity of negative numbers with x % 2 == 0), and they turn a good problem into a test problem. I understand that authors want the contest to be educational, but why not just include it in the pretest? It feels like they purposefully want to make us fail FST.

Imagine thinking about a problem for an hour, finally passing all pretests, just to fail system test because of some weird C++ behavior that you have never even heard of...

Thank god O(n^3) was enough to pass D.

Guys, is problem D related something to Dijkstra algorithm?

I think it's related to Floyd Warshall Algorithm.

Why do we have to find all pairs?

The problem statements are so bad jfc. Bet authors are used to friendzoned by girls and wrote walls of text explaining his feelings.

I was very surprised to see $$$n \leq 500$$$ in problem D, my solution is $$$\mathcal{O}(m \log m)$$$ using just Djikstra, and it'd be simple to improve to $$$\mathcal{O}(m)$$$ as everything is run on unweighted graphs.

First, compute for every vertex $$$v$$$ three values: $$$\text{so_dist}[v]$$$, $$$\text{si_dist}[v]$$$ and $$$\text{bo_dist}[v]$$$, where the first is the (unweighted) distance to the source (node $$$1$$$), the second is the unweighted distance to the sink (node $$$n$$$), and the third is the unweighted triangle distance between the source, sink and node $$$v$$$: the minimum of $$$\text{dist}[1][x] + \text{dist}[n][x] + \text{dist}[v][x]$$$ over all nodes $$$x$$$. The first two are easy to compute in $$$\mathcal{O}(m)$$$ with a BFS, the third can also be done with a BFS: add a new source, and an edge with length $$$\text{dist}[1][x] + \text{dist}[n][x]$$$ to node $$$x$$$, then compute the length of the shortest path from the new source to $$$v$$$ for every $$$v$$$. Since the distances can only be up to $$$3n$$$, this is also easy in $$$\mathcal{O}(m)$$$.

Then, loop over edges. For edge $$$(a, b, w)$$$, you have four offers for the answer:

The answer is the minimum offer over all edges.

This holds, since after the operations WLOG the path we take is a direct edge from $$$1$$$ to $$$n$$$. If at some point during the operations the two endpoints of that edge were in the same vertex, the answer is at least $$$\min\left((\text{bo_dist}[a] + 2) \cdot w, (\text{bo_dist}[b] + 2) \cdot w\right)$$$, otherwise it is the minimum of the other two terms.

Submission: 174999462. My code uses Djikstra instead of BFS, but as mentioned above, BFS is an easy replacement.

I apologize for some issues involving task D.

Let me tell you a bit about our last 24 hours.

We didn't write a brute force solution until last night (it is partly my fault since I was too confident about the main ideas). In our previous (of course, fake) solution, only two cases were considered: $$$(\text{dist_1}[a] + \text{dist_n}[b] + 2) \cdot w$$$, and $$$(\text{dist_1}[b] + \text{dist_n}[a] + 2) \cdot w$$$, and nobody was aware of the triangle path in the third sample test.

And that is ridiculous. About dozen GM (incl. LGMs) tested this problem last week, and no one noticed that tricky case too. We didn't have enough time to find a good solution for $$$n \le 10^5$$$, so Floyd algo was utilized instead. Thanks for sharing your ideas (ty), but imo the problem will be too hard for an ordinary D if the constraints were raised like that.

A bit later than ideal but great job on essentially saving this contest at the last minute. Authors, write your brute force solutions!

D was one of the best problems in the round (probably harder than E, even with the small constraint).

Problem D is hard to understand in my opinion. The output of the third test case is quite unclear. But I guess once figuring it out the procedure of the third test case, the solution will be obvious.

Can anyone please give me some hints about problem D. Seems like some modification of Floyd-Warshall.

A is basically a reading exam. B is total garbo. No logic whatsoever. Literally just have to print and find pattern of 3 C problem statement 1/10. Solution is just case work.

wondering if authors obsure the simple problems with text bc he stole problems elsewhere

C is also a reading exam.

And D is the hardest reading exam, OK? I spent two hours understanding D.

What could be the possible rating for C ? Any guesses

Why is A too hard in every single round? Newbies just give up and the number of participants decreases, which makes all participants' performance and delta lower

Trap to make newbiews give up T_T

It also skews the rating of the problems. Imagine somebody new to Codeforces starts trying to solve problems, looks for the most recent 800-level problem, and finds this Problem A >_>

(and yes, I think it is justified for one to look for recent 800-level problems as opposed to sorting by #solves, since the latter tends to favor ancient outdated problems that are not a good indication of what to expect in present contests; but if recent 800-level problems are as hard as this, there is no actually good solution to this predicament...)

Why do you say that participants rating or problem's rating decreases because of newbies leaving? It makes little sense if any at all

That said, A still should not discourage half of the participants.

A participant's rating depends on how well they performed relative to how other participants performed (as well as other factors like their current rating). Similarly, the rating of a problem depends on the performance of participants on that problem.

However, only those who have made a submission would be considered as active participants. For example, let's say, hypothetically, that only 10% of those who intended to participate in the contest would have been able to solve D. But of the remaining 90%, let's say two-thirds of them were not able to solve A quickly and decided to quit the contest so that it is not rated for them (fearing that their rating would drop). So only 40% of the original number of people are actually considered, so those who solved D would be considered as being 25% (instead of the actual 10%). Being one of the 25% of participants that solved a problem is not as notable as being one of the 10% of participants that solved it, and the rating changes reflect that as well.

Similarly, let's suppose that only 10% of participants were able to solve A in ten minutes. But then most of the other participants decided to quit because they couldn't solve A fast enough and it would hurt their rating if they made a submission. So maybe, as a result, it turns out that the 10% who solved A in ten minutes end up becoming say, 90% of the participants that are considered (made a submission). So now A's rating is based on this excellent performance of 90% of the participants solving it in 10 minutes, and it might get a rating of 800 or 900 as a result, as if it's a really easy problem, when it's actually a much harder problem that caused many to ragequit.

These may be extreme examples, and the A here isn't as hard as some of the other recent A problems, but the point still stands that making A hard enough to discourage a significant portion of the participants ends up skewing the contest results, and its impact on participant rating changes and problem rating evaluation.

I'm so happy that I didn't give up even though a took me about one hour:'

this C gave me cancer

can anyone please give me a hint about B

$$$(a + 1)^2 = a^2 + 2a + 1$$$

How many luxury numbers are there between $$$a^2$$$ and $$$(a + 1)^2$$$?

What is the criteria of random distribution of the goodies :)

I am eagerly waiting for the first "random" merchandise packages.

Can Any One Explain the logic of Problem B of using Binary Search .Because I blank in this Question

if x * x > y, then you know x is bigger than floor(sqrt(y))

You try to find the biggest x, that is not bigger than floor(sqrt(y))

What is wrong with problem C statement, I took 1 hour just to understand statement(maybe my skill issues)!!! There is nowhere mentioned whether it is necessary for all three cricket to stay together till end or not? and that jump over statement.

The sqrt function of C++ just destroyed the contest for me.

It was already destroyed for me, but sqrt destroyed it even more :)

is hacking phase going on ? because many people used sqrt but they are not hacked while I was hacked .

I expected that sqrt is the problem because once double didn't even catch just 0.5 after number smaller than 10^9 so i checked by doubling the sqrt to see how retarded is this function's value

Is hacking still on @Jhin ?

No this isn't educational round or div3'4

then why solution is showing hacked ??

It must have been hacked during contest maybe last minute and you didn't notice

yes I closed my laptop after I solved the third one :(

Same for me. Could have become an Expert today, but alas!!!

Nevertheless got to know about sqrtl funcDon't make competitive programming problems ever again

I think that recently problem A become more difficult and take more time, so it's so frustrating.

In problem b, c++ builtin sqrt does not work (sqrtl need to be used), spent 1 hour there. overall the contest was pretty bad for me.

Builtin sqrt did work. You can checkout my submission

may be it only has issue with c++20

or you can use c++17 i also wasted all of my time. i don't know why it's working fine in c++17.

i have used c++!7 still hacked !! 1 200274443973227574 485348695690455822 actual answer : 747448170

Same, I got AC on the pretests and WA on test 11 after contest ended. Changed to sqrtl and got AC :/

The contest was enjoyable. Problem D was quite fun, and I also enjoyed E. I think it is easy for people's view of the contest to be obscured if they only looked at ABC.

D and E were really great, although i couldn't solve but had fun trying those

I wasted all the contest trying to know why B doesn't work. After the contest I changed the compiler from 20 to 17 then it worked.

The contest was very bad for me.

bro i have used c++17 during contest i was hacked

try this : 1 200274443973227574 485348695690455822 actual answer : 747448170

D is amazing! E is also nice. Thanks for the round!

I tried to solve question 2.5hrs but couldn't solve it. Ratings will decrease.

I'm actually glad that pretest 4 destroyed precision issues in C++

`sqrt`

, since otherwise, solutions that depended on`sqrt`

would get pretests passed, and likely would get FST, since I'd expect there to be some hacks that exploit`sqrt`

precision.That being said, I have doubts on whether it is appropriate for a B problem to require a more accurate way of calculating square root (like binary search), or a similarly complicated approach to solving this problem without computing square roots.

I have used sqrt and passed all the system tests.

I didn't use any method to get sqrt, I just used some pattern and found it based off that.

I have used sqrt but it was accepted for me

In the second half of the match, I replaced sqrt with binary search, which dropped my ranking from 700+ to 1400+, but it was proven after the match that what I had originally done (sqrt) wa in the 11th test point.

I made a stupid mistake on C. I considered the edge case as having the 'missing' square on (zero-indexed) the 4 coordinates of (1,1) or (1,n-2), (n-2,1) and (n-2,n-2).

Instead, I should ALSO check if the 4 corner coordinates are occupied.

I have noted a glitch in the codeforces compiler leading to my failed on main test cases verdict. In the question B , whose link is this, my solution which passed on pretests is this

After running on main tests , it showed wrong answer on main tests 11 .

I checked the error and found it is giving wrong answer in this test case : 77921270569329490 377318254283917957 Its correct output is : 1005355647 while my code on codeforces compiler gave the output : 1005355648

I copied my code and ran it on every online compiler I know as well as my local compiler and everywhere it gave the correct answer, while in codeforces inbuilt compiler it gave wrong answer.

I tried to dig further in it and found that it is not even printing the square root of 77921270569329490 correctly (which is 279143817, but its giving 279143816), which is taken care in all other compilers.

This glitch lead my answer to fail in main test cases.

If the moderator is viewing this, please check my submission on different compiler or do something about it. I do not want my rating to go down for no reason while it could have gone up.

This happened to me.

In fact, this may be a reasonable error. Because the accuracy of sqrt is not guaranteed.

Finished C 8 seconds before contest end and wasn't able to submit because CF was loading like a shit. RIP rating :(

Before this contest, I thought that if a solution to a problem "count number of numbers between l and r that satisfy a property" works for l=1 and on random test cases, then it always works. This contest gave about 1000 counterexamples to that.

Never be using sqrt again. Ac with sqrtl() and wa on main test with sqrt. But pretest was passed with sqrt.

My day is ruined :(

unpleasant contest unfortunately copied problems from other sites problem E is copied from a Chinese OJ.

https://noip.ac/rs/show_problem/3225

problem B is coped from oeis

https://oeis.org/search?q=1%2C2%2C3%2C4%2C6%2C8%2C9%2C12%2C15%2C16%2C20&language=english&go=Search

problem with compilers C17 and C20 problem B

make it unrated such a waste of time

my code is giving right answer on my computer but getting wrong answer on test case 11 when submitted. What's happening? pleased see the code and tell me why is this happening?

https://codeforces.com/submissions/tanvir942316

sqrtl instead and c17 compiler would work

I just have one question for myself why the f### did I participated in this round T_TWhen will the rating change? Is this round unrated?