Edvard's blog

Educational Codeforces Round #1
By Edvard, history, 9 years ago, translation, In English

Hi, Codeforces!

Educational Codeforces Round #1 will take place on 13 ноября 2015 года в 18:00 MSK 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 five 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.

Educational rounds are (and would) be prepared by me, Edvard Davtyan from Saratov SU Daemons team. Problems was invented by me and MikeMirzayanov. Thanks to my teammate danilka.pro for testing problems and MikeMirzayanov for Codeforces, Polygon and idea of the educational rounds.

I hope you will enjoy the problems. If they will be too simple for you, you are welcome to the second educational round, problems there should be harder.

Good luck and have fun!

UPD: The first phase of round is over. I remind that the results is not final and you can hack any solution during the day.

UPD2: Please use only deterministic generators. For example you should not use srand(time(NULL)) with calling rand() function in C++. Your generator should always generate the same test.

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

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

HAHA Edvard is wrote blog,but his blog till +1:)

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

Added problem F to the problemset. Now the contest will be interesting for nearly all Div 1 participants too. Let's have fun!

====

Добавил в контест задачу F — теперь даже Div 1 участникам будет интересно. Готовы?

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

After that you will have one day to hack any solution you want.

Can we also hack during the contest after locking a problem?

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

Please don't delay it today. I have a tight schedule today. Please!

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

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

How to solve E with DP?

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

There is a typo ... are (and would) be ... it should be ... are (and would be) ...

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

Damn, I wish this contest was a rated one :3

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

    It would not be like that if it was rated :)

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

Again

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

what is unexpected verdict

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

Successful hacking attempt!

Now try to hack 14233270! ch_egor got it! Try 14242942. alexey.shchepin got it. Those were interesting puzzles — would make an okay problem I guess.

I guess the real impossible one would be the first one with a bigger input. Less brute force would work probably. Any other ideas?

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

    Sorry, but I don't understand what are you doing. Can you explain it?

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

      I originally thought there would be hacking during the round, and knew I wanted to try hacking a in-contest solution afterwards. The reasonable solution would be to submit in the last second, but I had class and could only get only at small times.

      I wanted to submit something that was hackable, but no one else would really be able to hack. The way I did this was by hashing the input, and if the hash is equal to a certain predefined value, the solution fails. For example this solution fails on "thisisahacktest".

      It didn't end up mattering since there was no contest hacking, but it was fun.

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

    you hacked your own solution :p that doesnt make any sense :/

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

    Easy. I made it with binary search.

    13
1
19
31
19
19
92
74
69
32
32
91
42
73
    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      I noticed. Nice job! Just random tries until it worked? (fix all but last couple)

      Try this one: 14242942. Hopefully more constrained. :)

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

        You know, that your MOD is 1016 + 60, not 1016 + 61?

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

          Oh what. I saw before on CF that it worked to do it that way. I guess not above 1e9. Okay that's a useful find. x.x

          Anyway probably doesn't make it much easier here.

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

            It's not allowed to hack not the latest submission for the problem. Anyway, here is your hack.

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

              Nice job! That's like the same as mine.

              Maybe you just make them all the same and express the difference in base 3 I guess.

              Okay that was fun; I'm done now :P

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

does unsuccessful hack reduce point????

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

i am getting unexpected verdict over and over again

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

I wonder why it takes the first accepted submission's time as penalty when you have more than one accepted submissions :O

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



The checker is evil. Check out the smileys.

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

Why is the source limit only 256 KB? I wanted to test a case for problem D, where n=1000,m=1000, and k=1. But, when I input my 1000*1000 grid, the file becomes 956 KB. Anything I can do to fit the memory?

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

I think all that solutions for well-known problems stuff is good but the "24 hours hacking" is just a waste of time.

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

Liked this round very much.

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

E was nice w.r.t the way in which DP table had to be filled :D

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

Are we allowed to discuss the problems? I am really interested in problem C

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

    find every vectors angle with X axis and sort them and get the minimum value of distance(i , (i+1)% n)

    → Reply
»
9 years ago, # |
← Rev. 4   Vote: I like it -28 Vote: I do not like it 
int main() {
      if (I get high standing)

return

our home;

return

your home;

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

What is atan2 in c++ ?!

i used atan! it was hard because of checking some conditions! is atan2 easier?

THANKS!

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

    atan returns a result in [-pi/2,+pi/2] while atan2 gives in [-pi,+pi]. You cannot determine the exact quadrant in atan. For example; given p1(1,0), p2(-1,0), atan gives 0 for both p1 and p2. You need to do extra work to see that they are not the same vectors. But atan2 gives 0 for p1 and PI for p2 which is what we are exactly looking for.

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

Why the resubmission after hack is not tested on the hack input?! I hacked the same person using the same case twice xD

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

    I think, the system doesn't test the successful hacks because all of them will be added to the main tests and will be retested after the hacking phase. xD

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

When showing the scoreboard with Div.2 only participants, It shows only users with 1700- rating only.

Looks like it is still working with old limit for div2 before colors revolution.

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

Wow, really learnt a lot from this round, especially problems E and F. Please keep more of these rounds in future. Very nice initiative :D

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

The checker for problem F seems incorrect. It is saying this case:

17 1
0 1
0 2
8 2
8 -2
0 -2
0 -1
1 -1
2 0
3 -1
4 -1
5 0
6 0
5 1
4 0
3 0
2 1
1 0
7.12 0 1 0

is 4.00, but manually drawing it out gives me 3.12. Can you double check your solution against this case?

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

    Firstly, we cross LINE with polygon not SEGMENT.

    So answer is 4 : 8-6 inside poly, 6-5 and 4-3 along side.

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

I am Curious about to ask you Guyz that " Will All the Submissions be Rejudged after adding the Hack Cases after 24 hours Hacking Phase . Let me Know .

Thanks in Advance .

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

    Yes they will be rejudged with old tests + hacks.

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

i am got unexpected verdict when i hack problem F using n = 700, m = 100.

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

Successfully challenged myself :) :(

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

I am a Div 2 participant but why isn't my handle shown on the Div 2 Standings?

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

    Standings by divisions is not working correct. It will be fixed soon.

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

Problem C

Hard work, but finally I did it :|

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

    i have the same problem (WA on test 116 ). i didn't understand why!? can u help me :D submission id 30388279

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

Hello Edvard and MikeMirzayanov . I love the idea of educational rounds. I have a request. I am very bad at finding corner cases, and debugging. Can we have an educational round where the focus is on corner cases and debugging. If we have such a round in rated contest, I'll be scared to take part, and I don't like missing rounds. Besides, losing ratings because of one missed test case hurts real bad. If I practice such problems, then its not the same as solving in an actual contest. So, I request, that you prepare a round focussed on problems with lots of scope for Wrong Answer because of test cases. It will help me improve my debugging skills, because some times, I make silly errors, but give up on my solution thinking something's wrong with my approach, and I need to come out of that mindset. When I face this problem in practice, I procrastinate thinking I'll debug it later. As a result, if I code something in 15 minutes, I take 1.5hrs+ just to debug silly errors. I need to practice in contest environment and virtual contests are not the same. So, Please! Also, maybe 24hrs for hacks is maybe too much... but that's a secondary concern to me. :)

Thank you and have a wonderful day!

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

    I think it may be better if you can practice problems where there are a lot of hacks in virtual contests or mushups with your friends, which will make it much more interesting and motivational.Although I agree with your idea someway, frankly speaking, it’s hard for the organizers to meet the minority’s demond.

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

      But I can still see the test cases, and virtual contests are not as serious as real contests. This makes all the difference. I can sure, get all cases covered after 20 attempts and a bit of peeking at the test cases, but that is what I don't want to do, because it doesn't help at all during real contests. Besides, I am a lone coder, my friends not interested :(

      EDIT: If you don't make the whole contest case handling, then make the first three such, and the last two so hard, that I can't solve it :D . That way, I will be forced to try the first three.

      These are educational contests. Please help me learn the art of debugging :)

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

and now the time when hackers are more scary than system tests became ....

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

I was wrong(

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

I'm not sure if this has been discussed yet, but since this is an educational round, the editorial will be much more detailed while teaching us the concepts right?

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

For anyone wondering: Hacking E is pointless, testcase 4 enumerates all possible inputs.

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

Will the educational contest be rated?

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

    No. Quote of the original post:

    "The round will be unrated for all users and it will be held with extented ACM ICPC rules. "

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

Umm, both mine and Jury's answers are the same. Why does the code fail at #119?

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

any idea why so many codes including mine fails on testcase 119 for C?

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

That moment when your solution is 2ms away from time-limit :D

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

Was problem C so difficult to get right because it required to use long double? Changed mine solution from double to long double and got AC: http://codeforces.me/contest/598/submission/14258763

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

Can somebody explain what is wrong with #127 testcase ?

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

    Two angles different by 2e-17 radians which is much smaller than double precision.

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

Edvard Is there an editorial for this round ?

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

Please share editorial for problem F.

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

Hi. Where I can find the tutorial for this educational round ??

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

can any one plz tell me how to solve problem E in less than O(n * m * k * k * (n+m)) time

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

    Essentially, you can remove one k factor by observing that, when you make a cut horizontally or vertically, it is always less costly to use one of the portions in full if possible, than further cutting both portions. Hence, now instead of looping over how much of the k to distribute into the two portions, you take the best of two options.

    → Reply