Yes, the answer to this tests seems to be 4, not 11.

i was there and i saw hes been trying soo hard but couldnt succeed that was sooo saaad T_T T_T T_T like this comment if ur sad to

You're right. Since I was not able to prove the convergence, there is no guarantee, only several pieces of evidence. One evidence is that, during the contest testing, all other solutions had an absolute error less than $$$10^{-10}$$$. Another strong evidence is that, when I tried two starting approximations, one unital (i.e. less than the answer) and the other one $$$x_u = (n - 1)^2$$$ (i.e. greater than the answer), they both ended up as approximate solutions with absolute error less than $$$10^{-10}$$$. Since the small and the big starting points converged to basically the same point, it is highly believable that the real solution should also be near that point. (Maybe it is possible to prove some analogue of the squeeze theorem, in which case I will be able to certify the validity of each test. But, again, I did not prove that.) Another convincing fact is that in the end the distance between the current approximation and the next one is really small (that is, all $$$|L|$$$ equalities are approximately true). Generally, the vicinity of $$$x_n$$$ and $$$x_{n + 1}$$$ does not imply the vicinity of $$$x_n$$$ and $$$\lim x_i$$$ (e.g. $$$\sum_{i = 1}^n{\frac{1}{i}}$$$ is near $$$\sum_{i = 1}^{n + 1}{\frac{1}{i}}$$$ but $$$\sum_{i = 1}^{\infty}{\frac{1}{i}} = \infty$$$), but there are some additional conditions which may lead to it, e.g. alternation of the sign of $$$x_n - \lim x_i$$$. I am not a specialist in the theory of multidimensional dynamical systems, but I stronly believe that there should be a similar way to strictly prove the convergence in our case. Also not only $$$x_{10\,000}$$$ and $$$x_{10\,001}$$$ are close to each other, but also $$$x_{2\,000}$$$ and $$$x_{15\,000}$$$ are (and, I believe, everything in between is also near the answer, too, although I did not check that explicitly).

More than with the fact that I did not have a strict proof of the correctness of the tests, I was frustrated with the fact that some participants struggled to find the proof during the contest and thus did not attempt the problem. For example, both turmax and Jatana did all the math on the paper, but were not able to make the last step of not trying to find an analytical answer and apply some numerical method instead. What ultimately prevented them from submitting and ACing the problem might have been the belief that the jury had a strictly provable solution. This makes me feel a little bit awkward, as if I should feel like I've let the math fraternity down.

Sorry, folks. As many problemsetters say, there are basically two ways to come up with a problem: think of an solution idea and develop it into a problem which is solvable with this idea (solution↦statement), or think of a nice problem statement and do your best to try and solve it (statement↦solution). This problem was created with a statement↦solution approach, so what written in the tutorial is basically the best approach I was able to come up with (and the furthest point up to which I managed to strictly prove everything). It is possible that it is simply impossible to come up with a satisfying proof of convergence; it is even possible that there is some other procedure which converges faster (and, moreover, converges provably), but this method is unsuitable for a contest, because it will take all five hours of the contest, or even more, to come up with a quick method, to prove it, and to implement it. This is the problem, and I am sorry that optimally (for the contest) solving it requires both being a mathematician and, at the right moment, ceasing to be one.

Still I believe the problem is quite nice, and this is my highest quality and most difficult problem that I have offered to competitions of such a high level. I am so glad that a lot of talented programmers tried it!

I believe this approach (slightly different iteration as the model solution) gives upper bounds on the correct answer and does converge, though I'm not sure about the convergence rate.

Initialize $$$x_l$$$ to be an upper bound on the answer starting at each node l. From the police officer's point of view, we can update each $$$x_l$$$ to the optimal answer given the values of other $$$x_j$$$: the fugitive should pick the minimum threshold $$$A$$$ where $$$q_j$$$ can be set so $$$d_{l,j} + (1-q_j)x_j \le A$$$ for all j. The computed value of $$$x_l$$$ is the same as the editorial's formula when all $$$q_j$$$ are positive, however this may not necessarily be the case with current values of $$$x_i$$$. Since each $$$x_l$$$ is decreasing, they must converge and in the limit must satisfy the same equations.

EDIT: Now that I think about it, the matching approach for lower bounds should also work. If you set $$$x_i$$$ as the currently proven lower bound on the answer, the fugitive should pick $$$q_j$$$ to maximize $$$\min(d_{l, j} + (1-q_j)x_j)$$$. This must also converge as it's increasing, and the equations satisfied are the same (all true $$$q_j$$$ are nonzero as proved in the editorial).

C++20 is allowed, isn't it?

Have you read the tutorial? If you have and still have questions, ask again please.

Solution of K : First change even element to 0, and odd element to 1 When arr[i]=0, if this element adds in a subsequence, then previous two elements should be either (even,even) or (odd,odd) = (00) or (11) If arr[i]=1, the previous elements are (01) or (10) Also we maintain all such valid subsequences ending with 10 or 01 or 00 or 11 If arr[i]=0, this element can append in a subsequence ending with 1-> Just 0 -> result will be one extra 00 2-> Just 1 -> result will be one extra 10 3-> With 00 -> result will be one extra 00 4-> with 11 -> result will be one extra 10

If arr[i]=1, this element can append in a subsequence ending with: 1-> Just 0 -> result will be one extra 01 2-> Just 1 -> result will be one extra 11 3-> With 10 -> result will be one extra 01 4-> with 01 -> result will be one extra 11

void solve(){
  int n;
  cin>>n;
  vi arr(n);
  fori0n{
    cin>>arr[i];
    arr[i]%=2;
  }
  ll z=0;
  ll o=0;
  ll zo=0;
  ll oz=0;
  ll oo=0;
  ll zz=0;
  ll ans=0;
  fori0n{
   if(arr[i]==0){
    
    ans+=oo;
     ans=ans%mod;
    ans+=zz;
    ans=ans%mod;
    int t1=oo;
    int t2=oz;
    int t3=zo;
    int t4=zz;
    zz+=zz+z;
    oz+=o+oo;
    zz=zz%mod;
    oz=oz%mod;
    z++;
   }
   else{
    
    ans+=zo;
     ans=ans%mod;
    ans+=oz;
     ans=ans%mod;
    int t1=oo;
    int t2=oz;
    int t3=zo;
    int t4=zz;
    zo+=oz+z;
    oo+=t3+o;
    zo=zo%mod;
    oo=oo%mod;
    o++;

   }
  }
cout<<ans<<endl;

}

Thank you very much!