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!
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?
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 :)
If you are looking to register for SRM in the Web Arena. Please click '2' to access the match.
Gentle Reminder: Round begins in 35 mins :)
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.
I wasted a lot of time in hard because of a typo in generator..
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.
I actually think med will be the same problem with $$$n=500$$$ and $$$n=2000000$$$
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.
Well, is there any idea that is not included in $$$n=500$$$ but in $$$n=2000000$$$?
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.
How to solve it for such high bound? I can think of the solution from editorial
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$$$.
I did not think in terms of linearity of expectation. My idea is something like:
I am not sure how to do it in nlogk.
That's not the $$$n$$$ we are talking about..
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.
250: I wrote s[i] = ... instead of appending. Hope it is okay :)
Update: FST :(
I had to resubmit because of this, given that the length of P is min(N,100) :(
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.
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.
Casually gonna promote my channel here. Screencast and solution for Div 1 250 SwapTheString
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?
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)$$$.
The observation is that the matrix is of form $$$c \cdot (a \cdot I + J)$$$, where $$$J^{512} = I$$$.
Also, there is no good reason for the bound to be a power of 2.
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.
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.
Is there any plan to allow huge input instead of providing a generator for each problem?
Please.
FYI, it took them years to move from $$$50$$$ to $$$2000$$$.
Wow, can anyone tell me what's so difficult about allowing huge inputs?
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.
Why give problem about the same idea as problem from 2 SRMs before?
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.
In Div2, 500: are tests like "((" allowed? Isn't it required for the input to be "regular bracket sequence"?
Sorry for the inconvenience, it will be fixed soon.
How you will revert wrong hacks ? Round will be unrated ?
One of the users hacked all the solutions in our room with an "irregular bracket sequence".
yep we were in the same room I guess..
Vivek1998299 Could it be fixed ?
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.
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.
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!!
Solved it, finally!! I sincerely apologize for whatever the reasons for the downvotes might be.. Thank you!
Help required in Div 2 B (SMALLESTREGULAR)
After seeing the editorial i was trying to submit code as editorial
editorial code:
My code:
It shows the Wrong answer ...please somebody help :)
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.
I can't understand ... I wrote exactly same as editorial :(
https://www.topcoder.com/single-round-match-786-editorials/
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; }};
Thanks buddy now it passed....please tell me why we add "s[i] = ')' " ... what is the need of this?
Bro Topcoder sometimes sucks....when i submit same code(my cpp code) after refreshing and again logging in..then it perfectly runs ...LMAO.
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
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.
goto practice session ..filter with submitted
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!?
That contest has finished -> it is in practice section\special events.
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$$$ ?
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}$$$.
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
Click