hmehta's blog

Topcoder SRM 767
By hmehta, history, 5 years ago, In English

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)
  • Vote: I like it
  • +15
  • Vote: I do not like it

Comments Comments (45)
| Write comment?
»
5 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

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

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

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

      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.

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

        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.

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

And, wtf was that med?

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

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

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

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.

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

    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)

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

      My version is shorter :)

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

      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.

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

        Is every problem where you need to code even the simplest possible segtree or simplest possible dfs annoying for you? I don't get you

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

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

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

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.

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

    Surprise surprise

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

    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.

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

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

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

My div2 1000, failed with Dijsktra, why ?

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

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.

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

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 :|)

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

    Noboby could challenge in last few minutes in arena

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

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

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

      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.

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

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

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

    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).

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

      Same. BTW what's the 'old' arena? Is there a new one?

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

        The Java applet one. The web arena is more recent.

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

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

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

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

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

      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?

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

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

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

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).

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

    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.

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

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.

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

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

    Could you please not?

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

      That's rude

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

        No, it's not, he said "please".

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

        I'm ready to pay this price if it means cancelling another bad contest

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

    You can hold it on Codechef — then if something fails, nobody will really care.

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

      Let's reduce the space of people who will care. Why Codechef. Use hackerearth. Call for problem setting on HackerEarth
      No of fks anyone gives to hackerearth = $$$-1$$$

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

All these Red handles together, who is manning NASA headquarters

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

Codeforces < Topcoder

→ Reply