Petr's blog

An inverse topological week
By Petr, history, 9 years ago, In English

http://petr-mitrichev.blogspot.com/2015/10/an-inverse-topological-week.html

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

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

For problem K of NEERC Moscow Subregional, what is the "standard, involving advanced data structures and quite tedious to implement" solution? I solved it with the "simple" solution but I have no idea how to approach the problem differently.

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

    I was going to comment the same, but then I saw this!

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

    I've kind of assumed that the approach of "Look at vertex 1, then recursively handle vertices not reachable from 1, then put 1, then recursively handle vertices reachable from 1" can be somehow sped up from O(N^2) using data structures, but now I don't see a good way :)

    GlebsHP, any comments?

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

Yours blogs are great and you always have one upvote from me :)

One little suggestion from me, you don't have to agree :) I see in your blogs analysis for Topcoder, Codeforces and some Russian contests. That is ok, you are doing that contests and have really good results. But I didn't see that you mentioned some great tasks from other platforms. I think that will be more useful for many coders. First that tasks saw smaller amount of competitiors than your blogs, second CF and TC have big community, so many other users can help you in solving. You don't have to write results, analysis or something like it, but you can write your idea or even text for 1-2 harder tasks from that platforms.

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

    May be he does not have enough time for that. Those task which we think are good may be tedious, boring or not interesting for them. Petr level programmers like the task which has simple and intuitive solution. What I have read from Petr blog is that he is fan of simple problem statement(we are too but in different sense because I lost in the middle in long problem statement).

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

      I think that nobody likes long statements and reason is same — you are spending a lot of time for nothing...

      This was my suggestion, so if he has free time, he can share with us some new and unknown task from many contests. Anyway I will continue with reading this blogs :)

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

        Many of the task, he does not remember much. Recently a similar task Petr has solved in previous SRM could not solved in this. I don't know much of problem similarity but it happens. Some of programming sites like Hackerank came with same type of problems (Eg- Codesprint) yes they are improving but they are not in the level of Codeforces or Topcoder as for now. Prizes are added incentives but I don't think Petr will participate for the sake of prizes.

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

          When I said unknown I didn't thing about old used tasks. I thought that 60% of coders see that task on official round and maybe that isn't interesting for them.

          It isn't place where we should discuss about quailty of competitions on other platforms. I shared my opinon on other blogs about it and that is enough. I didn't talk about working contests, everybody can see tasks after contest and share opinion about the most interesting problems.

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

        I do like long statements if they are interesting enough and are in some OJ archive :)

        Example: GOV chronicles

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

    When I talk about tasks in my blog, I usually only mention tasks that I've tried to solve myself, as otherwise I can't really write anything useful or even estimate the beauty of the task.

    So in order for me to mention tasks from other platforms, I have to solve them myself, and so far I haven't found other platforms compelling enough.

    Did you have some specific other platform in mind?

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

      I'll tell you what I am doing and what is interesting for me. I don't have intention to promote any platform and tell you what is good to solve.

      I think that rated contests on many sites are nice. Sometimes they had bad and not very creative tasks, but lot of problems were cool. I found good tasks on:

      -CodeChef (Monthly Contest, Cook-off, Lunchtime)

      -HackerRank(101 Hack, Week of code)

      -HackerEarth (Clash)

      -Coci

      Normally nobody expects that you are solving all these contests, but you can read task and solve something when you have free time ;)

      My favourite contest are 101 Hack and Coci.

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

        Thanks for sharing! Unfortunately I don't have that much in terms of free time, so solving problems out of competition isn't something that I usually do :(

        My impressions about the platforms you mention:

        CodeChef — yes, there are sometimes nice problems, and I've actually participated there several times, but some bad problems and some system issues made me enjoy those contests less, so I stopped.

        HackerRank — since nothing seems to be available publicly without registering, it's hard for me to see if the problems are nice or not. I think if they make the problem statements, contest standings and contestants' solutions available without registering, the website would be much more compelling :)

        HackerEarth — I haven't actually paid attention to it before, so thanks a lot for mentioning! Similar to HackerRank, not much seems to be available without registering, so it's hard for me to see if it's worth it to participate.

        Coci — This one looks very compelling indeed, I should try it at some point. My only reservation is that the contest duration is 5 hours. Is it for teams or for individuals?

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

          COCI has 3-hour contests (last time was 4 hours because of technical fails). Where did you get the 5 hours from? And it's for individuals, of course.

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

            Good point, I've misread the main page. I should definitely participate!

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

I particularly liked problem G and H. G was a geometry and typical geometry on ACM is like "think for 1 minute and code for >=1 hour" and here I needed a bit longer thought, however code turned out to be very easy :). When looking at codes of other people I smiled every time when I saw some segment/Fenwick tree when it was sufficient to take just one global max and one global min (having fixed case before) ^.^

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

I just saw the simple solution to K...

Wow, that has to be the coolest solution I have seen in a while. :)

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

    where did you find the simple solution to K?

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

      It passed by me while I was in a pizza place having dinner. I should have said hi...

      I don't want to spoil it, it's easier to appreciate it if you have to think for a while.

      → Reply