I think I misunderstood c

Problem C editorial is so nicely written..understood it clearly thanks:)

amazing round loved it

Just become expert again Amazing contest

What will be the expected difficulty for problem B it seems bit tough compared to other div 2 B Questions

Thanks for slow editorial!

Div2 D Alternate explanation:

Consider ?<??>?>??

Observation : Last > will be n and last < be 1

This is always true. If 1 and n are always in the permutation could there be a > after n and < after 1? No. If there aren't any such symbols for either > or < they will be in 1st position .

However will the subsequent >s after last > also be n-1,n-2,n-3? And will the subsequent <s after last < also be 2,3,4.....?

The answer is No.

This is because we have ?s after last > and last < respectively. There we could put values So that we could form a decreasing sequence from n ( > > >) and an increasing sequence from 1 (< < <). There could be many such sequences clearly.

Now let's propose an algorithm,

?<??>?>??

Starting from the back we have n-2 choices where n is number of els in the set. This is because only the minimum(1) and maximum(N) is fixed. Now remove last element.

?<??>?>? again n-2 choices where n is number of els in the set.

?>??>?>

1 choice last > is fixed. Similarly last < is fixed.

?>??>? now last > is the max el in the set. We remove 2 els and N so far. Irrespective of our choices for the 2 els, there will be 1 unique maximum in the set which will take place of last >. So for ? we have n-2 choices again where n is number of els in the set.

Hope you get the solution.

Thanks for the amazing editorial!

I don't understand why my solution for C didn't work. It passed the first test case fine, and was very similar to the expected output for the second testcase, so I was wondering where I went wrong.

Problem C. Decreasing String ***** In this problem test number 2 in test case 5. The string is given "pbdtm" and the POS=8 If I select s1=pbdtm s2=pbdm s3=bdm s4=bd s5=b The condition is still right. Because s1>s2>s3>s4>s5 And the POS value of 8 is 'd'.. But why this is wrong answer?

Problem B — Fear of the Dark

We can solve this problem using binary search as well.

Let's define a function f(w) which will return true or false for a particular radius w. True means for that particular w (w > 0), there is a path from point O to point P which is completely illuminated, and vice versa. If you observe the return of function by increasing the value of w gradually, you will notice this monotonic pattern [0 0 0...0 1... 1 1 1] where 0 means false and 1 means true. Here we can easily apply binary search to find the first 1.

Now how to write the function? Case 1: If both the points O and P lie inside any of the light of radius w, return true. Case 2: If both the circles intersect and the point o and point p lie inside any of the lights, return true, false otherwise.

Implementation (C++) 227374949

I'm still not getting one case. For which i didn’t able to solve the problem. Suppose the lanterns are so much far fron point o and p but they are closer to each other, i mean points a andb. But now if we take the distance between a and b and divide by 2, how is this can be answer. Because point o and p are not inside them, the are not covered. Can anyone explain?

Great idea for E, thanks a lot for the wonderful contest :)

You can also solve problem B by binary search. By the way, problem c editorial is great,thanks:).

come on

Nice editorial

Awesome Editorial and Problem set.

Can someone help me with understanding my solution to B more clearly? I tried using binary search by answer here. I felt it was a plausible solution since if a radius (say r) is an answer then all radiis > r are also the answer. I tried implementing some solution, didnt work, maybe my impl on binary searching for real answers suck. Help/Correction appreciated!

// checks if point is inside circle
bool check(pair<float, float> circle, pair<float, float> point, float w){
    return ((circle.first - point.first) * (circle.first - point.first) + 
    (circle.second - point.second) * (circle.second - point.second)) <= w * w;
}

//checks if circles A and B are touching
bool istouch(pair<double, double> a, pair<double, double> b, double w){
    return w + w >= ((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));
}


//checks if the radius is a valid answer
bool isok(pair<float, float> b, pair<float, float> p, pair<float, float> o, pair<float, float> a, float w){
    return (check(b,o,w) & check(b,p,w) | (check(a,o,w) & check(a,p,w))) | 
    (check(b,p,w) | check(a,p,w)) & (check(b,o,w) | check(a,o,w) & istouch(a,b,w));
}

double WORST = 3e3f;
double EPS = 1e-6f;

void solve(){
    pair<float, float> p, a, b, o;
    cin >> p.first >> p.second;
    cin >> a.first >> a.second;
    cin >> b.first >> b.second;

    o = make_pair(0.0f, 0.0f);

    double l = 0.0f, r = WORST;
    double w = r;

    //binary searching the answer starts from here
    while(r - l > EPS){
        double mid = (l + r)/2;
        if(isok(b,p,o,a,w)){
            w = mid;
            r = mid;
        } else {
            l = mid;
        }
        // cout << l << " " << r << "\n";
    }

    cout << w << "\n";

}

For problem E, I was able to squeeze in what I think is an $$$O(m \times 2^m \times \sqrt{n})$$$ solution that doesn't precompute the number of programmers needed to satisfy a project: 227729256

Not sure if this was intended to pass or not!

after contest is completed. now i can understand the editorial for Problem C. Does it happen to anyone? Am it the only one who face difficulty to understand just after the contest.

227807811

double sq(int x){
    return (double)x*x;
}

class pt{
    int x, y;
    public:
    pt(int x = 0, int y = 0): x(x), y(y){}
    double dist(pt p){ return sqrt(sq(x-p.x) + sq(y-p.y)); }
    void read(){ cin >> x >> y; }
    bool inside(pt c, int r){ return (*this).dist(c) <= r; }
};


void solve(){
    pt c, h, a, b;
    h.read(); a.read(); b.read();

    double w = min(c.dist(a), c.dist(b));
    double w2 = min(h.dist(a), h.dist(b));
    w = max(w, w2);

    bool f = c.inside(a, w) && h.inside(a, w);
    bool s = c.inside(b, w) && h.inside(b, w);

    if(!f && !s){
        w = max(w, a.dist(b)/2.0);
    }
    cout << fixed << setprecision(10) << w << "\n";
}

Could somebody tell me what is the case I am missing out in the code ?

my logic: first expand the circle(with minimum radius) until both the starting and ending point are in some circle(boundary).

check if both points lie in a single circle, if yes, we got the answer

if not, the points are in separate circles, we need to check if there is a need to make the circles touch, or it already is touching or overlapping.

Please help me in Problem C ,I am facing runtime error on testcase 8 . Below is my code :

include<bits/stdc++.h>

using namespace std;

void solve(string& str,long long pos){ if(pos<=str.size()){ cout<<str[pos-1]; return; }

// eg -> kabsi ,pos = 11

long long ct = 0;
long long size = str.size();
long long temp = str.size(); // x = 5
long long var = str.size()-1; // var = 4
while(temp<pos){
    temp += var;
    var--;
    ct++;
}
var ++; 
long long prefixSum = temp - var;


// ct refers to how many times str will be reduced 

stack<char> st;
st.push(str[0]);
long long count = 0, itr = 1;

while(count < ct && itr<str.size()){

    if(itr == str.size() - 1){
        if(st.top() <= str[itr]) {
            // ignore
            itr++;
            count++;
        }
        else{
            st.pop();
            if(st.empty()){
                st.push(str[itr++]);
            }
            count++;
        }
    }

    // right
    else if(st.top() == str[itr] && str[itr] == str[itr+1]){
        // teeno equal vala yahi nipat jayega
        st.push(str[itr++]);
    }   

    // right
    else if(st.top() <= str[itr] && str[itr] < str[itr+1]){
        st.push(str[itr++]);
    }

    // right
    else if(st.top() < str[itr] && str[itr] > str[itr+1]){
        // ignore
        itr++;
        count++;
    }

    // right
    else if(st.top() < str[itr] && str[itr] == str[itr+1]){
        // ignore
        st.push(str[itr++]);
    }

    // right
    else if(st.top() == str[itr] && str[itr] > str[itr+1]){
        // ignore
        itr++;
        count++;
    }

    // right
    else if(st.top() > str[itr]){
        st.pop();
        if(st.empty()){
            st.push(str[itr++]);
        }
        count++;
    }

}

string answer = "";
while(!st.empty()){
    char cha = st.top();
    st.pop();
    answer += cha;
}   

reverse(answer.begin(),answer.end());

for(long long k = itr ; k<str.size();k++){
    answer += str[k];
}

// cout<<answer<<" "<<count<<" "<<ct<<endl;


while(count < ct && !answer.empty()){
    answer.pop_back();
    count++;
}

// cout<<ct<<endl;
// cout<<answer<<endl;


long long newlen = size - ct;
// newlen is length of new string formed 
long long index = pos - prefixSum - 1; // did -1 to make 0 based indexing

cout<<answer[index];

}

int main(){ std::ios::sync_with_stdio(false);std::cin.tie(nullptr); long long n; cin>>n; while(n--){ string str; cin>>str; long long pos; cin>>pos; solve(str,pos); } }

For Problem F, the editorial states that when "when you move a camera of type 2 to the first block, it can force multiple cameras of type 3 into the second block". I'm unable to see why this is true.

It seems to me that from the way we pick the camera of type 3, after a single move, it will fix all the $$$x$$$ which have $$$d_x - x > 0$$$. Because after moving the camera of type 2 from block2 to block1, we might cause several indices to have $$$d_x - x = 1$$$ (and not any value higher than $$$1$$$), which can be fixed by a single camera move.

For 1886D - Monocarp and the Set, I have implemented the same logic as given in the editorial. We have to print the number of ways before and after the modification in the string, so first I calculated the number of ways to order the integers $$$1,2,3...n$$$. Then, while modifying the string, if we add a new $$$?$$$ in the string at index $$$i$$$, I am multiplying the previous number of ways with $$$i-1$$$. If we remove a $$$?$$$ from the string, there are two cases if the index is $$$1$$$ or not. If the index is $$$1$$$, then I am calculating the number of ways as I calculated in the beginning and if the index is not $$$1$$$, then I am just dividing the previous number of ways by $$$i-1$$$. This gives me the correct answer for test cases$1$ and $$$2$$$, but the code is failing for the $$$3$$$^rd test case.

Could anyone look at my code 228305867 to point out the issue?

In F why "if we skipped some camera which could be inserted into the first block, and chose some other camera for the same slot, they can be "swapped". " is right?

I think if we first insert the camera which $$$s_i$$$ is small and then insert the camera which $$$s_i$$$ is big,for the second block it is greater,but for the first block it is not greater than we first insert the bigger one.

BledDest

Can anyone help me to find why is it wrong in th case 16 of the problem E: https://codeforces.com/contest/1886/submission/228496275

Hi, can anyone explain for D, (TestCase 1, before all queries.)why the permutation 2, 1, 3, 5, 4, 6 is not possible ?

Maybe I am missing something, but the sequence is <?>?>

For C, I did an answer using the quadratic equation that avoids data structures, but it has a runtime error on test 8, don't know why :(

/* solve.cpp
 * solution to problem X
 */

#include <bits/stdc++.h>
#include <iostream>
using namespace std;

int solver(string s, long long pos) {
  long long L = s.length();
  // quadratic equation to find length of x.

  // x - the length of the substring of the solution.
  long long x = floor((1 + sqrt(1 + 4 * (pow(L, 2) + L - 2 * pos))) / 2);

  // xb - the index of the beginning of substring x
  long long xb = (pow(L, 2) + L - pow(x, 2) + x) / 2 - x;
  // xi - the index in the substring x of the solution.
  long long xi = pos - 1 - xb;
  // cout << "*** x: " << x << " xi : " << xi << "\n";

  long long i = 0;
  long long erased = 0;
  while (L - erased > x) {
    // what to do before getting to the end of the string
    if (i + 1 <= L - erased) {
      char curr = s[i];
      char next = s[i + 1];
      if (curr > next) {
        s.erase(i, 1);
        erased++;
        if (i > 0)
          i--;
      } else {
        i++;
      }
    }
    // at the end of the string
    else {
      s.erase(i, 1);
      erased++;
      i--;
    }
  }

  // Print result.
  cout << s[xi];
  return 0;
}

int main() {
  int numTests;
  cin >> numTests;
  while (numTests--) {
    string s;
    int pos;
    cin >> s >> pos;
    solver(s, pos);
  }
  return 0;
}

for question C you should put a hint (use a stack) as only knowing this information made me solve it

overall, good question and perfect tutorial thanks

In problem $$$C$$$, I was wondering what if we had some $$$Q$$$ queries, where each query is asking the character at queried position and length of string as ($$$N < 10^6$$$).

Any ideas on how we will go about it, like what information do we need to store ?
Or should the constraints be reduced ?
Like any approach for this so called Bonus problem ?

Roms

Another approach for problem A which is more concise 248334395