Topcoder SRM 697 starts in around 16 hours, and no blog made yet. So I thought I'd make one.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | nor | 157 |
4 | atcoder_official | 156 |
4 | cry | 156 |
6 | -is-this-fft- | 155 |
7 | maroonrk | 154 |
8 | adamant | 153 |
9 | Um_nik | 151 |
10 | djm03178 | 146 |
Topcoder SRM 697 starts in around 16 hours, and no blog made yet. So I thought I'd make one.
Name |
---|
Cool! No one solved the easy problem :D
There are some technical issues with Easy, should be resolved in a moment.
You can enjoy the detailed editorial at the topcoder website.
ConnectedStates can also be solved with exponential generating functions(the answer is (n - 2)! times the coefficent of xn - 2 in the power series of
, where p and s are the product and the sum of all ai.
Well, this was not what we wanted =(
solution. O(n2) is intended. It also can be optimazed to
.
We forgot about
It does work in O(n2) though.
Oh, now I see it. Then it is intended one =)
I have no idea what you just said, but that sounds really crazy.
(I'm sure I'm not the only one thinking this)
Btw, there is an excellent article on exponential generating functions.
I found it very useful at a time.
http://www.artofproblemsolving.com/community/c1157h990764_the_combinatorics_of_basic_calculus
Thanks! :)
Were you the writer ? If so first of all thanks alot ! Btw where was Limak, on a vacation ?:P
"no Limak" => "I'm not a writer" ;)
I was a tester (and editorialist this time). A writer was Arterm.
How to solve Div2 Hard (XorOrderDiv2) ?!
May be out of the topic But where are the editorials for the SRMs(I mean 696 and others) which are missing on this page here
Yeah i too can't find them , some one please explain
All editorials are at the website you linked. They are usually created after the round, sometimes with much later.
Thanks for guiding... (It means I should check the page regularly after the contest if I do not find just after the contest... ) :)
For 696 in particular I started a post that currently only has div1 easy, but today I got AC on div2 hard and div1 medium, I will write the explanation later today :)
Thanks for the efforts....
Hi, I was writer this time, Errichto was a tester.
I apologize for the issue with div1-easy, I occasionally commited wrong solution during the contest to see if it works. We still don't know if it affected anybody during challenge phase, if it affected the contest probably will be unrated.
Hope you found some interesting task during the contest anyway.
UPD: We believe that most likely it didn't affected any challege. So there is a strong chance it will be rated.
Is it common for things to be tested during the competition? IMO, it's far better to let incorrect solution pass than to run the risk of this happening during systest.
Arterm thought that he has made a mistake in one of his generators, went to the problem-preparing system, compiled his own solution with something added, and run it on all tests. Btw. everything was ok with tests so it was all unnecessary. Unfortunately, that solution was saved for some reason.
I don't imagine being unable to test something during the contest. Organizers often want to check something. In particular, sometimes we are worried about the correctness of our solutions of the validity of the test data. It means that we use the system sometimes. In this particular case it wasn't a must, but who would think that checking something will lead to issues with the systesting? The risk seemed to be to small to consider it (but yeah, sth went wrong).
I must also add that it was me who advised him to just "compile and run" in the system. I thought that not submitting won't save a solution. So my advice was very very bad.
I'm pretty sure exactly the same thing happened in a recent SRM (I don't remember exactly which, maybe someone with a better memory can tell us), so the chance must be bigger than you imagine :)
It's computing, whatever can go wrong usually does, which is why you should only mess with things as a last resort (e.g. test data doesn't follow constraints, or there is a high probability the solution is wrong). I'm pretty sure solutions that don't sort the array would be very easily challenged anyway.
Yeah, you are right I think.
I remember an interesting situation from one CF round. It's advised that a checker should print some info in case of WA, e.g. "the printed numbers must be distinct". It's displayed only during the upsolving (and organizers see it during the contest). During the round we saw that in one case a checker prints 0 instead of some other number in the middle of some message. I made a change (requiring some new variable) in the checker (why not, right?), run tests on all our ~10 solutions, and committed. A moment later I found a mistake and managed to find a wrong solution for which my new checker gives AC. Ok, I must quickly go back to the first version. And then I REMOVED the checker by mistake. Polygon is smarter than me though, and it didn't allow me to update a problem in the CF round. Yeah, that was fun. And note that the first change wasn't even important — that info wasn't displayed to any participant during the contest. During the contest you would see only e.g. "WA on test 4" anyway.
small note: I simplified the story a bit. In particular, not only Polygon but also a coordinator tries to not allow you to destroy a contest.
I'm pretty sure exactly the same thing happened in a recent SRM
Are you thinking of SRM 652? This was a while ago (over a year), but in that case, some last minute changes were made to the checker but there was a mistake. Details located here and here.
And the other way around, software should be designed to be as foolproof as possible — if a user could do something wrong, it should be expected that he will do it for sure.
I believed it is completely safe. Like, we discussed and agreed not to changing testset. I was just curious if wrong solution will pass. But, unfortunately, it went to production and messed up.
If you interestring, issue was the following: in around 30%-40% of testcases all b-s were sorted. So, if you want to check they distinct checking each adjacent pair, you may fail if you do not sort.
No electricity supply for 14 hours. That's why no blog. I didn't even got the chance to participate in SRM.
Thanks to MedoWith11Es for the post.
please anyone can explain the div2 hard(1000)..
I have read the editorial but couldn't understand how trie tree work. I need some help how trie work for this problem. Thanks in advance.