awoo's blog

By awoo, history, 6 months ago, translation, In English

1886A - Sum of Three

Idea: fcspartakm

Tutorial
Solution (fcspartakm)

1886B - Fear of the Dark

Idea: BledDest

Tutorial
Solution (Neon)

1886C - Decreasing String

Idea: Roms

Tutorial
Solution (Roms)

1886D - Monocarp and the Set

Idea: Roms

Tutorial
Solution (Roms)

1886E - I Wanna be the Team Leader

Idea: BledDest

Tutorial
Solution (awoo)

1886F - Diamond Theft

Idea: BledDest

Tutorial
Solution (Neon)
  • Vote: I like it
  • +25
  • Vote: I do not like it

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think I misunderstood c

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it +3 Vote: I do not like it

amazing round loved it

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Just become expert again Amazing contest

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No it is pretty balanced. You need to know basic geometry and/or binary search

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      definitely not basic geometry, you should have good practise of it atleast

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I thought of using binary search at first, on w but w is floating point number. so how can we apply binary search on it can you please elaborate.

»
6 months ago, # |
  Vote: I like it -37 Vote: I do not like it

Thanks for slow editorial!

»
6 months ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it

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.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    "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."

    I made this wrong assumption and was wondering why my solution is wrong! Thanks for this. I never would have realised why my solution is wrong( This happens a lot to me, I make wrong assumptions and get to a wrong solution but I never find that wrong assumption on my own, and usually some other person points it out for me. I need to work on this by embracing the Sherlock's quote : "When you have eliminated the impossible, whatever remains, however improbable, must be the truth"

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you for breaking my false assumption.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the amazing editorial!

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The fifth character is different.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    $$$s_2 = \tt{bdtm}$$$, not $$$\tt{pbdm}$$$

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i'm having same problem just wondering why ( s1= pbdtm -> s2 = pbdm )is not valid ???

      • »
        »
        »
        »
        6 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        The problem statement says that we always need to make the next string lexicographically minimal.

        From $$$\tt{pbdtm}$$$ we could go to $$$\tt{pbdt}$$$, $$$\tt{pbdm}$$$, $$$\tt{pbtm}$$$, $$$\tt{pdtm}$$$ or $$$\tt{bdtm}$$$. The lexicographically smallest one of these is $$$\tt{bdtm}$$$.

        We cannot go to $$$\tt{pbdm}$$$, since $$$\tt{bdtm}$$$ is lexicographically smaller.

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          Got it ! , thanks man

        • »
          »
          »
          »
          »
          6 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks you so much.. actually I misunderstood the problem statement

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
6 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I tried to solve it using binary search 247760061, but getting a TLE though. can someone please help me figure out why?

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Change while to for(int i=1;i<=200;i++) and set high to 1e9 and you'll pass this question!

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks. It worked 248056414.

        So, was that because there will be so many real values between the extremes?

        And we are can get to an approximate value in < 200 iterations?

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I think it's possible that the way your code is written could have some precision issues causing it to get stuck in a dead loop. In fact, we would halve the search each time, and even 100 searches would be enough to achieve the precision needed for the question.

          (I'm sorry my English is not good, the above is the result of using a translator, I hope you can read it:)

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

come on

»
6 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Nice editorial

»
6 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Awesome Editorial and Problem set.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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";

}
  • »
    »
    6 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    In theory binary search should be possible here, even if I don't think it makes the problem easier to solve than the direct solution.

    Problem 1: istouch() is wrong. You need to square the distance at the left-hand side (as you do in check()), or take the square root of the righthand side (hypot() is useful here).

    Problem 2: isok() is wrong. You need to check four possible paths: O->A->P, O->B->P, O->A->B->P, and O->B->A->P. The first two subexpressions (check(a,o,w) & check(a,p,w) and check(b,o,w) & check(b,p,w)) cover the first two possibilities. The third expression doesn't really work. instead of check(b,p,w) | check(a,p,w)) & (check(b,o,w) | check(a,o,w) & istouch(a,b,w) you need something like (check(b,p,w) | check(a,p,w)) & (check(b,o,w) | check(a,o,w)) & istouch(a,b,w) (note the different places of the parentheses!)

    (Also, generally don't use & and | for Boolean logic. Use the proper Boolean operators && and || instead. But that's not causing any bugs in this case.)

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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); } }

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    6 months ago, # ^ |
    Rev. 4   Vote: I like it +12 Vote: I do not like it

    Good question, it was one of our main points of concern while designing the solution (we weren't sure if it is necessarily to change the positions of multiple cameras of type $$$3$$$). This is because, when you move a camera of type $$$2$$$, it increases $$$d_x$$$ by $$$1$$$ on some suffix of values. But when you "move" a camera of type $$$3$$$, it actually stays in the first block (we still have to hack it before stealing the first diamond). It just has a bigger range of possible positions. So, it decreases $$$d_x$$$ on some suffix, but increases $$$d_x$$$ back on some shorter suffix (i. e. it just decreases $$$d_x$$$ by $$$1$$$ on one subsegment, not on the whole suffix). If there are multiple points where $$$d_x - x$$$ became positive after we moved a camera of type $$$2$$$, some of them might be outside that affected segment.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
6 months ago, # |
  Vote: I like it +6 Vote: I do not like it

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

  • »
    »
    6 months ago, # ^ |
    Rev. 3   Vote: I like it +20 Vote: I do not like it

    Suppose we already placed cameras of type $$$1$$$ and $$$2$$$, and try to place cameras of type $$$3$$$. Why is it always optimal to do it in non-descending order of $$$s_i$$$, and place a camera only in the first block (instead of placing it in both) whenever possible?

    Suppose we fixed an optimal placement of cameras, and it differs from the one produced by that greedy algorithm. Let's fix the first (in sorted order) camera $$$i$$$ that would be placed in the first block by the greedy algorithm, but is not placed there by the optimal solution.

    There should be a moment of time (some $$$x$$$ seconds before stealing the first diamond) where we would place that camera $$$i$$$ in the first block in the greedy solution. So, the condition $$$s_i \ge x + len$$$ must hold. If there's no camera of type $$$3$$$ occupying that moment, then we just place that camera $$$i$$$ there and remove it from the second block.

    If there is such a camera, suppose its index is $$$j$$$. We can show that if we place the camera $$$j$$$ in both blocks, and the camera $$$i$$$ in the first block only, nothing will break: we can place the $$$j$$$-th camera in both moments of time occupied by the $$$i$$$-th camera, and the $$$i$$$-th camera in the slot of the $$$j$$$-th camera:

    • since $$$s_j \ge s_i$$$, the position for the $$$i$$$-th camera in the first block is suitable for the $$$j$$$-th camera;
    • since $$$s_j \ge s_i$$$, the position for the $$$i$$$-th camera in the second block is suitable for the $$$j$$$-th camera;
    • $$$s_i \ge s_j$$$ does not necessarily hold, so it might be possible that the slot occupied by the $$$j$$$-th camera is unsuitable for the $$$i$$$-th camera. But remember that the greedy algorithm would place the $$$i$$$-th camera in the time slot occupied by the $$$j$$$-th camera, so the condition $$$s_i \ge len + x$$$ holds. So, that slot is suitable for the $$$i$$$-th camera.

    By repeating this process enough times, we can transform the optimal solution to the solution produced by the greedy approach, and nothing breaks.

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Obviously, the programmers that you finally choose are the biggest ones, so you should sort them decreasingly instead of increasingly before DP. Otherwise it means that you assumed choosing the smallest one, making it not optimal sometimes.

  • »
    »
    6 months ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    e.g.

    2 1

    1 3

    3

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 <?>?>

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    when you add 3, it becomes maximum so it shouldn't be a question mark, but rather a '>'

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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;
}
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Another approach for problem A which is more concise 248334395