matthew99's blog

By matthew99, history, 5 weeks ago, In English,

I was the author of this round. Feel free to discuss the problems in the comments.

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

»
5 weeks ago, # |
Rev. 6   Vote: I like it +45 Vote: I do not like it

Registrants 386? Seriously 20x times lower than Codeforces? Why? Because of time of the contest the participants decrease by 20x? I think topcoder contest has great problems (some problems are even better than CF!) and very interesting contest way so 386 seems like a very low number for me.

UPD: The number of participants (who opened at least one problems) was 348 — probably the lowest number since SRM 500. Seeing these reply, we can see that many competitive programmer don't know when SRM holds and you can see that this is one of the reason of being less the number of participants. So I write the time and date of next contest. SRM 720 will be held in August 24th, 11:00 — 12:35 UTC. (14:00 — 15:35 MSK) I hope you reading this and think about your schedule.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    Maybe because there was no announcement blog on CF?

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 2   Vote: I like it -23 Vote: I do not like it

      Does it changes at all? You can see topcoder calendar. I can't believe 95% of CF participants don't see TC site or TC calendar. There must be other reasons.
      UPD: I've just noticed that there are SRM schedule in codeforces calendar.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +82 Vote: I do not like it
        You can see topcoder calendar

        Actually for me it is not so easy to find that calendar nowadays :)

        5-7 years ago they had much better design, smaller number of alternative platforms with contests available and significantly smaller number of issues with their contests.

        And nowadays it is just some strange platform where you should use either still-not-working-properly web arena or Java applet which you don't need for any other competition and which causes "It crashes, can you help me?" comments at CF from time to time... And you need to write code in a way which is different from the way you write it at any other platform, OJ archive or ICPC (back when I started doing TC I didn't even know what class and method is and it was like "copy-paste this, change this and write your code here in the way you are usually doing it in int main()"), and you should either install some plugins or work in a way that doesn't allow you to run/test your code in a fast&simple way.

        No surprise they are not so popular now — the reasons aren't such a big secret.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Well, IOI has the same format for solutions. And non AM SRMs still gather quite a few people. Not to the tune of CF round, but still

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
          Rev. 2   Vote: I like it -26 Vote: I do not like it
          And you need to write code in a way which is different from the way you write it at any other platform

          I think that's not the problem, because once SRM was very popular and also I learned this way in 20 minutes.

          And nowadays it is just some strange platform where you should use either still-not-working-properly web arena or Java applet

          I use Web Arena during contest and Java applet for practice. And I feel like it's complicated. But I think the only major problem is website — using Java applet problem can solve by upgrading Web Arena, and making website to be simple and very easy to know how it works (in part of competitive programming). Though now it's complicated, so I think it's time to write a blog in CF, "How to practice in topcoder and participate SRM".
      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        emmmmmm. Maybe it's because the topcoder arena needs to install the JAVA environment and the official website is very slow to visit, that's too much trouble,at least for me.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Another reason for the low participants could be the time. In my timezone (IST) the srms are usually held at around 6.30 am.

        A lot of coders from India, China, Japan and Russia (basically asia) probably find it difficult to compete at such time. (especially the students in college or schools i guess). CF rounds however are held usually during the evening or night in these time zones, which i understand is uncomfortable to others though :/

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
          Rev. 4   Vote: I like it -14 Vote: I do not like it

          Do you think 15-year-old student can wake up until 3:00 AM to participate in CF round every time (of course I'm participating 1/3 of contest), despite I have to leave home to go to school at 7:00 AM? Also, SRM is timezone-friendly and the time at the contest day varies much. (next SRM is friendly for asians)

          UPD: If this comment was not helpful, I'm sorry. I was just ranting that found easier version of exactly same problem I created in Atcoder, in previous CF Round (#428).

          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
              Vote: I like it +23 Vote: I do not like it

            Yes, I do. It depends only on motivation.

          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
              Vote: I like it +5 Vote: I do not like it

            I do not like participate in SRM's, not because of the time, because I found that Web-Arena is uncomfortable for me. Also I believe that it is not comfortable for the majority.

            If I liked web-arena, I would wake up whenever SRM holds, unless I have an exam next day :)

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's pretty clear (and maybe even said by TC admins) that algorithm contests don't make them any money. So they don't put much effort into it, except for high quality problems which I appreciate.

    I felt bitter for some time that they "used" Algorithm fans to build their real business of Development and just "dumped" Algorithms, except for the TCO which gives them easy publicity.

    But then I got over it. In the old days it was huge fun with a great community, I learned a lot, and because of them we now have cool sites like CF.

    So they don't owe me anything, but I just think it's sad that TC leaders/owners didn't value what they had, a fantastic algorithms contest community. But business is business, I guess.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think it's both because lot's of people didn't know about it, and because of timing.

    There were no announcement of CF, as someone already pointed out, they sent no email reminder about it, and last but not least, their calendar is pretty hidden, and unclear.

    Also in CEST (most of Europe) the contest started at 11PM, and nearly in whole Asia it was during the night, or at dawn, and lots of people won't stay up to midnight, or wake up at 5AM, to participate.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Can we lower number of SRMs in the middle of a night?

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +36 Vote: I do not like it

      Can we lower number of Codeforces rounds in the middle of a night?

»
5 weeks ago, # |
  Vote: I like it +49 Vote: I do not like it

I hope 20 minute delta between winner's easy and medium submit while getting very high score on medium is due to some legitimate reasons

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    And yanQval also obviously cheated in SRM 712...

  • »
    »
    5 weeks ago, # ^ |
    Rev. 3   Vote: I like it +45 Vote: I do not like it

    According to yanQval himself, he was installing Greed before opening medium. His solution on easy was different from medium in that easy wasn't generated by Greed, but medium was. Also, they were different in code style.

    I'm communicating with admins on this issue.

    update: he said he was using a new computer with no plugins and that he used a different template from someone else on easy, which could explain the conflict in code style.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +23 Vote: I do not like it

      If that's the reason it would be fantastic. Problem is definitely solvable in 5 minutes, though it is still had to do so

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 2   Vote: I like it +23 Vote: I do not like it

      Actually it would be also nice to hear his explanation how did he manage to code the solution for 300 in 40 seconds during SRM 712 :D As he was not disqualified it means it was a legit participation. I am looking forward to learning his secret.

      Does he have some plugin which generates algorithms for him?

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      Well he also said he was installing (or fixing?) Greed before opening 1000. Maybe Greed is not so friendly to new users :P

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Also, how to solve hard? Easy and medium were nice, right difficulty for Europe AM SRM

»
5 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

I wrote another post and was asked by the author to remove it, as he already prepared one, but was not allowed to post until the coding phase ends.

But...

It doesn't make sense. This way TC has a very low registrants number and there is no info on CF about SRM.

Either allow authors to announce their SRMs earlier or do not allow them to post about it at all. Otherwise the number of participants will be less than 100 soon.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    It seems I don't know the reason either.

    cgy4ever Can you explain this to us?

  • »
    »
    5 weeks ago, # ^ |
    Rev. 3   Vote: I like it +6 Vote: I do not like it

    I have a better way to write SRM announcement blogs in Codeforces:

    • Previous SRM writer should write Topcoder announcement blog, before 16 hours before of SRM. (so, if there is SRM 750, the blog writer is the writer of SRM 749)
    • If there's no announcement post about SRM before 10 hours, everyone can write an SRM announcement.
    UPD: Two consecutive SRM writer is very rare, so you can achieve "writer doesn't post the announcement" with high probability.
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It seems writer is not allowed to announce on Codeforces. So all announcement will be written by someone else.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I believe it should be OK to make such announcement if the post author doesn't say who the writer is. Although if a person who never made any announcements suddenly creates such post, it'll bring some suspicion.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Div.1 Medium? Nice problem.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There is some moment in time when you last time has negative score (and make it zero). Vertices visited by this time form some kind of tree (possibly empty) rooted in 0. So you just have dynamics with 2 arrays — maximal score in subtree if you entered it during that preparation stage and if you had not

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Sorry, I can't understand. Can you elaborate?

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        I guess at 5 AM this is most I can do :)

      • »
        »
        »
        »
        5 weeks ago, # ^ |
        Rev. 3   Vote: I like it +13 Vote: I do not like it

        This is a dp problem over a tree. The tree is rooted at node 0, so start the dp at the leaves and build your way up to the root.

        Keep track of two arrays A and B, and for each node i, A[i] is the maximal value you can get from any subtree of the subtree rooted at i such that the subtree also includes node i, and B[i] is the maximal value you can get from any subtree of the subtree rooted at i which does not necessarily have to include node i.

        Then we can calculate A[i] and B[i] for each node by considering

        A[i] = max(val[i] + sum(A[j]), 0) where sum is over all child nodes j of node i.

        B[i] = max(sum(B[j]), A[i])

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          I'm sorry but I don't get why this DP computes the answer we want. Can someone provide more intuition? I understand what Egor is trying to say but I don't see how this DP computes that value.

          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
            Rev. 9   Vote: I like it +5 Vote: I do not like it

            I'll try to provide some intuition for how this dp works.

            The problem can be thought of as in what way we can do two steps such that the sum at the end is maximized.

            1. walk through a bunch of nodes starting from node 0 and ignore their values entirely, because if the sum from these nodes is negative you can just zero it out. Let the nodes visited, which is a subtree of node 0, be t0.

            2. and then walk to more nodes that start at the child nodes of the leaf nodes of t0, as we can backtrack through the nodes visited at step (1) for value of 0 on the revisits, to get to all these new nodes, and consider these new node values in the sum. So we would consider the sum as the sum from a number of subtrees, where each subtree is rooted at a node whose parent is a leaf of t0.

            This is exactly what the dp memo B considers.

            The value of B depends on A. A is the value when step (1) consists of walking through no nodes initially and considers in the sum all nodes that are visited.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why can't I paste code directly into the TopCoder applet? I couldn't paste code into the applet or copy code from the applet so I had to use TopCoder Arena which is a travesty in itself...

Is this some common issue? I tried reinstalling the applet and updating Java version but nothing helped..

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There is a wonderful world of TopCoder Arena plugins

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    If you are using mac then instead command you have to use control-c, control-v for copying and pasting inside the applet. So to paste code in applet copy code using command-c from any editor then paste in applet using control-v.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks, I realized that a little later!

      Also, KawigiEdit in the link Egor mentioned creates the function definitions as well as the testing framework for you, so it seems very useful for SRMs.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Is it possible to copy paste code from Web Arena? Can you do that with opponent's code during the challenge phase?

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      No. And it is forbidden to use OCR

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Any hints for 1000-points div2?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    Xor has great properties. For each vertex, get the xor-sum of the edges on its path to the root. It's equivalent to choosing four vertices and sum up their xor-sums calculated above.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please explain a little bit more?I am unable to understand the approach!

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        You can read others' solutions

      • »
        »
        »
        »
        5 weeks ago, # ^ |
        Rev. 2   Vote: I like it +3 Vote: I do not like it

        We have to find two disjoint path in tree such that their xor is maximum.

        1. Find xor of all possible paths in tree. Complexity -> O(n^2)

        2. Then find which two paths give maximum xor. This will work because if we xor any two paths in tree, it will cancel out the common path and give resulting xor of disjoint paths only. Complexity -> O(MAX*MAX) where MAX is 1024

        Code

»
5 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

1.I was learning English vocabulary first,So I open the problem late.

2.The computer is new,So it didn't have Greed.When I want to solve problem 250,I found I can't program.I asked for a friend,and he told me how to program without Greed.And give me a template(?),because I was't able to write as TC's format.Beforce opening 500,I get to setup a Greed and use my usual template As http://codeforces.com/submissions/yanQval

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +48 Vote: I do not like it

    How about 40 seconds submit during SRM 712?

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it -48 Vote: I do not like it

      That was en error only about me

      • »
        »
        »
        »
        5 weeks ago, # ^ |
        Rev. 2   Vote: I like it +13 Vote: I do not like it

        Can you make your screencast of next SRM you participate? :)

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +30 Vote: I do not like it

        That was en error only about me

        mind elaborating what the error was?

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
          Rev. 2   Vote: I like it +17 Vote: I do not like it

          I guess that he accidentally submitted only 40 seconds after opening the task instead of waiting 5-8 minutes to make it reliable.

          Or he might have forgotten to open the task early enough and he did not have time to wait longer.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          According to himself, the network was slow at the beginning of the contest, so he got the problem from others who opened it (this happens with CF in the first minutes from time to time), coded, opened the problem and submitted without realizing instantly that it was not under CF or ACM rules.

          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
              Vote: I like it +161 Vote: I do not like it

            That means cheating I guess

            • »
              »
              »
              »
              »
              »
              »
              5 weeks ago, # ^ |
              Rev. 2   Vote: I like it +31 Vote: I do not like it

              +1. This really looks like an obvious cheating case to me.

            • »
              »
              »
              »
              »
              »
              »
              5 weeks ago, # ^ |
                Vote: I like it +2 Vote: I do not like it

              Why wasn't he banned then? Do you need some sort of confession from the cheater or other proof? Isn't it enough to determine cheating based on 40 seconds coding time?

              • »
                »
                »
                »
                »
                »
                »
                »
                5 weeks ago, # ^ |
                Rev. 2   Vote: I like it +1 Vote: I do not like it

                I already noticed (because I participated in SRM 712), and I said to admin in Topcoder slack:

                Coder yanQval solved SRM 712 Div1 250 in 39 seconds (even 2nd is 5 min). Seems like admins should check whether he/she is cheated or not.

                And admin said:
                Thanks, I will look into them

                And there are no more reply about them so I don't know whether admin looked into them, though if he/she cheated I think at least disqualified (or banned for a few months).
»
5 weeks ago, # |
  Vote: I like it -63 Vote: I do not like it

Please star my projects and contribute if you are interested. 1. https://github.com/ArmenGabrielyan16/DiceRoller 2. https://github.com/ArmenGabrielyan16/SuperLibrary

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Any hint on Div1 Medium?