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

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

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!

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

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

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?

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

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

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

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

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

Gentle Reminder: Round begins in 35 mins :)

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

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.

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

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

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

    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.

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

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

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

        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.

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

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

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

            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.

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

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

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

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

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

                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.

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

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.

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

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

    Update: FST :(

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

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

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

    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.

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

    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.

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

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

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

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?

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

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

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

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

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

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

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

      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.

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

    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.

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

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

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

    Please.

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

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

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

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

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

        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.

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

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

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

    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.

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

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

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

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.

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

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.

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

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

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

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

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

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

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

    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.

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

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

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

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

        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;
         }

        };

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

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

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

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

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

              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

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

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.

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

    goto practice session ..filter with submitted

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

      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!?

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

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

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

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$$$ ?

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

    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}$$$.

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

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