Thanks for the editorial, the randomized solution to G is quite interesting.

I think there also should be tag graphs in the problem 1418C - Mortal Kombat Tower cause I solved it with Dijkstra's algorithm.

I think it is not right that the model solution for D heavily relies on datastructures available in a relatively small subset of available languages, even though one of them is c++

Can someone explain the segment tree solution of G . what i didn't understand is that valid regions depend upon the choice of right border and also on the number under consideration for eg. for the array 1 2 3 3 2 5 4 4 2 3 4 3 if we fix the right border at last index and took the number 4 under consideration then the valid/invalid regions will look like 0 0 0 0 0 0 0 1 1 1 1 0 . But these regions will change if we change the right border or the number under consideration . so there are total n*n such arrays . How can we keep track of them all with segment tree . Do we require multiple segment tree or one will suffice .

Such a clever and interesting approach for the problem E. I am interested to know if someone is able to solve it by going the usual way of (sum of damages for each perm / n! )

G and F should be swapped

Can someone give me links for more problems similar to G in which I can use string hashing but not of strings directly?

Hey awoo can you tell me more about the thinking process of G. Like how did you arrive at the conclusion that we can use numbers in base 3?

Hey awoo, In the post of Unofficial Editorial, I wonder whether problem D has an easier solution if we can only move one pile at a time.

I think the solution aniervs posts is right, but I wonder whether you have other clever solotuion?

Hi awoo and adedalic . The way we have pushed the divisors into the set for all the values from ceil(l/x1) + 1 to floor(r/x1) in the way mentioned in the editorial solution is not clear ? Like as i understand that why we can't directly pushed all the divisors of all the numbers in the range with simple for loop of divisors of all the valid numbers of the segments . And also in the method of the solution we are also not clearing the set for further iterations of x1 is very complex to comprehend . Thanks for reading the comment and I will be grateful if you will explain .

Can anyone help me identify what's wrong in my approach in C :

dp[i][0] //denotes min coins spent if I kill the last boss 
dp[i][1] // denotes min coins spent if my friend kill the last boss .

int ans(int i ,int j){
        if(i<0)
            return 1e9 + 7 ; 

        if(i==0)
        {
                return a[i]; // since my friend's turn is the first one 
        }
        if(i==1)
        {
            if(j==0)
                return min(ans(0,0),ans(0,1)) ; 
            else
                return  a[i] + min(ans(0,0), ans(0,1));
        }

        int& res = dp[i][j] ; 
        if(res!=-1)
            return res ; 
        if(j==0)
            res = min(ans(i-1,1) , ans(i-2,1)) ; 
        else if(j==1)
            res = min(ans(i-1,0) + a[i], ans(i-1,0) + a[i-1] + a[i]) ; 
        return res ; 
    }

here's my submission : 92930622

Edit Request awoo

I think in problem E tutorial, you mistakenly replaced all $$$a_j$$$ for $$$b_j$$$ in every $$$max(K - a_j, 0)$$$ expression.

I've implemented the same code and it gives correct answer on my machine but it shows WA on Test Case 1. 92970290. I don't understand why this is happening.

For G you would be better off using xor instead of sum. For each value generate two random integers x and y, and cyclically put x, y, x xor y in places with this value, the hash will be prefix xor.

**any one can help out why i am getting tle on Problem D and tc 52? i am using treemap and treeset **

public class D {

static TreeMap<Integer, Integer> tm;
static TreeSet<Integer> ts;
static int mod = (int) 1e9 + 7;

static int ar[];

// static Scanner sc = new Scanner(System.in); static StringBuilder out = new StringBuilder();

static HashSet<Integer> gr[];
int n;

static class pair implements Comparable<pair> {

    int f;
    int s;

    public pair(int a, int b) {
       f = a;
       s = b;
    }

    @Override
    public int compareTo(pair o) {
       // TODO Auto-generated method stub
       if (this.s == o.s)
         return o.f - this.f;
       return this.s - o.s;
    }

}

static int[] dp;

public static void main(String[] args) throws IOException {
    // TODO Auto-generated method stub

    int tc =1;// sc.nextInt();
    while (tc-- > 0) {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int q = Integer.parseInt(st.nextToken());

       int ar[] = new int[n];
        tm = new TreeMap<>();

        ts = new TreeSet<>();


        st = new StringTokenizer(br.readLine());
       for (int i = 0; i < n; i++) {
         ar[i] = Integer.parseInt(st.nextToken());
         ts.add(ar[i]);
       }

       Arrays.sort(ar);


       for (int i = 0; i < n - 1; i++) {

         int dif = ar[i + 1] - ar[i];

         tm.put(dif, tm.getOrDefault(dif, 0) + 1);


       }




       if(ts.size()<=2)out.append(0+"\n");
       else{

         out.append(ts.last() - ts.first() - tm.lastKey() + "\n");
       }


       while (q-- > 0) {

         st = new StringTokenizer(br.readLine());
            int t1 = Integer.parseInt(st.nextToken());
            int x1 = Integer.parseInt(st.nextToken());



         int ceil=x1;
         int floor=x1;
         if (t1 == 0) {


          if(ts.ceiling(x1+1)!=null){


               ceil=ts.ceiling(x1+1);

               tm.put(ceil-x1, tm.get(ceil-x1)-1);
               if(tm.get(ceil-x1)==0)tm.remove(ceil-x1);


          }
          if(ts.floor(x1-1)!=null){
              floor=ts.floor(x1-1);
               tm.put(x1-floor, tm.get(x1-floor)-1);
               if(tm.get(x1-floor)==0)tm.remove(x1-floor);
          }

          if(floor!=x1 && ceil!=x1){

              tm.put(ceil-floor, tm.getOrDefault(ceil-floor, 0)+1);
          }

          ts.remove(x1);


          if(ts.size()<=2){
              out.append(0+"\n");

          }
          else{
              out.append(ts.last()-ts.first()-tm.lastKey()+"\n");
          }


         } else {



          if(ts.ceiling(x1)!=null){

              ceil=ts.ceiling(x1);

              tm.put(ceil-x1, tm.getOrDefault(ceil-x1, 0)+1);


          }

          if(ts.floor(x1)!=null){

              floor=ts.floor(x1);
              tm.put(x1-floor, tm.getOrDefault(x1-floor, 0)+1);
          }

          if(ceil!=x1 && floor!=x1){

              tm.put(ceil-floor, tm.get(ceil-floor)-1);
              if(tm.get(ceil-floor)==0)tm.remove(ceil-floor);
          }

          ts.add(x1);
          if(ts.size()<=2){
              out.append(0+"\n");

          }
          else{

              out.append(ts.last()-ts.first()-tm.lastKey()+"\n");
          }

         }
       }

       br.close();

    }

    System.out.println(out);

}

i am getting runtime error in solution for problem c. can somebody help. https://mirror.codeforces.com/contest/1418/submission/92995605

I had read the problem 1418B - Negative Prefixes for more than 40 min and after that I had read the solution but I wasn't able to understand these lines in block ,can any one help , I think it says we need to find array so that it prefix sum array should be like starting from negative elements and once the positive element came then there should be no negative elements(all elements after that are positive) like eg [−8,−14,−13,−9,−5,2,0] and as given in solution and k is 5 , and we need to reduce the k some and propose a solution ,but that was not the case

Let k be the maximum j (1≤j≤n) such that pj <0. If there are no j such that pj<0, then k=0.

Your goal is to rearrange the values in such a way that k is minimum possible.

thanks in advance

A solution for F without any data structures, just simple math (although with many steps and cases):

For easier reading, let's rename $$$(x_1,y_1,x_2,y_2)$$$ to $$$x,a,b,c$$$, so we need to find three numbers $$$a,b,c$$$ such that $$$xa=bc \in [l,r]; a,c \in [1,m]; b \in [x+1,n]$$$. In fact, we can drop the constraint on $$$c$$$, it follows from the others.

So far, we have fixed a value of $$$x$$$. Now let's fix the greatest common divisor $$$g$$$ of $$$b,x$$$. There can only be a total of $$$n \log n$$$ such divisors across all values of $$$x$$$. The idea is to quickly find a solution given $$$g,x$$$ if it exists. We know that $$$b>x$$$ and since $$$g$$$ is their common divisor, we can write $$$b=x+yg$$$ for some $$$y>0$$$. The constraint on $$$b$$$ becomes $$$y\leq \frac{n-x}{g}$$$. Also, since $$$b$$$ divides $$$ax$$$, we have that $$$b/g$$$ divides $$$a(x/g)$$$ and so, since $$$b/g$$$ and $$$x/g$$$ are coprime, $$$b/g$$$ divides $$$a$$$, and so $$$a=(b/g)z=(x/g+y)z$$$ for some $$$z$$$.

Let's handle two cases:

1) $$$g > \sqrt{x}$$$. In this case there can be at most $$$x/g < \sqrt x$$$ different values of $$$y$$$ and we can try each. For a fixed $$$y$$$, we check whether $$$b$$$ fits the constraints and whether we can find $$$z$$$ such that $$$a$$$ also fits the constraints.

2) $$$g \leq \sqrt{x}$$$. We try each value of $$$z$$$ as long as $$$a$$$ is less than $$$m$$$. In fact, from $$$a=(x/g+y)z$$$ and $$$y>0$$$ we have $$$z \leq \frac{m}{x/g+1}$$$. After fixing $$$z$$$, we look for $$$y$$$ to fulfil the linear constraints given above (a couple of integer divisions and min/max).

Overall, the sum of small divisors (less than $$$\sqrt{x}$$$ for all numbers $$$x$$$ up to $$$n$$$ is asymptotically $$$O(n \sqrt n)$$$, and the sum of all values $$$\frac{1}{x/g+1}$$$ for all small divisors is asymptotically equal to $$$O(\sqrt n)$$$, so the overall complexity is $$$(n+m)\sqrt{n}$$$.

How to compute the probability of collision in problem G? Would some love to elaborate why it is the same as two vectors (out of n) colliding in a K-dimensional space with their coordinates being from 0 to 2? I will appreciate it a lot.

Your code here...
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
void solve()
{
    lli m = 1000000007;
    lli t;cin>>t;
    while(t--)
    {
        lli n;cin>>n;
        lli A[n];
        FOR(i,0,n-1)
        {
            cin>>A[i];
        }
        lli i=0,s=0;
        lli f=1;
        while(i<n)
        {
            if(f)
            {
                s+=(A[i]==1);
                i++;
                if(i<n&&A[i]==0)
                   i++;
                f=0;
            }
            else 
            {
                i++;
                if(i<n&&A[i]==1)
                  i++;
                f=1;
            }
        }
        cout<<s<<"\n";
    }

}
int main()
{
    solve();
}

Can anyone tell what's wrong in the code?

problem C have DP solution

solution