### awoo's blog

By awoo, history, 10 months ago, translation,

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)
• +25

 » 10 months ago, # |   0 I think I misunderstood c
 » 10 months ago, # |   0 Problem C editorial is so nicely written..understood it clearly thanks:)
•  » » 10 months ago, # ^ |   0 true
 » 10 months ago, # |   +3 amazing round loved it
 » 10 months ago, # |   0 Just become expert again Amazing contest
•  » » 10 months ago, # ^ | ← Rev. 2 →   -13 basiji good for you i hope goods
•  » » » 10 months ago, # ^ |   0 oh my god is he basiji ?
•  » » » » 10 months ago, # ^ |   0 yes
 » 10 months ago, # |   0 What will be the expected difficulty for problem B it seems bit tough compared to other div 2 B Questions
•  » » 10 months ago, # ^ |   0 No it is pretty balanced. You need to know basic geometry and/or binary search
•  » » » 10 months ago, # ^ |   0 definitely not basic geometry, you should have good practise of it atleast
•  » » » 6 months ago, # ^ |   0 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.
 » 10 months ago, # |   -37 Thanks for slow editorial!
 » 10 months ago, # | ← Rev. 2 →   +7 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 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.
•  » » 9 months ago, # ^ |   0 "However will the subsequent >s after last > also be n-1,n-2,n-3? And will the subsequent
•  » » 9 months ago, # ^ |   0 Thank you for breaking my false assumption.
 » 10 months ago, # |   0 Thanks for the amazing editorial!
 » 10 months ago, # | ← Rev. 2 →   0 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.
•  » » 10 months ago, # ^ |   0 The fifth character is different.
 » 10 months ago, # |   0 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?
•  » » 10 months ago, # ^ |   0 $s_2 = \tt{bdtm}$, not $\tt{pbdm}$
•  » » » 10 months ago, # ^ |   0 i'm having same problem just wondering why ( s1= pbdtm -> s2 = pbdm )is not valid ???
•  » » » » 10 months ago, # ^ |   0 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.
•  » » » » » 10 months ago, # ^ |   +5 Got it ! , thanks man
•  » » » » » 10 months ago, # ^ |   0 Thanks you so much.. actually I misunderstood the problem statement
 » 10 months ago, # | ← Rev. 2 →   0 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
 » 10 months ago, # |   0 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?
 » 10 months ago, # |   +3 Great idea for E, thanks a lot for the wonderful contest :)
 » 10 months ago, # |   0 You can also solve problem B by binary search. By the way, problem c editorial is great,thanks:).
•  » » 5 months ago, # ^ |   0 I tried to solve it using binary search 247760061, but getting a TLE though. can someone please help me figure out why?
•  » » » 5 months ago, # ^ |   0 Change while to for(int i=1;i<=200;i++) and set high to 1e9 and you'll pass this question!
•  » » » » 5 months ago, # ^ |   0 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?
•  » » » » » 5 months ago, # ^ |   0 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:)
•  » » » » » » 5 months ago, # ^ |   0 Yeah, got that man.Thanks, I was able to read through.
 » 10 months ago, # |   0 come on
 » 10 months ago, # |   +8 Nice editorial
 » 10 months ago, # |   +8 Awesome Editorial and Problem set.
 » 10 months ago, # |   0 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 circle, pair 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 a, pair 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 b, pair p, pair o, pair 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 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"; } 
•  » » 10 months ago, # ^ |   +10 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.)
•  » » » 5 months ago, # ^ |   0 can you please help me with my submission too 247760061
 » 10 months ago, # |   0 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: 227729256Not sure if this was intended to pass or not!
 » 10 months ago, # |   0 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.
 » 10 months ago, # |   0 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 answerif 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.
»
10 months ago, # |
0

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

}

while(!st.empty()){
char cha = st.top();
st.pop();
}

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

count++;
}

// cout<<ct<<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); } }

 » 10 months ago, # |   0 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.
•  » » 10 months ago, # ^ | ← Rev. 4 →   +12 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.
 » 10 months ago, # |   0 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?
 » 10 months ago, # |   +6 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
•  » » 10 months ago, # ^ | ← Rev. 3 →   +20 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.
•  » » » 10 months ago, # ^ |   0 Thanks very much!
 » 10 months ago, # | ← Rev. 2 →   0 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
•  » » 10 months ago, # ^ |   +3 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.
•  » » 10 months ago, # ^ | ← Rev. 2 →   +3 e.g. 2 11 33
•  » » » 9 months ago, # ^ |   0 Thank you so much!
 » 10 months ago, # |   0 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 ?>
•  » » 10 months ago, # ^ |   0 when you add 3, it becomes maximum so it shouldn't be a question mark, but rather a '>'
•  » » » 10 months ago, # ^ |   +3 Oh, I see now. Thank you Vanjanja.
 » 8 months ago, # |   0 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 #include 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; } 
 » 8 months ago, # |   0 for question C you should put a hint (use a stack) as only knowing this information made me solve itoverall, good question and perfect tutorial thanks
 » 7 months ago, # | ← Rev. 2 →   0 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
 » 5 months ago, # |   0 Another approach for problem A which is more concise 248334395