hmehta's blog

Topcoder SRM 749 and Editorials
By hmehta, history, 5 years ago, In English

Topcoder SRM 749 is scheduled to start at 07:00 UTC -5, Feb 2, 2018. Registration is now open for the SRM in the Web Arena or Applet and will close 5 minutes before the match begins

Editorials: https://www.topcoder.com/blog/single-round-match-749-editorials/

This is the first SRM of Stage 3 of TCO19 Algorithm. This stage will also help you qualify and win reimbursements/tickets to TCO19 Regional Events

Congratulations to Petr for qualifying for TCO19 Finals from Stage 2.

Stage 2 TCO19 Points Leaderboard | Topcoder Java Applet | Next SRM 749 — Feb 2

Hope to see most of you competing! All the best!

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

Comments Comments (37)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Match begins in less than an hour! Hope to see most of you compete :)

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

    Small feedback, on the Div2A, "duration" parameter is "long long" so I started thinking about fast exponentiation, only to see later that duration <= 100,000 in the constraints. Of course I should have read the constraints first, but it would have been nice to define this parameter as "int". Just a suggestion; thanks for the contest!

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

I never participated in Topcoder SRM before since I had some problems handling the arena applet. Now I have got everything done but always miss the contest since I don't always login to the arena. Is there a way that I can have the notification before a contest, i.e, sent to my email? Thanks in advance for any advice.

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

    We are working on that, The new way would be — You can register for an SRM anytime 24 hours before the round and then we will send you a reminder 20 mins before the round :)

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

what a nice problem div2C is!

how to solve it?

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

    A short outline:

    Handle X=0 first, then A[i]=0, then solve the "everything is non-zero" case in the way explained below.

    Define P[k] to be the product of the first k elements of A. Then, the product of A[i:j] equals X if and only if P[i] * X = P[j]. Now, even without needing to compute inverse elements, you can look at each i and count the matching js. (What's the right order of looking at the is and what data structure do you need to get the number of matching js quickly?)

    → Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it -22 Vote: I do not like it

who was the setter of the contest ! don't know how to set problems ! **** such huge level of difficulty even in problem1 . see the division1 +2 summary ! **** worst constest !

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

    I understand your concerns, however we had last 2 rounds where we tried to achieve a success rate of more than 70% in Level 1 problems for both divisions. But sometimes we also need to have challenging rounds for the reds.

    We had such a round after 5-6 rounds. We are keeping a close eye on the difficulty and will make sure we have an appropriate balance between the same. :)

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

      but see the level of div1a , many red + yellow scored 0 . such a huge imbalance not even seen on codeforces .

      even in division 2 round sudden increase in difficulty pf problem b ! is it topcoder open finals or what ! such a huge difficulty and just 1 hour . is it good ? at least increase the time if contest is difficult .

      even in topcoder open finals petrr was able to solve all three , but here just 1 .

      the legend with 1 submission . huh !!

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

        Totally understand your point. In Topcoder Open the problem coordinators work very hard to make sure problems are appropriate for the contestants and the time of the contest.

        Here in the regular rounds sometimes the calculation can go a little here and there.

        Also, the focus is to provide fun, challenging and learning problems.

        We will be publishing the editorials within a day. Hope you were able to learn something out of the contest this time.

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

      Rule 14: Don't respond to trolls, it means they win.

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

        Hey , Xellos dont do too much . i am asking a genuine question , he has to reply as he is the admin of topcoder .

        don't spit ur venom here !

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

          Look man, if anyone's "spitting venom" on this comment thread, it's certainly not Xellos.

          "i am asking a genuine question , he has to reply as he is the admin of topcoder"

          I'm actually not even sure you asked any question, apart from "who was the setter of the contest" after which you berated them for making the "worst contest ever", or "is it good", which seemed to be more or less rhetorical. Neither would strike me as "genuine".

          Also, he certainly does not have to reply; he is doing so because he is professional and evidently has a much kinder soul and more patience than the rest of us.

          I actually would be inclined to agree with Xellos and think you're a troll if it weren't for the fact that you've messaged me before and we've had a legitimate conversation. I think you just act a little bit like you're owed something here. Nobody who makes these websites has to do it, and you (like the rest of us) should be thankful that they do, because it provides people like us with something fun to do. Have you tried creating problems before? It's fucking hard, especially if you're trying to target an exact difficulty range. Like, seriously, just think about it for a second and think about what you would try to do if you were going to make a Div2 250, 500, or 1000 question. Of course there's going to be variation and sometimes a question might be too hard or too easy. It happens, chill out.

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

The skill gradually increases the amount of damage he deals when attacking the monster multiple times. More precisely, each attack after the first one will deal M more points of damage than the previous one, where M = (level percent of attack). __

Here the last "attack" refers to the initial variable and not to the value of the previous attack? I.e, the growth is linear, not exponential?

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

    linear

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

      Right. I think this could have been phrased better. Sample results agree with both interpretations.

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

Web Arena ignored all my tries to perform a challenge (on button "Challenge") and worked only with test cases from examples (after clicking on "Run" button). Also problem statements were loading quite long after Challenge phase start.
@hmehta Please, take a look on this.

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

    Very sorry for the issues you faced.We suggest you to please use the applet. We are not working on the web arena issues anymore while we are building the new arena.

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

      Really, a third arena is in the works?!

      Is there a place to read more about that?

      By the way, what's the recommended way of using the Java Arena with Java 9+, when there's no Java Web Start available? I ended up just reading the .jnlp file and replicating the contents by hand. In more detail, it meant downloading the jar from https://www.topcoder.com/contest/classes/7.2/arena-client-combined.jar, and then running it like this: java -cp arena-client-combined.jar com.topcoder.client.contestApplet.runner.generic www.topcoder.com 5001 http://tunnel1.topcoder.com/tunnel?dummy TopCoder. But the arena has some visual artifacts with Java 11. So, is there a cleaner way?

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

        I use Java 8 update 121 and update check is disabled.
        Don't have any problems with applications, who requires Java.
        What I'm doing wrong?

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

          Java 8 is fine, yeah. My question is about Java 9+. Once you have a newer Java, it is not always convenient, or possible at all, to downgrade.

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

            Yes, a new arena with an updated backend is in progress.

            The new backend is being used for the marathons currently.

            Java 9 issue: Working on that, will post here and also update on the website when we have a quick solution :)

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

Is Div1 med solvable without matching ??

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

    Of course! Since n ≤ 9. It leads to a dp bit mask.

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

      then why u didn't solve , ended with 0 being one of the best in the world

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

        No! -25 point :D

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

          lol ! so hard problem set , i hates . at least one should be solvable . div 2 were also hard .

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

            If n was large as m, I might solve it easily by matching. Setting n ≤ 9 let me thought about bullshit dp bitmask.

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

    I think finding the matching can be done with a greedy algorithm, such as looping through cells in target by X and then Y coordinate, and each time pairing with the available stacell with highest Y coordinate.

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

    A greedy scheme also works in this problem. Let us call points which need to go from Black to White type 1 and those which need to go from White to Black type 2.

    Iterate over the grid row first from top left to bottom right. At any point if you see a type 2 cell, then you need to find a type 1 cell to the above and/or left of it, which has not yet been used. Among these you can greedily pick any of the rightmost ones. Now you can move the black color of that cell to the current cell in at most 2 moves.

    The reason this greedy works is because every type 2 cell needs to be paired with a type 1 cell, and once you're at (r, c) all unused cells in the same column above it are equivalent in which future type 2 cells they can be paired with.

    At the end you're left with a bunch of unused type 1 cells, if there are an even number you can arbitrarily pair them and destroy them in at most 2 moves.

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

Why are the examples so weak?!!!

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

Thanks for the round!

My screencast with mumbling: https://youtu.be/hqCECmi_AJc

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

WTF! I get WA for 250 because thought level instead of attack * level / 100.

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

    Lol. I thought the same.i thought my solution has some overflow issues. Really poor. I think samples should at least clarify these.

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

The hard problem has a really nice solution. First note that we never need to cross an edge between two adjacent cells more than two times. Now there are only six different options for how we walk the stairs between two adjacent floors, as illustrated in the first picture below. For how we walk on a certain floor, we have essentially the same options, as illustrated in the second picture below.

Stairs options:

stairs options

Floor options:

floor options

We can use these observations to solve the problem with dynamic programming, iterating over the floors from top to bottom. First we have to determine which transitions (combinations of stairs option for floor x-1 and x, stairs option for floor x and x+1, and floor option for floor x) are possible, which is a bit of casework (see my solution for details). Then we determine for each floor option its cost. And then what remains is a pretty simple dp.

The final solution is linear and it would work for much bigger limits then those that were given in the actual problem. And the complete code is quite short.

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

Can anyone please explain solution using matching for the Div1 Medium?

→ Reply