### Gerald's blog

By Gerald, 10 years ago, translation,

Good day, friends!

Today another Codeforces round for Div2 participants will be. As the last Div2 only round, this round has been prepared by a team of three people: NALPPolichka and Gerald. Traditionally, we express our gratitude for their help to Artem Rakhov (RAD) Maria Belova(Delinurand Mike Mirzayanov (MikeMirzayanov).

Score distribution: 500-1000-1500-2000-2500

Good luck and have fun of solving problems! :)

UPD: Problem analysis

• +145

 » 10 years ago, # |   -25 "last Div2 only round"?
•  » » 10 years ago, # ^ |   +12 he meant "previous".
 » 10 years ago, # |   -6 I wish have a good contest.
 » 10 years ago, # |   +4 another 5 minutes~?time to prepare~
 » 10 years ago, # |   -10 Good Luck Everyone!!hApPy CoDiNg !!
 » 10 years ago, # |   -14 Oo boy! I am so going down big time.
 » 10 years ago, # |   -9 can anyone tell me where can i get the pretests input.?i don't knw why my output is wrong.
•  » » 10 years ago, # ^ |   +2 You should wait until the system testing phase is over
 » 10 years ago, # |   -26 Why is running the code on pretests important? The code should be ran only on the given sample inputs, for the following reasons :1. I don't know what are the pretests, so that puts me at a disadvantage when hacking. People often use kludges to get their code working, which is usually not visible. 2. The number of solutions that can be hacked are reduced considerably. I would like to know the possible reasons for including pretests that are not known to the contestants.
•  » » 10 years ago, # ^ | ← Rev. 2 →   +10 If there's no pretest, one could easily create tons of account --> there would be a few of his accounts in his room. For the fake accounts just give only outputs for example tests, submit, and use the main account to hack his own fake accounts. After hacking himself, he repeats again and again, thus gaining thousands of points :)
•  » » » 10 years ago, # ^ |   -28 Oh yes! I forgot the disadvantages of the system. But, it was hurtful to see that many people in my room had 2-3 WA's before submitting problem A.
•  » » » 10 years ago, # ^ |   +24 I think the main reason is: If there was no pretest, one could easily create a dummy account, submit an obvious wrong answer, locked it, read stronger coder's code to know the correct algorithm, code it, and get much more points.
•  » » 10 years ago, # ^ |   -21 my guess is that people could abuse this by having a dummy account and submitted a totally incorrect solution, and then hacking that dummy account with their 'actual' account. easy hacking points. having some pre-tests prevents this
•  » » » 10 years ago, # ^ |   +10 But he have to be on the same room. It's a little hazardous...
 » 10 years ago, # |   0 I just learned that the C hypot function is too slow.I got TLE while using it but it passed when I wrote my own hypot.
•  » » 10 years ago, # ^ |   +6 Useful hint:For comparing distances you dont need to get square root, you can compare squares => no doubles + no sqrt.
•  » » » 10 years ago, # ^ |   0 Thanks
 » 10 years ago, # | ← Rev. 2 →   +2 bad luck!when I want to submit D in last 1 minute my D'link modem freezed and after contest I got first accept.:(
 » 10 years ago, # |   +3 Any hints about D and E?
•  » » 10 years ago, # ^ |   0 Solve D using Dijkstra
•  » » 10 years ago, # ^ |   +3 Although I have not submited it because could not implement Dijkstra and so am not sure about it  but my logic for D is:Apply Dijkstra to get the "key" (shortest distance) to each vertex.If key ==L then c++;. Then examine each edge.if starting vertex of this edge key is less than "L" and st.key+edge weight >L then there exist a point in this edge with distance exactly L,so c++.Similarly if end.key L then another point provided st.key!=end.key because then you would be adding the same point on the edge twice.Simply run this for all edges .Can anyone provide me link where I can get java implementations of all important and useful algorithms .It will be very useful during contests
•  » » » 5 years ago, # ^ |   0 actually your logic is slightly wrong , it should be- st.key + edge weight > l && end.key + distance to Point from end > Lwhere, distance to Point from end = edge weight — (L — st.key)
 » 10 years ago, # |   0 Hi there,I wanted to solve problem C with the idea most contestants did. To have an array of size 26 for S & P and then processing it. My big mistake was that I taught it would get TLE. Can someone explain me the time of this idea???Tnx
•  » » 10 years ago, # ^ |   +4 The time is O(|S| * Aplhabet). Because you take |T| - |S| strings and check them with time O(Alphabet).So time is O((|T| - |S|) * Aplhabet) = O(|S| * Alphabet).You can get TL if you work with strings and get new string using substr, delete or something other, that works O(|S|).
•  » » » 10 years ago, # ^ |   0 Oh yeah, You're right. Thanks a lot Dima!
•  » » 10 years ago, # ^ |   +1 O(27*l) where l->length of string.Will pass in 2s.
 » 10 years ago, # | ← Rev. 2 →   0 The bruteforce solution of problem B is 8,000,000 as I think.However, I've failed in test #27 (TLE).Can any body check it for me please? It's so simple and straightforward.http://codeforces.com/contest/144/submission/1077198Thanks
•  » » 10 years ago, # ^ |   +1
•  » » » 10 years ago, # ^ |   -8 дык не про то спрашивают
•  » » » » 10 years ago, # ^ |   -7 Как раз про то
•  » » » » 10 years ago, # ^ |   0
•  » » 10 years ago, # ^ |   +1 You should compare square of the distanse with square of the radius (which could be precomputed exactly after input). "hypot" function does slow sqrt operation.
•  » » 10 years ago, # ^ |   -6 Well, I've tested your code. I fount that hypot is very slow. use condiction: sqr(dx) + sqr(dy) <= sqr(r), would be much faster. Solved in 50ms.
•  » » 10 years ago, # ^ |   0 Thanks guys very much. I'm so grateful.hypot() is slow. That's a useful information.
 » 10 years ago, # |   -11 Did anyone misinterpreted problem statement C like me? Take look at here.
 » 10 years ago, # |   +8 Cool contest!And I realized that I should learn how to read, because I was trying to solve different problems! :(I am still wondering, what is the best way to solve slightly modified version of task B: let's assume that generals are sitting not only on the border, but also inside rect?
 » 10 years ago, # |   +15 I don't think that time-limits for solutions for problem B written in Python were fair. I got TLE for my submission in Python during contest (http://codeforces.com/contest/144/submission/1077165) and pretty much the same logic written in C++ got accepted later (http://codeforces.com/contest/144/submission/1082838).
•  » » 10 years ago, # ^ | ← Rev. 2 →   +5 Agree.Here is my situation.It would be nice to have time limits like here were done by codechefers.
 » 9 years ago, # |   0 can anyone pls provide acorner test case for problem A of Codeforces Round #103 (Div. 2);getting wa;m just a noob started practising on codeforces thnks in advance
 » 4 years ago, # | ← Rev. 3 →   0 What is the correct output for 4 5 1 1 3 1 2 3 16 1 2 1 4 2 1 1 4 1 4 I think it should be 3 but AC codes gave 2.Am I wrong?UPD : Got it misunderstood the question.