ECNA 2019 Problem B

I've been giving it read after read and can´t really figure out why is 1-4-3-1 for length 6 not a valid solution. Would appreciate help understanding why is that particular solution invalid, the problem is not really written in a clear way.

After reading a very interesting article about Mobius function , I stumbled into one of the proposed problems, GCDEX2 . The problem is, all the proposed algorithms in the original article need O(N) memory, precalculation time (to answer queries in time ), which is too much for the proposed constraint. Ideas? Thanks in advance.

I've been trying to solve Pipes selection for some time, but i have not had productive ideas. The best idea so far is grouping the prefix sums by their residue modulo every prime to speedup search in some way, but I have not managed to make it work. Suggestions?

I stumbled upon UVA Summing the Lengths of the Longest Increasing Subsequence of Permutations, that basically asks for the first three digits of the sum of the LIS lengths over all permutations of length n. After trying it or a few days, I gave up and searched for information. It is easy to see that:

Where denotes the expected value. It is easy to manage the logarithm of that number with Stirling's approximation, get the fractional part of the logarithm and exponentiate to get the first digits. Nevertheless the core of the problem lies in computing for a random permutation w of length n. I have been reading about the topic, and this paper gives the estimate

Where c ≈  - 1.77108 as a known estimate. Nevertheless, this doesn't give the ouput of uDebug and differs by a  ± 1 margin in about 5% of the cases . I have also asked the question in MathOverflow, and it seems that that estimate is the best known and that there is no polynomial or logarithmic time algorithm for computing .

Finally, I am right now trying to contact the problemsetter baodog looking for clues, as there seems to be few options now:

• He has improved the state of the art in computing without knowing so and expects the contestant to do so too.
• He has not improved the state of the art and expects the contestant to provide a solution.

The last option is ethically questionable. The problem stats page is quite strange too, since the only accepted solution's are Josh Bao's(the problemsetter) in the 2007 and someone else 20 days later. Also, the old version of the problem asks for the first 5 digits and has a different output for the same input truncating it to the first 3 digits. Moreover, I get the old output by truncating the BDJ estimate to as shown by this code. So, can someone provide help to solve this problem and I am not seeing something obvious? Am I right and this problem is impossible with today's knowledge of the matter?

I have been trying to do UVA "Ahoy, Pirates!" but it seems there is an error somewhere. I have downloaded code that gives AC to test against my solution on test cases generated by a program I wrote](gives RE in ideone because of long output) and compared the outputs with WinMerge, only to see that they are identical.

One curious thing I noted was that changing M from 101 to 301 in the code converts the Wrong Answer into a Runtime Error, which baffles me. Would you please help me in finding the error in my code, or is there an error somewhere else?

Edit: Ran it through the test cases generated by my generator using VS 2012 compilation with array bounds checking, not a single error reported.

I have always wondered what is the philosophy behind those ICPC problems that don't specify the number of test cases. What are the problem setters trying to evaluate, and how should I respond? Obviously, enough test cases will TLE out my solution.

One of the great things about programming contests is choosing the right algo for the right job, say, I wouldn't go full Fast Fourier Transform if simple convolution gets the job done. So, should I respond to those problems with the best algo I can think of? Should I respond with a provably optimal algo? Or, should I reverse engineer the problem-setter expectations and choose something along those lines?

This blog is intended for discussion, please don't understand this as a rant :)

Problem A of Gym is giving me a lot of trouble. I have reviewed my code multiple times and after several Wrong Answers I can't see the mistake. Any help is appreciated :) My submission