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

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

Hey All!

Topcoder SRM 782 is scheduled to start at 12:00 UTC -4, Mar 28, 2020. Registration is now open in the Web Arena or Applet and will close 5 minutes before the match begins.

Thanks to jy_25 and misof for writing the problem set and coordinating the round. Also thanks to Chandnani and a.poorakhavan for testing and writing the editorials respectively.

This is the last SRM of Stage 2 of TCO20 Algorithm Tournament and TCO20 Regional Events Qualification

Stage 2 TCO20 Points Leaderboard | Topcoder Java Applet | Upcoming SRMs and MMs

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)

Good luck to everyone!

  • Проголосовать: нравится
  • +33
  • Проголосовать: не нравится

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

Reminder: Match begins in 5 hours!

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

Can anyone tell how to solve Div 1 500 pt problem?

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

500 should've been 250, definitely too easy.

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

How to solve 250? Now I know we use bitmasks, but don't understand transitions fully.

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

    First, you can throw away any penalty token with value > $$$2*D$$$. This leaves at most 12 penalty tokens. Use a mask over those tokens.

    Let $$$dp(mask)$$$ be the required expected value if we only had tokens which are activated in the mask. For each possible value of the roll i.e. for every value $$$v$$$ in the range $$$[2,2*D]$$$, try all possible ways of getting sum equal to $$$v$$$ (You can precalc those, each way is a mask of tokens). A way that uses tokens of the mask $$$x$$$ is valid if $$$x&mask = x$$$. Over all valid ways, find the one that has the minimum value of $$$dp(mask - x)$$$. add to $$$dp[mask]$$$ that minimum multiplied by the probability of rolling $$$v$$$.

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

    Problem K. There is editorial online.

    We don't care about numbers > 12 anyway. Let mask represent the numbers we haven't eliminated yet. For each state, we just try out every possible rolls, and try every possible ways to make a move with this roll.

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

    let dp[mask]=the answer we get considering only the tokens corresponding to this mask.

    For calculating dp[mask], we iterate through all the sum s[2,2d] and go to all the submask possible after removing sum s from this mask. We take the dp[submask] which gives the minimum answer for this sum s. If for a sum s, we can't make a transition to any other submask, then we consider the current sum remaining in this mask. So we get for each sum s, the minimum possible answer we can form.

    After this we can calculate the answer for dp[mask] by taking expected value of sum s for all s from [2,2d].

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

How to solve div1 1000?

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

    Div1 1000 is a very interesting problem :)

    First, since we need to flip every vertex at least once, the closed walk should be spanned all $$$N$$$ vertices. Second, suppose there is an edge between $$$v_1$$$ and $$$v_2$$$, and we go from $$$v_1 \rightarrow v_2$$$, going by $$$v_1 \rightarrow v_2 \rightarrow v_1 \rightarrow v_2$$$ makes "extra flip" of color of vertex $$$v_1$$$ and $$$v_2$$$. We define such move "anti-shortcut of $$$v_1 \rightarrow v_2$$$".

    Now, let's suppose that the given graph is a tree. There is a unique closed walk of length $$$2N-2$$$, which passes each edge twice. When we walk in the determined closed walk, the color of vertex $$$i$$$ will be black if $$$deg(i)$$$ is even, otherwise it will be white.

    Since the sum of degree of each vertices is even, if the graph size $$$N$$$ is even, there will be even number of vertices which will be white. Now let's choose two white vertices $$$w_1$$$ and $$$w_2$$$ and do anti-shortcut for all edge of direct path between $$$w_1$$$ and $$$w_2$$$. The maximum possible length of the closed walk will be $$$4N$$$.

    The last problem is if $$$N$$$ is odd. If there is an odd cycle, going around it will make all vertices on cycle flipped. So, the parity of number of white vertices will change! Thus, we can solve in this pattern with maxium length $$$4N + N = 5N$$$.

    If $$$N$$$ is odd and the graph is bipartite... there's no way to complete the game. That's because the length of closed walk will be even because of bipartiteness of graph, but the length of closed walk "should be" odd because we need to flip vertices odd times.

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

      It seems to me that it used a same idea behind sevenkplus's pony round problem https://codeforces.com/problemset/problem/453/C.

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

      Just wanted to mention that we can actually improve the bound to $$$4 N $$$.

      Say $$$N$$$ is even. Note that the length of the walk is $$$2(N-1) + 2R$$$, where $$$R$$$ is the number of even subtrees. Since each even subtree root must have an odd subtree child, $$$R \leq \frac{N}{2}$$$, and this takes $$$ \leq 3N$$$ moves in total.

      If $$$N$$$ is odd, let the backedge in the cycle be from $$$u$$$ to $$$v$$$. Let the weights of $$$u$$$ and $$$v$$$'s parent be $$$0$$$ and of all other nodes be $$$1$$$. Now $$$R$$$ becomes number of even weight subtrees and $$$R \leq \frac{(N+1)}{2}$$$ still holds.

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

    Notice that we can invert the colours of any two vertices $$$a$$$ and $$$b$$$ with a cycle $$$a \rightarrow \ldots \rightarrow b \rightarrow \ldots \rightarrow a$$$. We can also use the root as vertex $$$a$$$. The only problem can be when everything except the root becomes black — then we need one odd-length cycle (so the only impossible case is bipartite graph, odd $$$N$$$). This way, we can get a solution with many edges.

    Now we can reduce the number of edges — if an edge $$$u-v$$$ is used $$$x$$$ times in the direction $$$u \rightarrow v$$$ and $$$y$$$ times in $$$v \rightarrow u$$$, where $$$x, y \gt 2$$$, we can reduce $$$x$$$ and $$$y$$$ both by $$$2$$$. The above approach gave us $$$|x-y| \le 1$$$, so this will result in either $$$x=y \le 2$$$ or $$$x \le 2, y \le 3$$$, which is $$$\le 5M$$$ moves. Next, all except at most one of these edges (in the odd cycle) can be from a DFS spanning tree. That actually gives at most $$$5N$$$ moves (details skipped).

    Finally, when we know how many times each edge is used, we can bruteforce an Eulerian cycle on them.

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

500 should have been 250, 1000 should have been 500, way too easy problems. However at least they were nice. Aaaand of course shitty pretests in 1000. I wanted to test my code on the odd positive case which they didn't cover but did it wrong and got challenged and got -166 to my rating RIP

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

    But it's true that only around 1/3 of people are solving Div1 500, despite around 2/3 of people are solving Div1 250. If you'd turn 500 to 250, it will be "DesperateForces" which is only enjoyable to high-rated coders :)

    I think Div1 500 is the problem which the solution is easy to come up with higher rated coders, and also implementation is easy, and that's why many high-rated coders got more than 450.00 points, but for blues and lower-yellows, coming up with such accurate greedy algorithm is difficult, when the problem comes to be not a typical greedy pattern.

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

      No, 500 is really easy. You can miss the trick, but you can fail at any problem. The drop in solving could be simply because 500 = intimidating: I looked for something more non-trivial, which led me to "and in this case we can push this person as far to the end as possible", then I started wondering when we can push someone completely to the end, and suddenly I just figured out the solution. If it was 250, I might have tried that right away.

      A problem that's really easy for high-rated coders is 250 if it's reasonably easy also for lower-rated ones. I believe this was the case.

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

      I spend about 45 minutes to solve the 250. And forgot to add the bigger than 2*D cards. :( And I solved the 500 around 25 min kind of brute force (without DFS etc). So maybe solved more people the 250 because most of the people start with that.

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

        This.

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

        The situation like you is very rare. Maybe you were lucky because you won against all contestants who only solved 250-point problem.

        Let's see contest standings.

        • There are ~70 contestants who solved Div1 250 but didn't solve Div1 500.
        • There are only 4 contestants who didn't solve Div1 250 but solved Div1 500.
        • However, there are 12 contestants who didn't submit Div1 250 but submitted Div1 500, but failing it in challenge phase or system test.
        • In contrast, only 1/4 of submitters of Div1 500 are failing in challenge or system test.

        Looking from the preceding 4 data, we can conclude that Div1 250 was by far easier than Div1 500, even if we swap the order of these two problems.
        I'd say, simply like, you were relatively not good at the problem like 250, and you were relatively good at problem like 500.
»
4 года назад, # |
Rev. 2   Проголосовать: нравится +12 Проголосовать: не нравится

Another point of view — I would argue the contest wasn't too easy, in fact — it was a bit on the hard side. The problems currently had success rate around 66% / 33% / 3% (ignoring people who didn't open any problems). A good contest (which is fun for most people in Div1) would have something along the lines of 80% / 50% / 5%. Currently one out of three people didn't have any points.

Yeah, I know there will also be the regular haters who are like "if you can't solve these problems go to Div 2" — but then again, do you want Div1 to be for ~20 people? If you are among those people and would feel superior by this, then good luck finding problem authors who are willing to spend many many hours coming up and preparing interesting problems for just a handful of competitors.

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

    So, problemset where I submit everything in 45/75 mins and ~40 users submit everything in time is on the hard side (some solutions failed, but that should be mainly attributed to weak samples)? K

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

      If you were among the people who managed to solve all problems I'd be somewhat more likely to agree with you, but you haven't, and even among the people with two problems you are not fastest. So, apparently there is way to differentiate between people even if they have equal number of solved problems (be it all three or not). But there is no way to differentiate between people with zeroes.

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

        Well since you focused on my performance I think that line of attack may backfire since in both medium and hard problems I got just small bugs which just shows that there were traps which were not covered by samples which shows that problems were even easier than it seems by looking at statistics. In medium I found it and resubmitted (that is why I have 370 pts instead of 447), in hard it was changing ".back()" to "[0]", but I quitted the contest 0,5h before the end of coding phase (and I was something like 10th person to submit all three problems even with that much time left). I was more used to times when typical number of people getting all three was something like 3 out of 700, not 20 out of 200.

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

        How is his performance related to what he is saying?

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

          I'm not claiming he's not good (his rating obviously shows he is) — I'm claiming that "it took me 45/75 minutes to solve the problems, so they were easy" isn't a fair claim if you haven't spent enough time to test your solution properly. Especially if you have 30 minutes after you have submitted all three.

          Also, I agree that the 1000 should be hard, but not that hard that even targets cannot solve it (which used to happen more often than not). This leads to 250 and 500 being deciders, and challenges playing a huge role. I suppose it is very hard to come up with a 1000 which only 3 people will solve. I'd personally prefer a hard which is solved by 20 people, than hard, which is solved by nobody.

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

            I agree that the balance is important, but for me it's more important to make contest interesting for everyone. If there are a lot of people who solve everything $$$30$$$ minutes before the contest, the contest was definitely not interesting enough for them. Somehow, it almost doesn't happen on Codeforces :) (Although it's easier to make balance here as we can have 5-6 problems)

            Also I believe that your bounds of 80% / 50% / 5% are highly unrealistic, taking into account lower bound of rating in Div1 now. I would go with 60%/30%/5%.

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

              Some time ago, Div1 250 was usually Div2 500. Nowdays it is more common for it to be Div2 1000 (like today). This makes it particularly huge jump for people who just were promoted to Div1 and haven't consistently solved Div2 1000 until then.

              I am really happy whenever there is at least one really easy problem in a contest (no matter whether TopCoder, Codeforces, ACM or whatever) so almost everyone has solved something. Since speed matters, if you solve it slow — you are still near the end and still lose rating. 40% of the people having a zero would mean many people who had an off-by-one error or some stupid bug (but the right idea) being ranked the same as people who have no idea what a bitmask DP is.