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.
- gop2024 for coordination of the round.
- magnified for one of the problems and your enthusiastic support in preparing the round.
- blobugh 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, VuaVeNhi, lobotomy, kieusontungcva, ehnryx, stevenkplus, MagentaCobra, dorijanlendvaj, djq_cpp, ugly2333, gyh20, TomiokapEace, SSerxhs, jeroenodb, willy108, abc864197532, -skyline-, blobugh, ak2006, satyam343, Andreasyan, emorgan.
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
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
So 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.
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.
TimDee
Sooo trueee!!
btw who are you?
valeriu
kozliklekarsky
Marinush
Sorry if you are a successful person i didn't know it.
neoromantic social fresco
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!
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
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).
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!
Deleted
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.
there is interactive, isn't it? pray for "no interactive" :orz:
Auto comment: topic has been updated by low_ (previous revision, new revision, compare).
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!
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
Why super long statements? Don't even want to read
Thanks for the round, hate it
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)
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.
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
(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$$$
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
.
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
sqrttosqrtlafter 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 :)
I'll say politely :
" 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
isqrtfunction 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
Did you use a function like
sqrt(orsqrtf,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
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 ?
I think the problem description of this competition is very unfriendly. I spent a lot of time reading the questions instead of solving them.
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
sqrtleither, 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
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 a and 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
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.
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 Stress for 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...
:(
B hacked due to inbuit sqrt fuction
Using the inbuilt sqrt function is incorrect since it is not precise enough. Incorrect code should be 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.
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
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?
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.
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.
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
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.
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 :)
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
Same for me. Could have become an Expert today, but alas!!!
Nevertheless got to know about sqrtl func
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.
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.
D is amazing! E is also nice. Thanks for the round!
I'm actually glad that pretest 4 destroyed precision issues in C++
sqrt, since otherwise, solutions that depended onsqrtwould get pretests passed, and likely would get FST, since I'd expect there to be some hacks that exploitsqrtprecision.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.
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
When will the rating change? Is this round unrated?
Today In the solution of problem B, I got an WA on Final Test. (Test : 11) By analysis i found: for sqrt(185269712007480489)=430429683 compiler giving 430429682(That is one less). As a result answer is getting wrong. Here the submission link: 174994977 Please anyone mention me: What the actual problem is? Isn't it a fault of sqrt() funtion? Or any other?
You call sqrt function with a long long, but double precision isn't good enough for big numbers. Long double fixed it for me. Best practice would be not to use sqrt at all.
I am getting my answers correct on B in my computer.But it is showing wrong answer when submitted.
same is happening with me
WA on B because I used sqrt https://codeforces.com/contest/1737/submission/175026254 :(.
The same code just used sqrtl and got accepted after the contest https://codeforces.com/contest/1737/submission/175041400.
Im never using sqrt again :(.
same happened with me bro
can someone explain to me how to solve problem B logically without trying every single possible equation without knowing what the heck I am doing .....
I did not try the equation, I just noticed the pattern
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).
175010124 This is my solution for problem B it says on wrong answer on test case 11 for l=77921270569329490 r=377318254283917957 and wrong answer 4th numbers differ — expected: '1005355647', found: '1005355648' but when I am running it on my compiler I am getting correct expected answer. Please someone confirm that my solution is wrong or not and if I am correct how can I make this correct on standings?
Please someone help.
change all sqrt to sqrtl and see how it goes
This round made me question my implementation skills ( especially in Problem B, Took around 30 mins to understand and fully code the solution but then gave 1 hr to fix the Wrong Answer on Pretest 4, which unfortunately couldn't get fixed within the contest time, but after the contest, when I watched other people's solutions, there was a great learning experience that how the builtin sqrt function can turn out to be faulty and how to write for such codes ) — so overall I will take this as a learning experience, and the round taught me how not to panic and focus on problem-solving rather than worrying about the rating and all and most importantly that one should never give up. So, I'm up for contests like this anytime and wish to grow.
change all sqrt to sqrtl and see what happens
Yes I did it now, But i thought My logic is incorrect during contest
Yes it is working now Thanks!
how to run the script ? And where to put the seed ?
Here is some feedback on the problem set:
sqrt(x)in C++.The statements contained quite a number of typos, but apart from that the contest was well prepared and the problems were nice. I enjoyed participating, thanks to the authors.
p.s. The trend of downvoting the contest announcements is truly frustrating. I think that many authors (for example me) are less attracted by hosting a contest because of the toxic feedback of the community. Codeforces should try to solve this issue.
And what do you suggest codeforces does?
There will always be bad feedbacks no matter how good the problems are. As an author all you can do is minimize the negative feedbacks by making creative problems.
I feel like you are an example of what your profile picture says. Or you are a troll.
Idk what brought about my profile picture, I just asked is there anything codeforces can do about it?
Feedbacks are very mixed, I ironed myself up and dug in very very deeply around the site. Read many bad things people said, and also learned how to just not give an F.
But reading your constructive feedback is very comforting to me. And I agree that the announcement downvoting trend is toxic and very unsupportive for future setters, but we also have to understand the fact that the community is exponentially expanding, and it's hard to teach everyone how to treat others. Even harder than teaching them that using sqrt might cause precision problems! xD
For the typos problem, I blame Grammarly. Ofc it helps me fixed a lot of grammar problems, but it keeps correcting "ant" to "and", makes it hard for me to edit E. xD (Jk ofc it still my bad, since it's on me to proofread everything beforehand)
Overall contest have good mixture of all concepts of competitive programming. Nice contest @low_ sir.
And what are the mixtures?
like there was questions from implementation, STL, graph, DP. One can learn new concepts from these question.
I can attribute that a lot of negative feedback (including mine) stems primarily from lower rated contestants. I, personally being a lower rated contestant can probably give an insight as to why this contest was not that appealing for people similar to or below my rating.
- Problem A was hard, and I mean really hard to be a problem A. I do agree very much with dario2994 on the opinion that it's a nice problem, but problem A-s are supposed to be pretty much solvable by everyone above a rating threshold (say 1000). This problem was clearly not one of them. Again, maybe I wouldn't have complained so much if it'd been a Div 2B (or even Div 2C), but it was just way too hard to be an A for a combined round.
- Since I didn't use
sqrtor any other such function, I did not face any problem in B. I found it a rather nice observation-based problem. But many newbies (or rather newcomers to programming in general) did get a bit stumped by the rather inconsistent behavior of C++ compliers with thesqrtfunctions, and that might've generated a lot of negative feedback from them.- Though I did bash problem C in my earlier comment, I do think in retrospect, I was being harsher than necessary. However, solving C wasn't necessarily a pleasant experience either. The problem statement was rather long, the problem statement could've been a lot simpler, and the images of the crickets were rather repulsive. (I know I'm being weird with this, but I think by simply replacing "crickets" with pawns or something similar, it'd have made a much better reading experience (is that even a thing?)). Also it was way too ad-hoc to be actually an interesting experience to solve. I know I might sound even weirder saying this, but it was an ad-hoc problem with no "ah-ha" moment in the solution, which made it, IMO, a not so nice problem.
Overall, the problemset was probably not that bad (given that I see so many higher rated users appreciating D and above problems), and I did love your attitude towards constructive criticism. Keep making problems, and I do hope and wish your next contests would be even better. :)
I thought B was pretty cool. The observation that the good numbers are exactly of the form $$$n^2$$$, $$$n(n+1)$$$ and $$$n(n+2)$$$ felt very nice.
Calculating $$$\lfloor \sqrt{x} \rfloor$$$... I didn't even think about that during the contest. The wave of "sqrt doesn't work, this is someone else's fault, please restore my ratings" feels like the same problem as people downvoting announcements.
175046236 Oct/08/2022 03:32UTC+8 ChristianoPenaldo B — Ela's Fitness and the Luxury Number GNU C++17 (64) Wrong answer on test 4 15 ms 0 KB
175046187 Oct/08/2022 03:32UTC+8 ChristianoPenaldo B — Ela's Fitness and the Luxury Number Clang++20 Diagnostics Wrong answer on test 4 155 ms 0 KB
175046156 Oct/08/2022 03:32UTC+8 ChristianoPenaldo B — Ela's Fitness and the Luxury Number GNU C++14 Wrong answer on test 4 15 ms 0 KB
175046131 Oct/08/2022 03:31UTC+8 ChristianoPenaldo B — Ela's Fitness and the Luxury Number GNU C++17 Accepted 30 ms 0 KB
175045612 Oct/08/2022 03:25UTC+8 ChristianoPenaldo B — Ela's Fitness and the Luxury Number GNU C++20 (64) Wrong answer on test 4 0 ms 0 KB
I am really lucky to choose the "correct" compiler (GNU C++17): But why? Will it be rejudged?
Btw, how to paste pictures please?
Why downvoting me? Sometimes I am so unlucky. I am just expressing a fact.
HELLO CODEFORCES AND DYTECHLAB I wanted to put forward my appeal that the jury's conduct of giving me Wrong Answer on preest 11 during System testing is wrong. I checked that it gave me wrong answer on test 4 on pretest 11 which i checked on my compiler as well as the other online compilers like codechef but it gave me correct answer there. I don't know what's the issue with the Dytechlab system testing. Please give a check on my appeal and resolve it if possible. Thanks Codeforces;
low_ and MikeMirzayanov please do look on this.
IMAGE PROOFS
MY SOLUTION CODE DURING THE CONTEST
Check this out.
Hey Can Anyone help me in these two submission I have checked for the square root https://codeforces.com/contest/1737/submission/175044526 it is giving AC in sqrtl and it is giving WA https://codeforces.com/contest/1737/submission/175047080
Fuc*ing sqrtl :(
Solved problem A in 6 minutes. it was quite easy for me.
Its my one of the best contest ever. Thanks codeforces:)
sqrtforces :D
For the 2nd question my code is
include <bits/stdc++.h>
using namespace std; #define mod 1000000007; typedef long long ll; int main(){ ll t; cin>>t; while(t--){ ll l,r; cin>>l>>r; ll k=sqrt(l); ll q=sqrt(r); ll ans=(q-k-1)*3; for(ll i=k*k;i<(pow(k+1,2));i+=k){ if(i>=l) ans++; } for(ll i=q*q;i<(pow(q+1,2));i+=q){ if(i<=r) ans++; } cout<<ans<<endl; }}Can someone pls tell how is it wrong? I checked other people solutions they used similar approach and got result as accepted. But what is wrong with this code?
try to use sqrtl instead of sqrt
I think problem E is pretty similar as this problem from 2015 ICPC Asia EC-Final. (The link of original source is down.) Though the initial weights of ants are different and you need to compute the probability of survival for each ant, the solutions are almost the same.
I didn't particularly like the round or problem B or results in it.
But what I want to say to the guys who complain about "sqrt, give me back my rating": yes, you are expected to be able to code in your language of choice. No, nobody cares that it gives correct answer in your environment.
If some people get the same score, who will win the prize?
The Problem B is very creative, which took me more time, but I feel very happy to make it.
That's why I love Codeforces.
help! Here is my code for B:
I can accept all point of sample input,but got wrong answer when submit,and the wa input is 1 1 890934354128376100,I don't know why,I got correct output when I use DEV for this input,but my codeforces output is different from DEV output,and when I change the second line "#define ll unsigned long long" to "#define ll long long",I got AC,why?,Is there some special property for codeforces between long long and unsigned long long?I spent almost the rest of the exam fixing the bug.
I think it depends on the implementation of the compiler...
Is this contest will be unrated? I agree that this contest is not easier like other Div2 contest but it's has really challenging Questions and brain boosting to solve them. Those who suffer in problem B, I have simpler solution so that there will be no precision error.
You 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.Please tell me wheather the contest is rated or not ?
List of tshirt and bag winners after running the script : https://pastebin.com/qMTBF9Ff
I set my default compiler c++ 17 now lol :>
+1
When the ratings will be updated?
It may not rated?
it should be rated
People who got wrong answer on problem B because of using sqrt(), rating should be updated assuming their submission as accepted if it is rated.
Why?
Otherwise it seems to be unfair.They deserve it as some compilers are accepting it, others are not.It was not known to people which compiler would behave in which way.
know your compilers and language
It is not always expected you know every slight differences between the compilers.
It is well known that sqrt() will not feasible to calculate square root of large numbers. So it's better to pass a long double to it or use
sqrtlfor accurate results. I did the same mistake long ago and learn this fact. The contest are not just for rating or prizes. It is a tool to learn and enhance your thinking ability.. With this question many of us will learnt how to overcome with such an issue.So don't take it in a wrong way.
So will this contest be rated?
Every Contestant Right Now :
Too hard to hack something like this B :( Is accepting copying submission during the contest has any problem?
After this round I will think twice when I use sqrt.
When will the rating be updated?
what could be the possible rating of problem c?
I'd say around 1300/1400, but I assume it's gonna be higher because of its position in the contest / low number of AC. Hardest part about it was that it was way too easy for a C.
Although I struggled a lot with D and E, I think they are both pretty nice problems. Upon seeing the scoring distribution, I predicted this round would be too hard for Div 2 because there were only 7 problems and it turned out to be true. Learning about the precision issue with built in sqrt function might feel more suitable in an educational round. Apart from those minor issues, I think this is overall a good round. Hope we can spread the positive words to encourage authors for their hardwork.
Is contest is unrated ???
Is it rated?
No,my rating updated just now.
To demonstrate how much the first problem means for a better competitive environment, I took notes of:
Where I was expected to end up if everyone participated in front of me(>=rating than me), that is I would've ended up somewhere 5500th;
Where I ended, ~3500th.
I don't care much about rating atm, but I still got -2 scoring out of the contest.
HELP！！！[user:MikeMirzayanov]
"Your solution 175015088 for the problem 1737D significantly coincides with solutions foammm/175015088, tianhangj/175021403."
I don't know this person at all, and the useful code for this problem is only four lines, so high code similarity is normal. Can the ruling be reversed?
Hello dear codeforces communnity.
Why is this round downvoted. I was at a boarding program for geriatric persons for monasticism and I could not participate. Why did this happen?
Cordially,
Francisc
https://pastebin.com/qMTBF9Ff According to this list does anyone get any notification or mail regarding prizes? Please let me know if someone get any information.
So who get the T-shirts?
https://pastebin.com/qMTBF9Ff This is the output list from the code provided in this blog. As the prize will be distributed among these ranks but I'm not sure whether is it correct or not. So just for clarification is there anyone who got some info regarding prizes. Please mention it. Thanks
how do i run the script idk how to get the testlib library working