hmehta's blog

Topcoder SRM 786
By hmehta, history, 4 years ago, In English

Topcoder SRM 786 is scheduled to start at 11:00 UTC -4, May 15, 2020. Registration is now open for the SRM in the Arena or Applet and will close at 10:55 AM, so make sure that you are all ready to go. Please note that the coding phase will begin at 11:05 AM UTC -4 but the registration will still close at 10:55 AM UTC -4.

Thanks to jeel_vaishnav and vivek1998299 for writing the problem set. Also thanks to misof for testing and coordinating the round.

This is the fourth SRM of Stage 3 of TCO20 Algorithm Tournament.

Stage 3 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!

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

Comments Comments (58)
| Write comment?
»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Blog says it starts at xx:x0 whereas schedule in applet says it starts at xx:x5. A difference of 5 mins. Will it start at time in blog or time in applet?

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

    The contest starts at 11:05.

    We were earlier planning for 5 min buffer time for late registrants but eventually had to use those making it 10 mins for room assignments.

    Room Assignments have been causing some trouble and we are investigating. Thus buying 5 more mins than usual helps us fix things before the contest begins.

    Thanks for understanding :)

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

If you are looking to register for SRM in the Web Arena. Please click '2' to access the match.

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

Gentle Reminder: Round begins in 35 mins :)

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

Is there any smart way to generate input, or you just need to rewrite code in your language and take care about overflow ?

I usually spend 5 minutes just to read data on proper way in the task. I do not see anything bad to give us valid implementation of input in needed languages.

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

    I wasted a lot of time in hard because of a typo in generator..

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

    Related:

    There are many good platforms out there for problems with $$$n$$$ up to $$$2\,000\,000$$$, where an additional step of artificially generating pseudorandom input becomes unnecessary.

    Today's round makes me miss the old-style TopCoder problems with $$$n$$$ up to $$$50$$$ which align with the platform naturally.

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

      I actually think med will be the same problem with $$$n=500$$$ and $$$n=2000000$$$

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

        When you already know and implement this part of the solution, yes.

        Until then, it's another parameter which a contestant can fail to optimize. Granted, this part is fairly trivial, and can be modularized. But still, in the contest environment, the overall problem complexity weighs up on people.

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

          Well, is there any idea that is not included in $$$n=500$$$ but in $$$n=2000000$$$?

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

            Yes, and it's bringing large $$$n$$$ to $$$n \le 512$$$.

            Yes, it's trivial compared to the other ideas in the problem. Even so, I've seen two different takes at implementation in my room, and each one adds a few extra lines to the implementation. Which mean more room for bugs, and more load on the contestant's brain overall.

            Your question seems to imply that I'm liking that part of the problem as having another worthy idea. This is not the case, I'm trying to be impartial. What I was trying to say is that, the more ideas a problem throws into the mix, the harder (non-linearly) it is for a contestant to untangle the mix.

            I recall an example when my hard problem's solution process was going like: "...and on top of that, the answer can be up to $$$10^{50}$$$; come on, I know you likely use C++, but it's trivial compared to what you have been through so far!". And a contestant later reported that was the last straw... I see it as unfortunate for the problem and the contestant alike.

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

            How to solve it for such high bound? I can think of the solution from editorial

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

              If you solved it in poly-time, you would've already used linearity of expectation. That formula only depends on $$$a_i$$$. So just precompute value for each $$$a_i$$$.

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

                I did not think in terms of linearity of expectation. My idea is something like:

                • if I am at 0, after k moves what's the probability that I am at i?
                • if we know these 512 values, we can just multiply this same array to get the probability after 2k moves This way in n^2logk time I found the contribution of each ai to every number.

                I am not sure how to do it in nlogk.

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

                  That's not the $$$n$$$ we are talking about..

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

I hate |input| = 200000 in Topcoder, OK this is personal.

Did any tester really try to "solve" the problems in the final statement?

1000-pointer: After V = val, accessing V[size(val)] violates the bound. Fine, it's a pseudocode, but who faithfully coded according to it in the languages available at Topcoder would have a trouble. Do you really need this trap?

250-pointer: The same issue as above. Why didn't you just say "append (char)(A[i] % 26 + 'a') to S"? Also, when I copypasted the pseudocode into my editor, line breaks has gone and it became terrible.

The second reason I performed badly was that I lost much time by these kind of things (The first is of course that I am not good enough at implementing). I strongly believe that, at least, lengths of arrays in such pseudocodes should be explicitly written.

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

    250: I wrote s[i] = ... instead of appending. Hope it is okay :)

    Update: FST :(

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

      I had to resubmit because of this, given that the length of P is min(N,100) :(

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

    Honestly I hate overflow bugs and assign vector to array at most — and it could be fixed easily with a little more time invested in the statements.

    Also, my code was successfully compiled with warnings, but when I tried to submit there was a message — "You can not submit until your code is successfully compiled".

    Tasks ideas were nice to me.

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

    Really apologize for the inconvenience.

    Actually we used the same kind of generators in our previous two contests SRM 763 and SRM 772, and those contests went quite good, so we decided to go with the same generators.

    Next time onwards we'll surely take into notes your concern while preparing the statements.

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

Casually gonna promote my channel here. Screencast and solution for Div 1 250 SwapTheString

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

What's the point of 500-point problem? I'm honestly asking, why would anyone think that 512 is a good constant?

There's is a solution with better complexity using some 'clever' observations, but authors allow SOME implementations of matrix multiplication. Why? If you're allowing matrix multiplications, then why not 128? If you don't want to allow them, then why not 1024 or 2048?

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

    Well I am not sure what is your solution, but my (not yet submitted) solution has complexity $$$O(const^2 \cdot log K)$$$, and I struggled for 10 minutes to decrease it from $$$O(const^3 \cdot log k)$$$.

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

      The observation is that the matrix is of form $$$c \cdot (a \cdot I + J)$$$, where $$$J^{512} = I$$$.

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

    Also, there is no good reason for the bound to be a power of 2.

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

      Modulo counters are digital logic devices and hence can allow counting till 2^p with p bits. We used a power of 2, just to give an analogy to the modulo counter devices used for digital logic.

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

    The complexity of the intended solution was O(n^2logk), where n is the counter size. Keeping n = 1024 would result in computations of about 10^6 * logk. While this would pass quite easily in the given time limit, we thought that keeping n = 512 would ensure quick evaluation of code as well as would not allow O(n^3logk) solution to pass.

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

Is there any plan to allow huge input instead of providing a generator for each problem?

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

    Please.

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

    FYI, it took them years to move from $$$50$$$ to $$$2000$$$.

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

      Wow, can anyone tell me what's so difficult about allowing huge inputs?

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

        AFAIK they'd have to rewrite the whole problemsetting infrastructure. It's also based on a Java applet called MPSQAS, where you have to paste the inputs. If you copypaste a huge test into this applet, it freezes.

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

Why give problem about the same idea as problem from 2 SRMs before?

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

    Not only that. In yesterday's dp practice contest (not uploaded yet) there was this task.

    If the limit on the counters in today's 500 and on the N in RandomSwaps <= 100, then fast multiplying the whole matrix would solve both problems in O(N^3logK).

    For RandomSwaps it was enough to generate only one row in O(NK). I noticed that it could be done in O(NlogK) or even faster but didn't implement it, as worse complexity passes.

    Today it was enough to generate one row in O(N^2logK), which I did not manage to implement in time. However, the idea of both tasks is almost the same.

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

In Div2, 500: are tests like "((" allowed? Isn't it required for the input to be "regular bracket sequence"?

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

Are system tests weak for Div1-250? My code got challenged, probably on input like "AAAAAA...." (single letter string) but submitting it in practice passes system tests.

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

Why is it so easy to reach Div1 on TopCoder? I have given only 3 SRMs including today (for some reason TC only counts 2). First SRM, failed all problems, second SRM managed to solve only Div2 Easy fast, today's SRM — managed to solve Easy fast and managed to solve Medium. The arena is showing me blue now.

The Div. 1. rating bound should be at least 1400 IMO.

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

My Div2, 500 solution works just fine on my system for some test case but fails system tests on the same test due to segmentation fault.. can anyone guide me with the reason? Thank You in advance!!

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

    Solved it, finally!! I sincerely apologize for whatever the reasons for the downvotes might be.. Thank you!

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

Help required in Div 2 B (SMALLESTREGULAR)

After seeing the editorial i was trying to submit code as editorial

editorial code:

public int[] findLexSmallest(String S) {
    ArrayList<Integer> res = new ArrayList<Integer>();
    int n = S.length();
    boolean closing = false;
 
    for (int indx = 0; indx < n; indx++) {
        if (S.charAt(indx) == ')')
            closing = true;
        else {
            if (closing) {
                res.add(0);        // a
                res.add(indx - 1); // b
                res.add(indx);     // c
            }
        }
    }
    int[] ans = new int[res.size()];
 
    for(int i = 0; i < res.size(); i++)
    {
        ans[i] = res.get(i);
    }
    return ans;
}

My code:

#include <bits/stdc++.h>
using namespace std;
#define lli int
class  SmallestRegular{
    public:
      vector <int> findLexSmallest(string S){
        vector<lli>ans;
        bool firstclosing =false;
        for(int i=0;i<S.length();i++)
            {
                if(S[i]==')')
                    firstclosing=true;
                else{
                    if(firstclosing)
                    {
                        ans.push_back(0);
                        ans.push_back(i-1);
                        ans.push_back(i);
                    }
                }
            }
            return ans;
     }
};

It shows the Wrong answer ...please somebody help :)

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

    Your solution misses few things . For example if(s[i] is '('&&first closing is true ).Operation will take place and s[i] turns into ')' from '('. So dont forget to change s[i] to ')' after every ops.

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

      I can't understand ... I wrote exactly same as editorial :(

      https://www.topcoder.com/single-round-match-786-editorials/

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

        I think they skkiped that part because Your code is working after adding one more line.

        include <bits/stdc++.h>

        using namespace std;

        define lli int

        class SmallestRegular{

        public:

  vector <int> findLexSmallest(string S){

    vector<lli>ans;
    bool firstclosing =false;

    for(int i=0;i<S.length();i++)
        {
            if(S[i]==')')
                firstclosing=true;
            else{
                if(firstclosing)
                {
                    ans.push_back(0);
                    ans.push_back(i-1);
                    ans.push_back(i);
                    S[i]=')';
                }
            }
        }
        return ans;
 }

        };

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

          Thanks buddy now it passed....please tell me why we add "s[i] = ')' " ... what is the need of this?

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

            Bro Topcoder sometimes sucks....when i submit same code(my cpp code) after refreshing and again logging in..then it perfectly runs ...LMAO.

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

              Well . I think they were not changing the string by themselves after every operation . Instead they were seeing Your string as the current processed string . they might recheck it .ha ha

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

In topcoder where can I find list of my solved problems, like for atcoder I have kenkoooo. I just want to see the solved questions along with rating, and unsolved ones.

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

    goto practice session ..filter with submitted

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

      Thanks mate, but its not showing anything, just blank page when I apply solved tag. I am using web arena.

      Also how can I find actual new ones instead of alphabetical ordered, for example I need 786 to be on top, then 785 etc. And where are the problems of unrated dp contest that started yesterday!?

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

        That contest has finished -> it is in practice section\special events.

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

Hey Arpa can you help in figuring out the mentioned straightforward transition step in Div1-Medium $$$dp[t][i] = p*dp[t-1][i] + q*(dp[t-1][i] - 1) + r*(dp[t-1][i] + 1)$$$ where $$$p, q, r$$$ are probabilities of selecting counter which do not have value $$$i$$$ or $$$i-1$$$, selecting counter with value $$$i$$$, selecting counter with value $$$i-1$$$ respectively. How can I find these probabilties ? Is $$$q = dp[t-1][i]/n$$$, $$$r = dp[t-1][i-1]/n$$$ ?

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

    With probability $$$\frac{1}{n}$$$ a counter will be selected. So, $$$dp_{t, i} = dp_{t - 1, i - 1} \times \frac{1}{n} + dp_{t - 1, i} \times \frac{n-1}{n}$$$.

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

can any of you show me how i suppose to submit my code in topcoder contest.in codechef,codeforces,atcoder i can just copy paste in the editor and submit it.but when i doing the same thing in topcoder it is showing compiling error

→ Reply