square1001's blog

TopCoder SRM 761 Announcement (from 3:00 PM UTC today!)
By square1001, history, 5 years ago, In English

Hi Codeforces!

It seems like (possibly) TopCoder SRM admins are busy with preparing online qualifier of "ltaravilse Cup" which will be held tomorrow, there was no announcement written by TopCoder SRM admins. Therefore...

I will announce that TopCoder SRM 761 will be held today! Here are some informations.

  • Start Time: 11:00 AM UTC-4
  • Duration: 75-minute Coding Phase + 5-minute Intermission Phase + 15-minute Challenge Phase + Systest!
  • Number of Problems: 3
  • Writer: I don't know the exact writer, but I guess it's misof :)

As usual, this match is rated (I hope). And I am looking forward to this match.

Don't forget that registeration phase will end 5 minutes before the contest! I hope that many of you will participate, as well as that we can solve many interesting problems.

If you have any question/discussion about contest, please write in comments :P

Useful Link: How to Compete in SRMs

UPD: Congratulations to Petr for winning Div.1 and farmerboy to win Div.2!
  • Vote: I like it
  • +55
  • Vote: I do not like it

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

I registered for TCC South America and when I switched to the tab for SRM 761, it said that I was registered for that as well. Turns out that I wasn't ... Is this only a problem with the web arena?

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

For real, find a sum of two repeated digit numbers?? And it's div1Easy?? Are you insane??

Problem like this maybe were probably okay in 2007 but it's 2019 now! It's freaking 2019!!!

And the more important question is who was that insane tester who approved the problem?

Argh, I'm so angry this is the most tedious and irritating problem I've seen in live contest for a looong time.

Worse than that are probably only problems about handling dates and calendar formats manually.

UPD: Here's another one instance of exactly this problem alongside with the one I mentioned a bit earlier.

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

    The contest isn't over yet, so I'm not going to comment on details, but I can see why it can work as a problem, especially a TC problem. (That doesn't mean I like it.)

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

      It may work as a problem in ICPC contest when it's okay to spend some time solving some technical garbage when you have nothing else to do. Or in TC div2 contest as medium or hard. But not as easy problem for TC div1 contest which lasts very little time and where easy problems are usually perceived as warm-up ones.

      For me personally it took approximately a hour to solve the problem, that is more then half of contest time. Okay, maybe it's me being too dumb or lame but I looked on room standings after ~45mins and there were only three submissions for the problem by some red guys.

      That's not how standings supposed to look after half a contest and it clearly doesn't follow aim of reducing TC problems difficulty claimed by misof. I think there were some time estimates on how long on average one should take to solve the problem on each level and this situation doesn't follow it either.

      And the first submission for this problem in my room was made by LLI_E_P_JI_O_K for the score of 243.34 and it has like few hundred lines and is obviously a copy-paste from some problem he probably solved before.

      Do you really think it's okay especially for TC to use very well known problem which is full of technicalities at the same time? So ones who solved it before would have vast advantage and others would get tilted at the very start of the contest?

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

        I think there are two fundamentally different ways to solve the problem: do it in the decimal form, or convert to fractions, add, convert back. I think the second approach doesn't have any technical difficulties or corner cases. It seems that you went for the first one, so you've shot yourself in the foot :)

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

          Yeah, sure thing. I suppose second one is the best choice when you don't have built-in long arithmetics and you're not up to change programming language to obtain it, right?

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

            long long was enough in this problem, I used BigIntegers to avoid thinking about it only.

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

          I was worried about the second approach being problematic, so I went for the first one and it worked. Lolrandom.

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

        Yes. It's a stupid implementation problem where you need to be careful. I spent like half an hour on making sure this crap works correctly.

        So? The difficulty is such that anyone can solve it (but there should be more samples simply because it's tricky), maybe with some guesses that the period/preperiod won't be too big. There are multiple approaches to the problem, some better, some worse. You don't like implementation problems that make you waste time? Solve 500 and 1000, that gives far more points. Don't trust yourself to solve 1000? Put that time into 250, maybe work on countertests for possibly wrong solutions. That's how TC often works (not that I like it), you have to follow good strategies and watch out for bugs because there's nothing except weak samples to check correctness. Even in TC, there's a good chance you'll end up having nothing to do, since there are much fewer problems and most likely, there will be just one that's giving you trouble and you can put your time into it.

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

          Judging by today's results I'd rather make instant rage-quit next time I spend more than 45 minutes on implementing TC div1easy. That would mean contest is already fucked up for me anyway...

          And I probably wouldn't be that mad if my first thoughts after seeing this problem weren't "Oh, no. I can't believe it. Not this shit again. Why. There should be something I miss. After all it's an easy problem. Right? Right?..."

          P.S.

          You don't like implementation problems that make you waste time? Solve 500 and 1000, that gives far more points.

          That is definitely what I would do if problem timer wasn't set to begin after I open the problem and not at the very beginning of the contest.

          you have to follow good strategies

          Not that you may know if your strategy is good or not for particular contest until it's too late to change it.

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

            That is definitely what I would do if problem timer wasn't set to begin after I open the problem and not at the very beginning of the contest.

            Nah, what I mean is that you can choose to give up on the 250 or decide that even if you hypothetically maybe solve it after 74 minutes, the amount of points lost by trying it last is low enough that it doesn't matter (or that you can farm up more points on challenges). In this case, the problem timer actually helps you — by giving up on the first problem you open, you don't get any direct penalty by wasting some time on reading it and figuring out that it isn't worth the time.

            Not that you may know if your strategy is good or not for particular contest until it's too late to change it.

            You don't know if your solution to a particular problem is good either, but you still bet that it is and try. If you can avoid choosing worse strategies more often, you'll have more success, just like when you can avoid choosing wrong solutions more often.

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

        Yes, I've already solved this in 2016 — submissions

        And this task (1318) has even bigger limitations — up to 20 digits, that's why I've used long arithmetic in the solution.

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

    Ha ha

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

    I don't like this problem either, but in my room at least 2 guys didn't manage to implement this

    UPD: ok, I've read your comment carefully and surprisingly found out that you didn't complain that the problem was standard thus easy, but that it was standard and technical. This puts my comment out of the topic you raised

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

    The problem is not completely evil though. For example, solution by KADR uses only rational numbers with int64 parts, and looks rather clean.

    If we choose to (1) implement the problem in C++ and (2) use big integer representation, that's our own choice. Which means it's the fault of the solver, not of the problem setter.

    [Edit:] I agree however that the problem actively provokes this faulty approach.

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

      Ok, maybe my main problem is that when I see the problem having lowest amount of points in the contest I want to solve it here and now and don't bother thinking much on how I'm going to do this beforehand. Even if it means that my solution is going to be a bit dirty and have some copy-paste or other bad stuff.

      Some problems, this one particularly are very resistant to this approach...

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

Bonus for Div1 250: Minimize the number of total digits in return string. Of course, if there are multiple optimal solutions, prioritize the period "0" than "9".

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

    Now that would be an ultimately evil version of the problem.

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

      Yeah, and this is what I thought at 2 minutes before the coding phase ends. I thought that I could challenge all of the solution in the room. But it turned out to be my first-ever challenge failing attempt in my life...

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

Thanks for educational problem 250. Now, I have a template for that kind of problem :)

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

I wrote the hard for this round (and I think misof wrote the other two). Here's a brief solution sketch:

Consider the following problem: You are given an undirected graph with $$$n$$$ nodes and $$$m$$$ edges. Each edge has probability $$$p$$$ of being destroyed, independently of each other. What is the probability the graph will be connected? It's easier to solve this problem for some fixed $$$p$$$, and you can do it in $$$O(3^n)$$$ time.

The probability can be written as a polynomial of $$$p$$$ with degree $$$m$$$. Call this polynomial $$$h(p)$$$. You can compute $$$h(p)$$$ by doing the addition/subtraction of polynomials in the above dp for an additional factor of $$$m$$$ in the runtime.

Consider another way to compute $$$h(p)$$$. We can compute $$$h(p) = \sum_{i=0}^{m} f(i) \cdot (1-p)^i \cdot p^{m-i}$$$. Thus, given the coefficients of $$$h(p)$$$, we can extract out $$$f(i)$$$.

There are some small optimizations you also probably need to do in the dp. For example, you can loop up to the degree of the polynomial in the submask rather than all the way up to $$$m$$$. My final number of operations is something like $$$3^{n-1} * n + 3^{n-2} * m$$$.

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

    Why require us to make non-asymptotic optimizations in the dp? Why wouldn't it be better to raise the TL to something like 5 seconds? I'd be so furious if I submitted a slightly slower solution and randomly failed due to that.

    (Now I'm only furious because of 250 and a well known 500.)

    Nice hard, though.

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

      The reason is 3^n * m^2 also has similar optimizations and is quite fast and the idea for that is too easy so I needed some way to separate them. I’m not sure there is a really good solution to it through, and this was the best compromise I could come up in time for this round.

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

      A few years ago I came up with the same problem as div1-medium, prepared it for Hackerrank and then didn't use it because a tester said it's well known :(

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

    This is a great problem, thanks! For reference, the polynomial you mentioned is a special case of the Tutte polynomial known as the reliability polynomial: https://en.wikipedia.org/wiki/Tutte_polynomial#Reliability_polynomial.

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

      From this wiki page, I don't consider it great. It is similar to 500. You know you win. It is almost impossible to come up with from scratch especially in very short contest likes SRM.

      At the beginning as I read it, I guess it is result of some theory.

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

        Even if we know Tutte polynomial, I think it is still difficult to come up with it, because I think it is non-obvious that we can restore probability for decided number of edges, just by coefficients of polynomial $$$∑a_{k}p_{k}$$$.

        Obviously, the problem statements seems like it's a combinatorics problem, not probability problem. So I think that the first step is the most important part for this question, which is not typical. For this reason, the reference seems it's just like posting a link to flow problem when problem requires a flow.

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

          It takes me a minute to restore $$$f(i)$$$: $$$p^i * (1 - p)^{m - i}f(i) = (\frac{p}{1 - p})^if(i) * (1 - p)^m$$$.

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

            Well, I thought that I mentioned two points:
            It is difficult to see that "the polynomial $$$f(p)$$$ which computes the probability of being graph connected when edge-disappearing probability is $$$p$$$", is describing the combinations of $$$m$$$-edge combinations.
            It is difficult to come up with the idea using similar but completely new probability problem while solving combinatorics problem. I think you claimed the point 1 is easy and takes only one minute for you, but not for the others. I also think that it is difficult to compute $$$f(p)$$$ for single $$$p$$$ in $$$O(3^{n})$$$. I only have came up with $$$O(3^{n}×n)$$$. (UPD: Finally came up, but it was not easy)

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

              I just express my thought why it is not great. Though it bring a new knowledge for me. Knowing that theorem is 99.999% of solving the problem.

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

                I just express my thought why knowing that theorem is not 99.999% of solving the problem.

                I actually came up with the similar idea of polynomialize for probability $$$p$$$, which my solution came up during the contest was to polynomialize the number of "weighted combinations" when the way of selecting "not choose" is $$$1$$$ but "choose" is $$$x$$$. (It is almost equivalent to Tutte polynomial when $$$p=1÷(1+p)$$$).

                So coming up with this idea is not difficult as you think. However, I didn't came up with solution of main problem because I struggled with the other parts.

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

Medium is also a classical problem. I remember KOTEHOK said that he read about it in Cormen and then it appeared in one of ICPC world finals that he won.

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

Note that in Python solution for 250 is as easy as:

from decimal import *
prec = 300
prep = 20
getcontext().prec = prec

def get_period(s):
    ans = len(s)
    for x in range(len(s)):
        if s[:x] == s[-x:]:
            ans = len(s) - x
    return ans

class AddPeriodic:
    def add(self, A, B):
        A = A[:-1].split('(')
        B = B[:-1].split('(')
        A = Decimal(A[0] + A[1] * prec)
        B = Decimal(B[0] + B[1] * prec)
        
        C = '{:f}'.format(A + B)[:-prep]
        
        period = get_period(C[-(len(C) - prep):])
        
        while C[-period-1] == C[-1]:
            C = C[:-1]
        
        return C[:-period] + '(' + C[-period:] + ')'

So much different from the hell you go through in C++...

But even here there are some caveats like the necessity to use '{:f}'.format() instead if str() to avoid zero being represented as 0E-500...

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

    Yeah, solutions in Python are usually shorter than the ones implemented in C++

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

Hi, i participated in the round ( Div 2 ), how can i see the problems of both division?

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

There is no editorial for SRM 760 and SRM 761 here https://www.topcoder.com/blog/tag/srm-editorials/ . I am unable to find that, Can anyone provide me the link of editorials. Thanks in Advance !!

→ Reply