Gerald's blog

Codeforces Round #103 (Div. 2)
By Gerald, 13 years ago, translation, In English

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: NALP, Polichka and Gerald. Traditionally, we express our gratitude for their help to Artem Rakhov (RAD),  Maria Belova(Delinur) and Mike Mirzayanov (MikeMirzayanov).

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

Good luck and have fun of solving problems! :)

UPD: Problem analysis

  • Vote: I like it
  • +145
  • Vote: I do not like it

Comments Comments (38)
| Write comment?
»
13 years ago, # |
  Vote: I like it -25 Vote: I do not like it
"last Div2 only round"?
→ Reply
»
13 years ago, # |
  Vote: I like it +4 Vote: I do not like it
another 5 minutes~?time to prepare~
→ Reply
»
13 years ago, # |
  Vote: I like it -10 Vote: I do not like it
Good Luck Everyone!!
hApPy CoDiNg !!
→ Reply
»
13 years ago, # |
  Vote: I like it -14 Vote: I do not like it
Oo boy! I am so going down big time.
→ Reply
»
13 years ago, # |
  Vote: I like it -9 Vote: I do not like it

can anyone tell me where can i get the pretests input.?

i don't knw why my output is wrong.

→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it
    You should wait until the system testing phase is over
    → Reply
»
13 years ago, # |
  Vote: I like it -26 Vote: I do not like it
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.
→ Reply
  • »
    »
    13 years ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    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 :)

    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it -28 Vote: I do not like it
      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.
      → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it +24 Vote: I do not like it
      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.
      → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it -21 Vote: I do not like it
    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
    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it
      But he have to be on the same room. It's a little hazardous...
      → Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
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.
→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it
    Useful hint:
    For comparing distances you dont need to get square root, you can compare squares => no doubles + no sqrt.
    → Reply
»
13 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

bad luck!

when I want to submit D in last 1 minute my D'link modem freezed and after contest I got first accept.
:(
→ Reply
»
13 years ago, # |
  Vote: I like it +3 Vote: I do not like it
Any hints about D and E?
→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Solve D using Dijkstra
    → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    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 and end.key+edge weight>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
    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      actually your logic is slightly wrong , it should be-

      st.key + edge weight > l && end.key + distance to Point from end > L

      where, distance to Point from end = edge weight — (L — st.key)

      → Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
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 
→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it
    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|).
    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Oh yeah, You're right. Thanks a lot Dima!
      → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    O(27*l) where l->length of string.
    Will pass in 2s.
    → Reply
»
13 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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://mirror.codeforces.com/contest/144/submission/1077198

Thanks

→ Reply
»
13 years ago, # |
  Vote: I like it -11 Vote: I do not like it
Did anyone misinterpreted problem statement C like me? Take look at here.
→ Reply
»
13 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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? 

→ Reply
»
13 years ago, # |
  Vote: I like it +15 Vote: I do not like it
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://mirror.codeforces.com/contest/144/submission/1077165) and pretty much the same logic written in C++ got accepted later (http://mirror.codeforces.com/contest/144/submission/1082838).
→ Reply
  • »
    »
    13 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    Agree.

    Here is my situation.

    It would be nice to have time limits like here were done by codechefers.
    → Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

→ Reply