Блог пользователя hmehta

Автор hmehta, история, 5 лет назад, По-английски

Hey All!

Topcoder SRM 767 is scheduled to start at 07:00 UTC -4, Sept 18, 2019.

Problem Writers: Arpa and minimario

Registration is now open for the match in the Web Arena or Applet and will close 5 minutes before the match begins.

Good luck to everyone!

Topcoder Java Applet | Next SRM 768 — Sponsored by Google — Oct 10

Some Important Links

Match Results (To access match results, rating changes, challenges, failure test cases)
Problem Archive (Top access previous problems with their categories and success rates)
Problem Writing (To access everything related to problem writing at Topcoder)
Algorithm Rankings (To access Algorithm Rankings)
Editorials (To access recent Editorials)
  • Проголосовать: нравится
  • +15
  • Проголосовать: не нравится

»
5 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Ok, so you tell me that timestamps in easy were not sorted? Suuuuper -.-

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +43 Проголосовать: не нравится

    No excuses. You're told to validate the input and it's also mentioned in one of the sample explanations.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится -14 Проголосовать: не нравится

      Who reads explanations of all samples if your code passes them? It seems I was not the only one to miss this since like half of participants was hacked on this problem and this is just plain stupid.

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I don't think many people were hacked on this. It's much easier to miss that last <= a, last1 = last2 if a1 = a2 and last1 <= last2 if a1 <= a2 aren't sufficient conditions — for example, I missed it at first and I imagine it constitutes a large number of hacks. Then come the conditions mentioned in samples and various silly bugs.

»
5 лет назад, # |
  Проголосовать: нравится +78 Проголосовать: не нравится

And, wtf was that med?

»
5 лет назад, # |
  Проголосовать: нравится +74 Проголосовать: не нравится

Sorry to be a hater, but I think this is one of the worst topcoder SRMs ever in terms of problem quality

»
5 лет назад, # |
  Проголосовать: нравится +53 Проголосовать: не нравится

The shit was this?

To clarify: Dijkstra isn't a medium problem in ${CURRENT YEAR}. Hard wasn't all that bad (it required actually thinking, wow) but annoying to code. 250 is just difficult to understand, apparently for the author too. My result before resubmitting medium (350 -> 130 points just because I used long long once but forgot when rewriting stuff) is worse than my result after challenge phase and that's worse than after systests even though I maybe-failed 250.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    Hard wasn't all that bad (it required actually thinking, wow) but annoying to code

    Emmm, and what is annoying to code here? I was amazed by how this problem was short and easy to code, I think it was one the most coding-friendly hard problems.

    (lacks obvious fenwick tree and dfs determining just preorders)

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится -10 Проголосовать: не нравится

      My version is shorter :)

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится -13 Проголосовать: не нравится

      Yes yes, if you cut off stuff and codegolf other stuff, it's very short. I was talking more about the parts that aren't the main point of the problem — generator, stuff I've written a million times before... it doesn't have to be long, but it's annoying standard stuff.

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

Oh, and most stupid bruteforces you can imagine passed to hard as well :). Cause it is kinda impossible to hack it, especially since you made it so that f[i] = w[i+1] :).

EDIT: Whoops, I have not read that solution I was talking about carefully. It is brute+opt that Jatana mentioned

»
5 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Dijkstra isn't a div1 medium problem. Div1 450 has a linear-time solution and the intention of the author was to let only O(n) solutions pass. Apparently, a few of the O(n log n) solutions managed to fit into the time limit anyway. This was not intended.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +46 Проголосовать: не нравится

    Surprise surprise

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    I figured it has a nicer solution, but decided to write Dijkstra because there's no way that can't be squeezed in. The first attempt, with vector< vector<int> >(N), got predictable MLE. I removed that, computed next vertices directly and oh look, I can't make it fail. So I submitted. (Then I resubmitted at the end because I didn't pay attention to long long the second time around...) Seems good enough, just with basic bitch priority_queue of pairs, an array of distances and no other structures.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Ah, okay I just overlooked the extra 0 in the constraint to n, :(

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

My div2 1000, failed with Dijsktra, why ?

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +26 Проголосовать: не нравится

Got AC on 1000 with the following algorithm:

Perform just what said in the statement.

Optimization: if we are staying in the vertex v and the current amount of fuel is f and for some previous query we had less fuel and we were able to reach the root then break.

»
5 лет назад, # |
  Проголосовать: нравится +43 Проголосовать: не нравится

Anyone else have issues with hacking? Is this just an issue with the web arena?

Why is there both lowercase and uppercase n's in the pseudocode? (And why no sample explanations? At least provide the answers for each query :|)

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    Noboby could challenge in last few minutes in arena

    • »
      »
      »
      5 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Oh, but in my case someone hacked (er I mean challenged) the solution I was looking at a minute later. :P

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I successfully challenged some 2 minutes before the end and got the OK reply immediately. Seems like it was a problem just for some people.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I tried to hack in last minute and lost 25 points.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    I used the old arena and got request timeout every single time I tried to hack a brute force on 1000 (tried at least 5 times before I gave up).

»
5 лет назад, # |
  Проголосовать: нравится +64 Проголосовать: не нравится

After discussing the issues with the round we decided that Division 1 will not be rated. We deeply apologize for the issues.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +28 Проголосовать: не нравится

    So what's the issue? The jury doesn't have a correct solution for 250? So what's wrong in the original jury solution?

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Seems that the 250 pts problem has been rejudged and not everybody failed. Could you please announce something more accurate about why unrated for div. 1?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Is div2 rating updated? Because my rating not updated yet.

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +65 Проголосовать: не нравится

Btw, I may rant at topcoder and its tasks for many reasons, but actually I would be very happy to see its improvement in the problem quality (both in the interestingness and in the quality of preparation), so I would suggest the following.

If an input to the problem is given as a generator, provide this generator in the copy-pasteable format. It is a pain to always spend a minute adding semicolons, changing "modulo" to "%", adding parentheses and modifying loops. And then spend a minute thinking whether there is no overflow which may be tricky even for those who have define int long long in their codes since these computations are performed on function arguments which could be just ints.

95% of contestants use C++, but it shouldn't be much of an issue adding them in all available languages, right? That would be very helpful, especially if you are going to make bugs/typos (N instead of n) in your generators and if your generators could give segfaults (par[1]=0, w[1]=B, whereas n=1 is possible).

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    With the limited number of languages, I don't understand why they don't allow the problem setters to write a driver function. It can read the parameters, generate the input then call the class method.

»
5 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Hi all.

I'm sorry for the problems occurred in the contest. Even now, I don't know what happened in 250 (Div. 1).

Here is the editorial. I'm currently improving it. You can put comments, I'll answer.

I promise I'll hold another round and remove this bad memory.

»
5 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

All these Red handles together, who is manning NASA headquarters

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Codeforces < Topcoder