Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### MedoN11's blog

By MedoN11, history, 7 years ago,

Topcoder SRM 697 starts in around 16 hours, and no blog made yet. So I thought I'd make one.

Timing here

• +72

 » 7 years ago, # |   +33 Cool! No one solved the easy problem :D
 » 7 years ago, # |   +58 There are some technical issues with Easy, should be resolved in a moment.You can enjoy the detailed editorial at the topcoder website.
•  » » 7 years ago, # ^ |   +23 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.
•  » » » 7 years ago, # ^ |   +5 Well, this was not what we wanted =(We forgot about solution. O(n2) is intended. It also can be optimazed to .
•  » » » » 7 years ago, # ^ |   +23 It does work in O(n2) though.
•  » » » » » 7 years ago, # ^ |   +5 Oh, now I see it. Then it is intended one =)
•  » » » 7 years ago, # ^ |   +12 I have no idea what you just said, but that sounds really crazy.(I'm sure I'm not the only one thinking this)
•  » » » » 7 years ago, # ^ |   +26 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
•  » » » » » 7 years ago, # ^ |   +23 Thanks! :)
•  » » 7 years ago, # ^ |   +15 Were you the writer ? If so first of all thanks alot ! Btw where was Limak, on a vacation ?:P
•  » » » 7 years ago, # ^ |   +36 "no Limak" => "I'm not a writer" ;)I was a tester (and editorialist this time). A writer was Arterm.
 » 7 years ago, # |   +11 How to solve Div2 Hard (XorOrderDiv2) ?!
 » 7 years ago, # | ← Rev. 2 →   +5 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
•  » » 7 years ago, # ^ |   +1 Yeah i too can't find them , some one please explain
•  » » 7 years ago, # ^ |   +9 All editorials are at the website you linked. They are usually created after the round, sometimes with much later.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 Thanks for guiding... (It means I should check the page regularly after the contest if I do not find just after the contest... ) :)
•  » » 7 years ago, # ^ |   +11 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 :)
•  » » » 7 years ago, # ^ |   +8 Thanks for the efforts....
 » 7 years ago, # | ← Rev. 2 →   +9 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.
•  » » 7 years ago, # ^ |   +21 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.
•  » » » 7 years ago, # ^ | ← Rev. 4 →   +26 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.
•  » » » » 7 years ago, # ^ |   +31 In this particular case it wasn't a must, but who would think that checking something will lead to issues with the systesting? 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.
•  » » » » » 7 years ago, # ^ | ← Rev. 5 →   +26 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.
•  » » » » » 7 years ago, # ^ |   +8 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.
•  » » » » » 7 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 7 years ago, # ^ |   +19 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.
 » 7 years ago, # |   +4 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.
 » 7 years ago, # |   0 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.