For the second paragraph of 1E (Vabank), can someone explain what exactly the queries are, and what is the analysis for why this results in $$$2 \log (10^{14})$$$ queries? I don't quite understand from the description in the editorial.

EDIT: I think this makes sense now. Start with $$$L$$$ money, and try $$$L$$$ then $$$L + \frac{R-L}{2}$$$ each time. If $$$L + \frac{R - L}{2}$$$ is too large, then this process will decrease the amount of money by $$$\frac{R-L}{2}$$$. $$$\frac{R-L}{2}$$$ vanishes quickly (i.e. halves at each step), so the balance will never become negative.

In problem D, can anyone explain how to decide the number of times to perform iterations.?

Help needed in task B Can someone please tell,why m would be arbitarily large if we have no positive difference.

Not author solutions, but fun solution D, E:

Solution D: Let's do a Dijkstra on the moments of deletion. It is clear that a song is deleted later if it has a larger deletion circle number, or if its ancestor is equal, about which it is deleted less. So let's do Dijkstra on these parameters. The first round is a simple simulation, and then you just need to maintain the next active song, which is easily done by a two-linked list. As a result, we take out, check that these songs have not been deleted yet, if we have not deleted them, then add them to Dijkstra, delete the next song, and see if the gcd with the new song is equal to one, and if so, add increasing the circle by 1. As a result, the asymptotic $$$O (n \cdot (log(n) + log (c))$$$.

Code: https://pastebin.com/n2Sx49fW

Solution E: Let's look at the element with the minimum height in the array, and look at the 2 segments into which it divides the array. Note that we must take the beauty of this element in the answer, and that the two segments into which the array is divided are independent, so we can solve the answer for them independently. The only difference from the original problem is that we can remove the array suffix / prefix for free.

Then we implement the recursive function $$$solve (l, r, t1, t2)$$$, where $$$t1/t2$$$ — can we remove the prefix/suffix for free. Well, you can immediately see the exit condition, if $$$r < l$$$, then the answer is $$$0$$$, because there are simply no elements

Let $$$pos$$$ be the position of the minimum on the segment $$$(l, r)$$$, $$$res1 = solve(l, pos-1, t1, 1)$$$. $$$res2 = solve(pos + 1, 1, t1)$$$. Also, if $$$t1 = 1$$$ or $$$t2 = 1$$$, then we can say that the answer is at least 0 (because we can just take the entire array for free). If $$$t1 = 1$$$, then we can not take $$$res1 + b[pos]$$$ (since this is a prefix). If $$$t2 = 1$$$, then you can also not take $$$res2 + b[pos]$$$ in the response (since this is a prefix). The answer can also be $$$res1 + res2 + b[pos]$$$. Well, these transitions are enough, because if we took $$$b[pos]$$$ in the answer, then the problem is divided into 2 smaller ones, and we solve them correctly, and if we did not take this element, then we did not take $$$res1$$$ or $$$res2$$$, which is case considered. As a result, each time we find the minimum element, and we divide the problem into 2 smaller ones, and it is not difficult to show that the complexity of this solution is $$$O(n \cdot log(n)$$$, since after each transition, one element becomes less, and one search query is made for $$$log$$$ (you can do it for a line, but you need to think)

Code: https://pastebin.com/5H8TnGq5

Is there any dp arroach in C ?

In problem D editorial, It is easy to find it using the bad pairs set. How exactly?

Simple circular linked list solution for Div2 D can be optimised to O(N).

110871644

AT the time of deletion just manage deletion in a circular linked list plain algorithm one use of set can also be transformed to queue with just a few changes.

For problem statement B , for input: 3 7 3 4 why (5 1) is W/A?

Problem G very nice and interesting! Below is my explanation of the editorial.

The first part of solution is trivial. Let's discuss the second part. The first solution in my mind is binary search, but it costs too much queries.

The editorial uses a different idea, which is similar to a famous problem: "egg dropping problem". The idea is:

• If you performed successful try($$$X \le M$$$), you will get one more "chance" to try without the risk of getting fired;
• If you failed($$$X > M$$$), you will lose one chance.

Although it's a rough estimate, it seems that you can perform a few more "safe" queries to cover the extra cost.(A very informal proof: after each query, the $$$\Delta$$$ of "extra cost" drops very fast, so the sum of it will not too large.)

So let's define the $$$size$$$ of a problem is $$$R - L + 1$$$; define $$$dp[x][y]$$$ is the maximum $$$size$$$ of problem we can solve using $$$x$$$ queries and have $$$y$$$ "chances" initially. Using the idea above, it's not hard to find that $$$dp[x][y] = dp[x-1][y-1] + dp[x-1][y+1] + 1$$$, which is similar to "egg drop" problem. The initial state of dp is: $$$dp[0][...] = 0$$$.

We will find that $$$dp[49][0] \approx 6 \cdot 10^{13} > 10^{14} - 2^{46}$$$, so it's enough. So we can use up to $$$47 + 49 + x= 96 + x$$$ queries to guess the right $$$M$$$, where $$$x$$$ is the number extra queries to cover "extra cost". It seems that $$$x \le 2$$$ for the test data of problem G, my solution(110886240) uses max $$$98$$$ queries.

Here is my code for question-C, i don't know what's wrong here, like my code is not passing pretest-2(giving correct answer for first few testcases,wrong for some and then again correct for rest). But when i tried running those testcases individually, all of them are giving correct answers. idk howz that even possible since i've not used any global variable. Can someone help me with this please?

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,m;
        cin>>n>>m;
       int x=m;
       int limit=ceil(m/2.0);
       bool ans=false;
       vector<int> a(n+1,0);
       vector<int> frnd;
       while(x--)
       {
           int avbl;
           cin>>avbl;
           int arr[avbl+1];
           for(int i=1;i<=avbl;i++)
           {
             cin>>arr[i];  
           }
           for(int i=1;i<=avbl;i++)
           {
               if(a[arr[i]]+1<=limit)
              { a[arr[i]]++;
                  ans=true;
              frnd.push_back(arr[i]);
              break;
              }
           }
           if(ans && x>0)
           ans=false;
            else
            break;
       }
       if(ans)
       {
           cout<<"YES"<<endl;
           for(int i=0;i<frnd.size();i++)
           {
               cout<<frnd[i]<<" ";
           }
           cout<<endl;
       }
       else
       {
           cout<<"NO"<<endl;
       }
     }
 return 0;
}

Thanks for the clear editorial(but a little slower), the contest is really good in general, I really enjoy it!:-)

Hope there will be more nice contests like this one on Codeforces.

My solution in E( almost the same as the author's)

For each height — h [i] we will find the leftmost (left [i]) and right border (right [i]) so that min[left [i], i] = h[i] = min[i, right [i]]. OK . this is understood how to do it. one of the ways is this binsearch + sparse table (finding min segment in O(1)).

Next, we will use dynamic programming on a tree of segments. in begin all dp equal to -1e18. dp[1] = b[1], then we can update all dp on the segment from 1 to right[1] because the minimum on this segment is h[1]. Go ahead, to calculate dp [i] — we know that on the segment from left [i] to i, the minimum is h [i], that is, no matter how you choose the last subsegment, min will be H [i]. i.e. dp [i] = max (dp [i], get_max (1, n, 1, lef [i] — 1, i — 1) + b [i]) and do not forget to update all dp from i to right [i] — (j = i, i + 1, right[i]) dp [j] = max (dp [j], dp [i]); this one can be done with a lazy push

Final asymptotics O (nlogn) My code for more information: 110848133

Heh, I feel like problem E from ARC 115 (contest that took place ~2 hours before this one) is very similar to problem E here.

I used an even simpler approach to C. Do two passes through the data. On the first pass only look at those days where there is only one friend available, and choose that friend, counting the number of times each friend has been chosen. If any friend is chosen more than $$$\left\lceil \frac{m}{2}\right\rceil $$$ times then there is no solution. Otherwise, do a second pass through the remaining days, still keeping count, and choosing the first available friend who hasn't been chosen $$$\left\lceil \frac{m}{2}\right\rceil $$$ times.

This will always give a solution since at most one friend can have been chosen $$$\left\lceil \frac{m}{2}\right\rceil $$$ times.

My code is here.

Another way to look at the solution of F: It's somewhat obvious that you're going to do Floyd-Warshall. However, after looking at the problem a bit, one can "spot some similarities" between the first and the second part of the input, with the difference being, that in the second part of the input, the values you are given are values over the paths, whereas in the first part, these are values over edges. With Floyd-Warshall, we can calculate the "first values" over paths aka distances, so why shouldn't we try to apply some sort of a "reversed Floyd-Warshall" on the "second values"? The loop you get is over $$$i, j, k$$$ to set $$$snd[i][j] = max(snd[i][j], snd[i][k] - dist[j][k])$$$. The only problem left is, at least I wasn't sure in which order to loop over $$$i, j, k$$$. I experimented a bit with the order and repeated the procedure three times (because why should this not work?). Then, since we have the "second values" over the edges, we can just compare them with the edge lengths.

I just found the aspect of "reversing Floyd-Warshall" too intriguing not to share it. Also, the code is quite short.

Otherwise the modulo has to equal their sum c+(m−c)=m what does it mean ? may any one help me. (c+m-c=m but how can we find modulo by this ?)

Wow, I just realized that Gustaw can choose $$$X$$$ greater than the number of euros he currently has in D1E ...

It's amazing that 1C and ARC115 E (just about 2 hours before this contest) need similar tricks to improve DP. I suggest those who are trying to solve 1C solve both of them together since I tried ARC115 E and felt it great for my DP skill. :)

For Problem C, I try to maintain a struct as (value, las).

The 'las' means the friend where it was last seen. And I think it can provides a ability to undo the previous operation (when it more than $$$\lceil \frac{m}{2} \rceil$$$). Through continuous withdrawal operations, I think if it has vaild case, it can be found.

But I wrong answer on test 4. I can't find the hack data, here is my code: Code.

My English is not good...very sorry...

in div2F/div1D...

can anyone explain these lines in details ( mentioned in editorial )

"It can be done using Dijkstra in O(n^2) if we initialize the distance to all ui with -li. After we are done for all vertices v, there only remains to check for each edge whether it has been marked useful for any vertex v."

how to solve problem C with flows(this is in tag)?? Who solved C with flow ... pls .. can you pls explain how did you solve ??

Please update problem ratings.

Let $$$dp[x][y]$$$ equal the maximal $$$d$$$ so that it's possible to find the answer on $$$[l,l+d]$$$ having $$$y⋅l+d$$$ money initially. One can show that $$$dp[k][0] = \binom{k}{[k/2]}$$$. It implies that $$$k≤49$$$. This adds up to 97 queries.

Can someone please explain this in more detail? Thank you!

KAN

In problem C's editorial, it is written that:

There is only one case when this is not possible: if f is the only friend who can play in more than ceil(m/2) days

How can we prove this?

For problem C, you could also have sets of friends that are available at each day, sort by the days with fewest people, then greedily pick any friend that isn't at the cap yet, increasing someones frequency when picked.

I had a little trouble convincing myself that it should work tho, did someone else do it this way?

For the last problem, I submitted something that's quite obviously at least O(number of all pairs satisfying just the first two conditions). It passed easily. Is there a clear general small upper bound on this number?

In problem E-Skyline Photo Can someone explain why I'm getting WA in test case 7?

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int N=3e5+5;
const ll INF=1ll<<60;
int n;
ll t[4*N], st[4*N];
 
void assign(int i, ll x, int u=1, int s=0, int e=n-1){
 if(s>i or e<i)  return ;
 if(s==e){
   t[u]=x;
   return ;
 }
 int v=2*u, w=2*u+1, m=(s+e)/2;
 assign(i,x,v,s,m);
 assign(i,x,w,m+1,e);
 t[u] = max(t[v],t[w]);
}
 
ll rmx(int l, int r, int u=1, int s=0, int e=n-1){
 if(l>e or r<s)  return -INF;
 if(l<=s and e<=r) return t[u];
 int v=2*u, w=2*u+1, m=(s+e)/2;
 return max(rmx(l,r,v,s,m),rmx(l,r,w,m+1,e));
}

void make_greater(int l, int r, ll x, int u=1, int s=0, int e=n-1){
 assert(x!=-INF);
 if(l>e or r<s) return ;
 if(l<=s and e<=r){
   st[u] = max(st[u], x);
   return ;
 }
 int v=2*u, w=2*u+1, m=(s+e)/2;
 if(st[u]!=-INF){
   st[v] = max(st[v], st[u]);
   st[w] = max(st[w], st[u]);
   st[u]=-INF;
 }
 make_greater(l,r,x,v,s,m);
 make_greater(l,r,x,w,m+1,e);
}
 
ll at(int i, int u=1, int s=0, int e=n-1){
 if(s==e)  return st[u];
 int v=2*u, w=2*u+1, m=(s+e)/2;
 if(st[u]!=-INF){
   st[v] = max(st[v], st[u]);
   st[w] = max(st[w], st[u]);
   st[u]=-INF;
 }
 if(i<=m)  return at(i,v,s,m);
 else  return at(i,w,m+1,e);
}

vector<int> nearest_min_in_left(vector<int> a) {
  int n = a.size();
  vector<int> ret(n);
  memset(t, 0, sizeof(t));
  for (int i = 0; i < n; ++i){
    ret[i] = rmx(0, a[i]);
    assign(a[i], i+1);
  }
  return ret;
}


int main(){
  ios::sync_with_stdio(0), cin.tie(0);
  
  cin >> n;
  vector<int> h(n);
  for (int i = 0; i < n; ++i){
    cin >> h[i];  h[i]--;
  }
  vector<ll> b(n);
  for (int i = 0; i < n; ++i){
    cin >> b[i];
  }
  vector<int> l = nearest_min_in_left(h);
  reverse(h.begin(), h.end());
  vector<int> r = nearest_min_in_left(h);
  reverse(h.begin(), h.end());
  for (int i = 0; i < n/2; ++i){
    swap(r[i], r[n-1-i]);
  }
  for (int i = 0; i < n; ++i){
    r[i] = n-1-r[i];
  }

  memset(t, 0, sizeof(t));
  for (int i = 0; i < 3*N; ++i){
    st[i] = -INF;
  }

  make_greater(0, r[0], b[0]);
  assign(0, b[0]);
  for (int i = 1; i < n; ++i){
    ll dp_mx = rmx(max(0, l[i]-1), i-1);
    if (l[i]==0)  dp_mx = max(dp_mx, 0ll);
    make_greater(i, r[i], dp_mx+b[i]);
    assign(i, at(i));
  }

  cout << at(n-1) << "\n";
  
  return 0;
}

[user:KAN] How to do problem D using dsu?

problem H can also be solved by suffix array.

like this

can someone tell what is wrong in my submission 283135877