Edvard's blog

Educational Codeforces Round 2
By Edvard, 9 years ago, translation, In English

Hi, Codeforces!

Educational Codeforces Round 2 will take place on November 27th, 2015, at 15:00 UTC for the first and second divisions. You can read about educational rounds here.

The round will be unrated for all users and it will be held with extented ACM ICPC rules. You will have two hours to solve six problems. After that you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

Round was prepared by me, Edvard Davtyan. Problems was invented by me and MikeMirzayanov.

I hope you will enjoy the problems.

Good luck and have fun!

UPD: Thanks a lot to PrinceOfPersia for testing the problems and Delinur for checking my bad English (in problem statements).

UPD2: The first part of competition is over. I hope that you enjoyed the problems. Now you let's hack other solutions :-)

UPD3: At the stage of hacking we found that a lot of correct solutions are numerically unstable, so they print the right answer with error in ninth digit. So we decided to increase the requirement for precision from 10 - 9 to 10 - 6. All submissions and hacks will be rejudged soon. It will not affect correct solutions. They will got Accepted as earlier.

UPD4: The editorial is ready.

UPD5: The round is over. All solutions are rejudged on full testset. The results are final.

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

Comments Comments (81)
| Write comment?
»
9 years ago, # |
← Rev. 2   Vote: I like it +16 Vote: I do not like it

hi,how can i hack solutions with generator codes? last contest i tried to hack a solution with generator code but it said invalid input. what should i do?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    Your hack is invalid -- and actually, most program outputs are "invalid" in the same way (I'll explain what I mean below). All input and output files must end in a new line character. So if you change cout << "6"; to cout << "6" << endl; in your program, then it would work properly. Technically, all of the output files you produce should also end in a newline character. The reason that you don't get WA is because the checkers ignore whitespace (and are case-insensitive). But it is good practice to include the newline at the end of your programs either way.

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    when you tryna hack but you get trolled since "#define int long long"

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it +13 Vote: I do not like it

      I once did that, got error

      return value of main must be int

      But, if you define the macro inside main, and be careful to define other functions below main, then it will be fine.

      → Reply
»
9 years ago, # |
← Rev. 14   Vote: I like it +20 Vote: I do not like it

An opportunity to compete without tension... ~-20

UPD1: (unless you get lots of down votes!) ~-30

UPD2: I wish I could delete my comment:( ~-40

UPD3: TNX the recent few ones who gave me up vote:) ~-30

UPD4: I can't believe this!!! :D ~+5

UPD5: Because of your forgiveness I give every comment an up vote;) ~+20

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

hi again!! 14453627 i tried to hack this. it got accepted but i think it should get time-limit exceeded what do you think?

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Maybe you should read comments in the announcing post about this contest? Don't you think you are the first who sent this solution?

    By the way, yes, it's correct solution because of breaks.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      (10^5)/2 555555 and then one 6 and then ((10^5)/2)-1 777777 ===> time-limit.order of time is= ((10^5)/2)*(average order for second for = (10^5)/4)=(10^10)/8 ====>time-limit.am i right?

      → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks. These rounds are great! But I can't see any editorial :(

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +47 Vote: I do not like it

Will there be a proper editorial this time?

Editorials are the most educational part of any Codeforces round, yet the first educational round had none. That made it less educational for me than regular rounds.

The concept of educational rounds is fantastic and can help us beginners a lot, but it has to be coupled with a strong, thorough, clear and educational editorial.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    Unfortunately previous time we have not decided in which format editorial should be. So there are editorial only in Russian. This time I'll write editorial myself. And I'll also translate editorial for the previous round soon.

    → Reply
»
9 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Can these problems have hints for tougher problems in the near future during the contest itself,since these are just unrated contests and meant for learning?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    add button "Get hint" (or even different levels of hints)

    if you use it, the accepted solution will get some penalty

    of course, one can use the second account just to unlock and read the hints, but cheating in an unrated round doesn't make any sense

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +75 Vote: I do not like it

      people cheat even in virtual participation.

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      No matter how hard you try admins won't accept it!

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        why not? it is easy to implement

        one also could implement the idea that the problem timer starts after you open it (like on tc), and that the hint automatically comes up after you can't solve the problem for half an hour or so :)

        and we just ignore 0.1% cheating contestants since the round is unrated anyway

        → Reply
»
9 years ago, # |
  Vote: I like it -19 Vote: I do not like it

Educational rounds are very good for IOI. I like them!

→ Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Why are these called educational rounds? For me, all rounds are educational!

→ Reply
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I'm new in Codeforces.But,**what is hacks**!?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Check out this comment by kingofnumbers.

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    during the contest only a few pretests will be run on your code... So others can give tests to try to show that your code is wrong. if they do a successful hack your submit will be unsuccessful or vice versa!

    → Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

some thing wrong with display times, I am getting 02::min::sec for registration time and 00::min::sec for before contest time please see to it

→ Reply
»
9 years ago, # |
  Vote: I like it +14 Vote: I do not like it

If regular Div 2 contests have the same difficulty as Educational Rounds, it would be fantastic.

→ Reply
»
9 years ago, # |
  Vote: I like it +6 Vote: I do not like it

I tried to hack a solution with a hack ID = 183673 the jury's solution seems to output 3141592653589793300.0000000000 but the true value is 3141592653589793238.4626433832795 the absolute error is of course much more than 1e-9?!

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Relative error is small though. The hack is successful only if both absolute AND relative error exceed 1e-9.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I didn't notice the "or" in the statements and spent the whole contest rewriting the solution in java with BigDecimals -_-

      → Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can I submit solution in next 24 hours?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    You can do it as long as you are alive BUT of course it will be UNOFFICIAL

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Ok. I was asking regarding whether the problems are locked for further submission or not. Thanks!

      → Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

What does jury solution for D output for the following test?

0 1000000000 1
0 0 1000000000

It seems to me that jury expects 0 as an answer, while it's Pi/2.

→ Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I have 2 TLE and 3 AC code on E. Why it shows verdict as TLE?

→ Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Rejudge?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    See the UPD3.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +20 Vote: I do not like it

      Не очень понятно зачем было делать перетестирование. Так как это не рейтинговый контест и тем более нужно было учитывать опыт прошлого educational где задача на геометрию не прошла с типом double и сделать выводы перед сегодняшним контестом.

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it -7 Vote: I do not like it

      If you can't write a correct solution, you can use mine :).

      → Reply
»
9 years ago, # |
  Vote: I like it +19 Vote: I do not like it

I've sent a submission for D in Java using only BigDecimal with very high precision yet it gets a wrong answer. Are you sure of the judge's answer precision?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I wrote BigDecimal solution too. On test 38 it gives 0.33492209274623239922 while my original solution gives 0.33492209274556042825 and jury solution gives 0.33492207527160644531. It is clearly jury solution that does not have enough precision.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      I don't see BigDecimal solution of you. Can you write the id of submission.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It doesn't work in all cases, so I didn't sent it. I was lazy and implemented only arctan (and only for small arguments) instead of atan2.

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
          ← Rev. 4   Vote: I like it 0 Vote: I do not like it

          Actually I see the difference only in 9th sign. Right now the precision is 10 - 6.

          → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I will try to write the full solution though. How hard could it be?

          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Done: http://mirror.codeforces.com/contest/600/submission/14530777

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              9 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Cool. I see the difference only in 9th digit so I think that the problem is okay.

              → Reply
            • »
              »
              »
              »
              »
              »
              »
              9 years ago, # ^ |
              ← Rev. 2   Vote: I like it 0 Vote: I do not like it

              One more BigDecimal solution by uwi: 14531957, but it differs from your (your solution as answer):

              Input	
-99999999 0 100000000
99999999 0 100000000
Output	
37712.36171985108000
Answer	
37712.361606713992089280270034371253587031800000000
Comment	wrong answer 1st numbers differ - expected: '37712.3616067140', found: '37712.3617198511', error = '0.0000000030'
              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                9 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Mathematica gives

                37712.3616067139920892802700343712535870319630927354351722357447180926

                using formula (14) from here.

                → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I found a bug in my previous BigDecimal solution. It didn't matter due to small angle. The new version works in all cases (hopefully). http://mirror.codeforces.com/contest/600/submission/14530815 . It was not easy to implement arctan of large argument as I thought. I wonder whether there is a better way.

        → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    You use doubles in intermediate calculation. Your solution is not precise enough because of that. My fully BigDecimal program gives 0.00188342316684821115 on test 36.

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your solution uses doubles about everywhere, so it is not "BigDecimal with very high precision".

    → Reply
»
9 years ago, # |
  Vote: I like it +41 Vote: I do not like it

I dislike the decision to lower precision requirements. It would be interesting to test different solutions on really hard tests, but now there's no such option.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    If we leave old precision all solutions will be failed. Also author solution has an error in ninth sign.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the expected solution to the F problem? I have a O(k*m) solution, where k is the maximum degree of a vertex, but this solution doesn't seem like a solution for a codeforces problem.

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    http://www.tau.ac.il/~nogaa/PDFS/lex2.pdf claims .

    The round is educational so it is not unexpected that the solution is hard.

    UPD. Never mind, O(m2) is enough to pass (unless someone provides a good testcase which looks a hard enough task by itself).

    UPD 2. ...and O(m2) can be further optimized to O(nm) but it is not needed here.

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    O(nm) solution is very simple and could be implemented in less than 100 loc. Please, read the tutorial.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      1. The tutorial is available only in Russian for this problem.

      2. By no means is this solution simple. Easy to code -- yes. Simple to come up with -- no.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        1. I'm sure Edvard is translating it.

        2. Right, I mean to understand and to code, but not to come up.

        → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Actually I think that these solution is very similar to Kuhn algorithm.

        → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +25 Vote: I do not like it

After seeing the last 2 education rounds where many people are having precision issues, I wonder what people's thoughts are about the level of precision required in some problems. It is obviously a trade off, because as a problem setter, you want the precision to be small enough that an approximation algorithm won't work, but on the other side of the coin, does it really add anything to require the precision to be exceptionally small?

As a problem setter, I can tell you that it is hard work to prove that my solution is correct when using floating point precision. I normally end up coding it in Maple with ~500 digits of precision to ensure that my C++ solutions are accurate enough. Personally (as a problem setter), I try to avoid any problem that requires the use of long doubles for the same reason I avoid the use of BigIntegers -- it isn't a level playing field of people who use different languages (and yes, I know, Java has BigDecimal, but most would easily admit that it is a pain to code using it). I'm curious to hear other people's opinion: does it really add anything to contests to ask for precisions of 10 - 9 rather than 10 - 6?

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +22 Vote: I do not like it

hack owners hacked them selves

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

so them print the right answer with error in ninth sign

Ninth digit. And "they".

→ Reply
»
9 years ago, # |
  Vote: I like it -7 Vote: I do not like it

Why not make Educational Rounds rated for Div 2?

→ Reply
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Will all the solutions be rejudged after including the Hack test cases?

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Will this contest have influence on the rating?@v@

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi,

After struggling for a couple of hours to solve problem B I found out something very interesing, the Arrays.sort method with the input from the 20-th test case take more than 2 s ( which clearly is not normal ), after switching to Collections.sort it got Accepted without any problem.

I'am very curious what is the full input for the 20-th test case ( just the first line ) because this really seems as a serious performance issues.

Thanks. Dan.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Maybe this: http://mirror.codeforces.com/blog/entry/12833 ??

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Cool, this seems like the explaination, thanks!

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Well, I believe it's an open question if one wants such tests to be in a fixed test set for the problem. It's perfectly OK for hacks. I always thought that antiqsort should not be in jury tests. But the fact that the standard implementation uses it changes something.

      I'd rather put such tests in training test sets and avoid them in official competitions (probably CF rounds either since someone anyway will hack this).

      → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My code is giving correct output for all the small test cases yet giving wrong answer on test 7 id: http://mirror.codeforces.com/contest/600/submission/14548282 can someone tell me where i am missing. I have tried to implement STL.

→ Reply