Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### MikeMirzayanov's blog

By MikeMirzayanov, 4 years ago, translation,

Hello!

ICPC Southern and Volga Russian Regional Contest (Northern Eurasia) 2019 has ended on October 15. There were 76 teams onsite in Saratov, most of them were invited because of their result on the qualification stage.

In this contest I play a role of Cheif Judge and the jury teams consists of ex-participants of ICPC from Saratov and jury members from other cities. Many thanks to all of them! I hope you will like the problems!

I invite ICPC teams and individual participants of Codeforces competitions to take part! Sure, the contest will be unrated.

• +163

| Write comment?
 » 4 years ago, # |   -66 is this rated for div3?
•  » » 4 years ago, # ^ |   +12 "Sure, the contest will be unrated."
 » 4 years ago, # |   -9 Thank you for your efforts. Good luck to everyone!
 » 4 years ago, # |   0 how to solve E?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +22 It's kind of 2-SAT.Let's iterate over all pairs of necklaces. For each pair $p$ and $q$, look at the similarities of $p, q$ and $p, rev(q)$. If this pair can only exist when both are in the same direction, draw a white edge between them; if this pair can only exist when one of them is reversed, draw a black edge between them; if this pair can't exist either way, report a failure. After this reduction it is fairly similar to e.g. 553C - Любовные треугольники.We want to split the resulting graph into two parts $S$ and $T$, such that there are only black edges between $S$ and $T$, and only white edges within $S$ and $T$; also, we want to minimize the size of $T$ (i.e. the number of reversed necklaces). First check if there is a cycle with odd number of black edges, if there is, report a failure. Otherwise, we have a bunch of "bipartite" connected components. Put the smaller half of each component into $T$ and we have our answer.
•  » » 4 years ago, # ^ |   +22 E had very odd bounds as it can be solved in quadratic time.For every pair of necklaces, we either get that Neither or both necklaces must be flipped (xor must be 0) Exactly one of the necklaces must be flipped (xor must be 1) The pair of necklaces imposes no conditions No amount of flipping makes them similar If 4 happens even once, answer impossible. Now knowing the orientation of one necklace in a connected component (with conditions as edges) determines the orientations of the rest. Just take the orientation that minimises flipped necklaces.
•  » » » 4 years ago, # ^ |   +7 Isn't it still O(N^2*M) for constructing the graph? For every pair of strings you need to iterate over them to count the similarity. After that it's just the coloring described by you. Is there a way of making the graph in a better complexity?
•  » » » » 4 years ago, # ^ |   +4 You can compare the pairs of strings by simply taking their xor. If you store them as bitmasks, the comparison takes, in some sense, $O(1)$ time. I assume this is what he means.
•  » » » » » 4 years ago, # ^ |   0 Thanks! I figured it out eventually. I find the bounds kind of odd now too.
•  » » 4 years ago, # ^ |   0 oh I'll check it. Thank you so much -is-this-fft- mango_lassi
 » 4 years ago, # |   -6 How to approach B?
•  » » 4 years ago, # ^ |   +14 you need at least k/2 buses and at most k buses since k<=8000 iterate on each k to find the optimal one
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +3 Only elaborating this approach, since I find the problem quite interesting. Suppose we have the counts of all teams in a non-descending/sorted order. An important observation is that in an optimal solution, the teams that go alone in the bus forms a suffix. This can be proven with an exchange argument. Now, what is the best way to pair up teams in a prefix? We want to pair up teams so that the maximum sum of counts is minimised. Consider the largest team in the prefix. It is best to pair it up with the smallest team (again, can prove with an exchange argument). So we remove the first and last of the prefix and repeat the procedure. Finally, we iterate on each prefix of even length (say $2i$) — obtain the maximum of the remaining suffix, and obtain the maximum sum of pairs of elements that are equally distant from the beginning and end of the prefix. Here, $s$ is the maximum of the two, and $r$ is $i + (n - 2i)$. And for all such $i$, we take the minimum of $s\cdot r$.
•  » » » » 4 years ago, # ^ |   0 Can you provide a link to the code? Thanks for the help.
•  » » » » » 4 years ago, # ^ |   0
 » 4 years ago, # |   -16 What is test case 2 in J ?
•  » » 4 years ago, # ^ |   0 there were a lot of test cases
•  » » » 4 years ago, # ^ |   0 Thanks, test cases are visible now
 » 4 years ago, # | ← Rev. 2 →   -21 -
 » 4 years ago, # |   0 Can anyone help me in explaining how to solve problem N (Wires) ? My solution is failing for test-case 7 :( Not able to figure it out
•  » » 4 years ago, # ^ |   +1 You delete a bridge.
•  » » » 4 years ago, # ^ |   0 I thought that I am already taking care of that. Looks like I am having a big or something. Thanks for that :)
•  » » 4 years ago, # ^ |   +21 Iterate over components, run dfs.Then you can always delete the last vertex in dfs (Try to think why it is true). So connect any vertex from next component with parent of last vertex.You don't need to find bridges or something like this.
•  » » » 4 years ago, # ^ |   0 Could you hack my solution?I add all the edges to connect the point, which is relabeled,using dsu and keep the sum of edge for each point.I check all the edges,if its Unicom block haven't been visit and one of its end is size of 1,I push it and its size-one point to a stack.If there is still some Unicom blocks haven't been visit, which means it's a circle.I got any of a edge with one of its point.I connect the 2~n element in the stack to element 1.I also WA on test 7.I have test many case and submit 10 times.I wonder whether my solution bugged or the SPJ bugged.Thanks a lot.
•  » » » 4 years ago, # ^ | ← Rev. 3 →   0 oh yeah! I am using algorithm to find all articulation bridges and made it complex. I see why choosing last node of the simple DFS works. I ll keep that in mind. Thanks for that :)Edit: Removing the code to find articulation bridges and just using last edge of DFS gave me an AC :)
 » 4 years ago, # |   0 According to the contests tab, it is "open hacking phase" now? Is there any actual hacking that can be done now? I.e. is there a reasonable chance that the test set (which was probably the same at the subregional) is not complete?
 » 4 years ago, # |   +40 Should we wait for editorial or not?
 » 4 years ago, # |   +4 How to solve problem C?
•  » » 4 years ago, # ^ | ← Rev. 3 →   +1 For C, What I did was, start by sorting queries by their r value. then i created a segment tree which tells the maximum possible answer with some l value for fixed r. segment tree was range update and point maximum query segment tree which also tells the index of maximum. now the main problem was how to store answer in segment tree so for fixed right index =x the index x would have -k + sum of segments which lie in (x-1,x) and index x-1 would have -2*k + sum of segments which lie in(x-2,x) and so on. we can do this possible by iterating over r and updating the range (1,r) with -k everytime.Heres my code- https://www.ideone.com/g2j16q
•  » » 4 years ago, # ^ |   0 https://pastebin.com/UNyjNnuuHere hope this helps
•  » » 4 years ago, # ^ |   -8 Key observation is that to reach row_index rb from ra all the elements lying between will be of same type(if element at ra is even then all elements will be even and vice versa)..same thing applies for column too... I am limited by my formatting skills otherwise I could have explained better
•  » » » 4 years ago, # ^ |   0 I think you posted this in the wrong announcement.
•  » » » » 4 years ago, # ^ |   0 Oops...nvm thanks for pointing it out
 » 4 years ago, # |   0 How to solve problem N:Wires?
•  » » 4 years ago, # ^ |   +1 If the number of connected components in the graph is $c$, then the answer is $c-1$.Just connect all the other components to the first component. To join the component:1) If it is a tree, change any leaf-vertex's edge2) otherwise, change any edge that belongs to a cycle
•  » » » 4 years ago, # ^ |   0 I was also trying to do this....but I couldn't hand the case31 23 45 6My code was connecting 1 with 3 or 4 which resulted in 2 becoming isolated.. How can I handle this situation
•  » » » » 4 years ago, # ^ |   0 Vertices can be isolated.We just need to make sure the edges are connected.
•  » » » » » 4 years ago, # ^ | ← Rev. 3 →   0 Oww!!!!of course...I guess I was overthinking after getting WA on test case 6...I was thinking about the vertices being isolated [Even sample case does that :|]....
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 UPD : Got it!! I wasn't considering multiple edges between two nodesIf the component is not a tree then if I change either any leaf node edge or cycle node edge, then will there be any problem63618975 Here I am trying to do that , but getting WA
 » 4 years ago, # |   +24 How to solve D, I, M?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +8 I: my solution was the weirdest solution I've ever came up withFirst to make it simpler we'll take the complement of the set, so we'll order by lesser size and greater sum and the restriction goes from SET <= K to SUM — SET >= K.Now, let's try and get TLE with a bruteforce solution like bf(i, remaining that need to be taken, current sum) + ordering the values before bruteforce.Here comes the trick, if we compress a tree to not have any internal nodes with degree 2 then it has O(N) leafs and O(N) nodes, using this fact we can compress the segments that we don't have a choice but to choose the values by using a binary search to remove that segment.This isn't enough since it might have values mixed in that are smaller than what should be the last value, so we do a binary search to find the largest value that doesn't use all M things and then do a special iteration to get some value that's exactly what the last should be.Complexity is something like O(N * logN * logV) or something like that lol.
•  » » » 4 years ago, # ^ | ← Rev. 4 →   +23 Alternative solution for I:Let's suppose we fix $K$ as the number of people in the subset $S$ and the people are sorted in increasing order of awkwardness. Obviously, the first set that we should output is $v_1, ..., v_K$. The main idea is how to transition from this set to potentially other sets while iterating through them in order of total awkwardness.It turns out that we can do that by two operations. Consider a pointer that initially points to $K$ and represents to the position of the $K$-th person in the set. We now consider two operations: - increase the position of the pointer by $1$ - fix the position of the pointer and grab a pointer to the previous person in the set.Basically, for set $1, 3, 5$ we can do these operations: $1, 2, 3 \rightarrow 1, 2, 4 \rightarrow 1, 2, 5 \rightarrow 1, 3, 5$.Essentially, we start increasing the second pointer only when we fixed the value for the first pointer.Two aspects here are essential: that the sequence of operations is unique for a given target set (we don't end up at a target set in two different ways), and that the intermediary sets are of increasing total awkwardness (the cost of transitioning is always positive). Therefore, the state space with these two operations is actually a rooted tree, and edges are always of positive weight. In fact, all edge costs are of form $v_{i + 1} - v_i$. That means that we can traverse the tree in order by simulating Dijkstra algorithm on this search tree.In order to reach the good complexity, we need to keep for each node in the tree a state of form: (maximum remaining sum, where current pointer points to, where is the fixed element to its right, how many elements are before it). Then we can transition from a state $(s, pos, npos, idx)$ to $(s - v_{pos+1} + v_{pos}, pos + 1, npos, idx)$ if $pos + 1 < npos$ (incrementing) or $(s - v_{idx + 1} + v_{idx}, idx, pos, idx - 1)$ if $idx > 0$ (fixing + incrementing). Each state determines the values $ptr_0 = 0, ptr_1 = 1, ..., ptr_{idx - 1} = idx - 1, ptr_{idx} = pos$, and the positions greater than $idx$ are determined by its path in the search tree.The rest is just reconstruction bonanza.Total complexity is $O(k \log{k})$.SolutionHow to solve D?
•  » » » » 4 years ago, # ^ |   0 Thank you but the solution can't be viewed.
•  » » » » » 4 years ago, # ^ |   0 Fixed.
•  » » » » 4 years ago, # ^ |   +47 solution of D:First we can imagine all the persons as 2-dimensional point $(L,R)$ with color $c$. If a person who located at $(x,y)$ is unhappy, then all person who located in the upper-left of $(y,x)$ should be in the same color(think about when two intervals don't intersect). So you can enumerate all the persons and see:if he is unhappy, what the color will be in the upper-left rectangle or we don't know the color yet.we change the problem to this:give some points with color(or don't have any color yet),and some upper-left rectangles with color(or don't have any color yet). you should choose rectangles as many as possible and make sure: 1.give colors to all rectangles and points which don't have colors yet. 2.all points in a chosen rectangle should have the same color with the rectangle.we can run a dp in $O(n^2k)$. for the first step,sort all rectangles according to its right boundary(from right to left).then define $dp[i][j][k]$ as "after considering the first $i$ rectangles, all useful points whose y-coordinate is larger than $j$ are already colored the $k-th$ color,how many rectangles you can choose at most?". some explanation about it: 1.after discretization, there are only $O(n)$ y-coordinates; 2.definition of useful points:you can imagine all the chosen rectangles, the figure of them is something like “stairs”. Obiviously only the points in the left of the leftmost stair are useful(because the rectangles are sorted).there are more details: 1.precalculate the color/number of points in all rectangles(I use bitset) 2.color the rectangle. and in the process of dp you need the information precalculated in the first step.the dp details are a little bit complicated but easy to think.At first I'm afraid this solution is not efficient enough, but after coding carefully, my solution runs in only $140ms$
•  » » » » » 4 years ago, # ^ |   +34 How to solve K? qwq
•  » » » » » » 4 years ago, # ^ | ← Rev. 4 →   +32 Suppose that we fix a way of distributing the ordinary projectors to seminars. Then there's a way to distribute the HD projectors iff for any integer $t,$ the time $t+0.5$ is not contained within more than $x$ intervals corresponding to seminars or lectures which do not already have a projector. (condition 1)It follows that we don't actually care about the exact intervals spanned by lectures. For example, $[1,4), [2,3)$ is indistinguishable from $[1,2),[2,3),[3,4),[2,3)$ or $[1,3),[2,4).$ Thus, we want to create some sort of flow graph with the seminars (not the lectures) as edges.The way of distributing the ordinary projectors must satisfy the following condition: Suppose that at time $t+0.5,$ exactly $X$ lectures and $Y$ seminars are happening. Then $X\le x, X+Y\le x+y,$ and at most $\min(y,x+y-X-Y)$ ordinary projectors are not being used at time $t+0.5$. (condition 2)Now let's construct a graph for the ordinary projectors. Create a vertex for each (compressed) time in increasing order from left to right. The source (left of all other vertices) has an edge to the first time and the last time has an edge to the sink (right of all other vertices). There will be edges for each seminar with capacity one and edges between every two adjacent times with capacities determined by (condition 2). All edges are directed from left to right. Then there will exist a distribution satisfying (condition 2) iff the max flow from the source to the sink is equal to $y.$If (condition 2) is satisfied, then (condition 1) will be satisfied as well, so after distributing the ordinary projectors we can distribute the HD projectors greedily. (Nice problem!)Code
•  » » » » » 4 years ago, # ^ | ← Rev. 4 →   +26 I have another interesting solution for D. First we can sort all persons by $r$ (departure time) in increasing order. For the $i$-th persion, consider who he will meet during the conference. We can define it as a set. $S(i)$ means the set of persons that the $i$-th persion will meet. For simplicity, we let $i \in S(i)$.According to the colors, there are 4 types of sets. The set contains at least two different nonzero colors. The colors in the set are the same, a nonzero color. The set contains two different colors, one is 0 and the other is nonzero. The colors in the set are all 0. When $S(i)$ is type 1, person $i$ is impossibe to be upset. When $S(i)$ is type 2, person $i$ must be upset.So we can preprocess these two types of sets and ignore them in the following solution.So the problem can be changed to this: we can select some sets (to make the corresponding persons upset), and assign a color to each set (For set of type 3, we can only assign the existing color). And this assignment is valid if and only if it doesn't exist that two sets are assigned different color but intersect with each other.Since $r$ (departure time) for everyone is increasing, we can describe $S(i)$ in a simple way. We can define $p(i)$ as the smallest $x$ that satisifies $r_x \geq l_i$. Then for all $p(i) \leq x \leq i, x \in S(i)$. And for those $x$ greater than $i$, $x \in S(i)$ if and only if $p(x) \leq i$. Hence, $S(i)= \{x|p(i)\leq x \leq i \vee p(x) \leq i \}$$S(i)$ consists of two parts, the first part of which is $\{x|p(i)\leq x \leq i \}$, a consecutive interval; the second part is $\{x|x>i,p(x) \leq i \}$, which may be some isolated points.Then we consider when will two sets $S(i)$ and $S(j)$ intersect. Suppose $i < j$, there are 3 types of intersection. The first part of $S(i)$ intersects with the first part of $S(j)$, if and only if $p(j)\leq i$. The second part of $S(i)$ intersects with the first part of $S(j)$, if and only if $\exists x, p(j)\leq x \leq j \wedge p(x) \leq i$. The second part of $S(i)$ intersects with the second part of $S(j)$, if and only if $\exists x, x>j \wedge p(x) \leq i$. (It is impossible that the first part of $S(i)$ intersects with the second part of $S(j)$ since $i < j$.)We can combine the conditions for the second and third types of intersection to $\exists x, x \geq p(j)\wedge p(x) \leq i$. We can define ${\rm minp}(i)=\min_{x\geq i}p(x)$. Then this condition can be rewrited as ${\rm minp}(p(j))\leq i$.Next, we can define $f(i) = \min(p(i), {\rm minp}(p(i)))$. Then $S(j)$ intersects with $S(i)$($i < j)$ if and only if $f(j) \leq i$. This is an elegant conclusion. After we get it, we can work out a dp solution. Define $dp(i)$ as the maximum number of unhappy persons when we only consider the first $i$ persons. After calculating $dp(i-1)$, how to get the value of $dp(i)$? First, we set $dp(i) = dp(i-1)$, then consider the maximum number of persons upset if we make person $i$ upset. We can enumerate the color $j$ assigned to $S(i)$, and then enumerate $k(0\leq k < p(i))$, which means the sets among $S(x)( k k$ and the color of $S(x)$ is $j$ or 0. We can use Binary Indexed Tree to maintain the amounts. This editorial is so long and I have written it for a long time because I'm not so good at English. But this approach is very easy to implement. I finished the code within 20 minutes. The time complexity is $O(n^2 k\log (n))$, where $k$ is the number of total colors. In the problem, $k=200$. Since we shouldn't enumerate all colors when $S(i)$ is type 3 (have a specific color), the complexity is far from reaching the upper bound. My solution runs in $93ms$.Here is my code.solution
•  » » » » » » 4 years ago, # ^ |   0 For the reason that the number of add operation is $n$, so with prefix sum, the time complexity is $O(n^2k)$.
•  » » 4 years ago, # ^ |   +64 M is nice. For each bit $i$, let L = set of indices $x$ with bit $i = 0$, R = set of indices $y$ with bit $i = 1$ and $y + 1$ also has bit $i = 1$. Similarly, for each bit $i$, let L = set of indices $x$ with bit $i = 1$, R = set of indices $y$ with bit $i = 1$ and $y + 1$ also has bit $i = 0$. Now, we used 26 sets.Observe that only pairs $(x, y)$, with y = 01111...1 (the string of 1s is nonempty) and x = 1 such that there is at least one bit 1 in the suffix, are uncovered.Thus, it is sufficient to make $12$ more queries that cover all y of the form 0111...1 for a fixed 1-suffix length and then put all x that can be matched on the left hand side.In total, my solution uses $38$ queries.
•  » » » 4 years ago, # ^ |   +5 Can you please provide your implimentation if you have it.
•  » » » » 4 years ago, # ^ |   +3 My implementation if you need :/#include using namespace std; // const int N = 5007; // bool mark[N][N]; inline bool checkbit(int x, int p) { return (x & (1< 0; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin >> n; vector< vector > rowres, colres; // memset(mark, false, sizeof mark); for(int b=0; b<2; ++b) { for(int i=0; (1< rows, cols; for(int k=1; k<=n; ++k) { if(checkbit(k, i) == b) rows.push_back(k); else if(checkbit(k+1, i) != b) cols.push_back(k); } if(rows.empty() or cols.empty()) continue; rowres.push_back(rows); colres.push_back(cols); // for(int &x : rows) { // for(int &y : cols) { // mark[x][y] = true; // } // } } } for(int i=1; (1< cols; for(int y=1; y<=n; ++y) { if((y & suff) == suff and (y & suff_e) == suff) { cols.push_back(y); } } if(cols.empty()) continue; vector rows; for(int x=1; x<=n; ++x) { bool ok = true; for(int y : cols) { if(y == x or y == x-1) { ok = false; break; } } if(ok) rows.push_back(x); } if(rows.empty()) continue; rowres.push_back(rows); colres.push_back(cols); // for(int &x : rows) { // for(int &y : cols) { // mark[x][y] = true; // } // } } int sz = (int) rowres.size(); cout << sz << "\n"; for(int i=0; i
•  » » » » » 4 years ago, # ^ |   0 Thank you very much.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 I think it should be " R = set of indices y with bit i=0 and y+1 also has bit i=0." instead of " R = set of indices y with bit i=1 and y+1 also has bit i=0.". Am i wrong?
•  » » 4 years ago, # ^ |   +19 Simpler solution for I:Sort all values. We loop through the number of elements from N to 1. Let's say now we are considering the ways to choose k elements. Start with the smallest k elements. We build our solutions progressively using 2 types of steps: Consider a pointer starting at the largest element. Each step consists of either increasing the current element to the next possible element, or move the pointer lefft and increase the current element to the next possible element. We can push the current sum, current position of pointer, position of previous element, position of current element into a priority queue to simulate this expansion. To restore the solution, just create an ID for each state and keep track of which move is used to reach the current state, and we can backtrack at the end.Complexity: $O(M\log M)$ Code#include #include #include using namespace std; using namespace __gnu_pbds; #define fi first #define se second #define mp make_pair #define pb push_back #define fbo find_by_order #define ook order_of_key typedef long long ll; typedef pair ii; typedef vector vi; typedef long double ld; typedef tree, rb_tree_tag, tree_order_statistics_node_update> pbds; pair par[3001101]; void solve() { int n; ll k; int m; scanf("%d %I64d %d",&n,&k,&m); vector > vec; for(int i=0;i > concerts; ll cursum=0; for(int i=0;i=1;siz--) { if(concerts.size()k) { cursum-=vec[siz-1].fi; continue; } int curid=0; priority_queue,vector >,greater > > pq; pq.push({cursum,0,n-1,siz-1,siz-1}); while(!pq.empty()&&concerts.size()(tmp); int id=get<1>(tmp); int maxnw=get<2>(tmp); int cur=get<3>(tmp); int curele=get<4>(tmp); lasid=id; concerts.pb({siz,S}); //proceed with current (type=0) if(cur0&&cur>curele&&S+vec[curele].fi-vec[curele-1].fi<=k) { pq.push({S+vec[curele].fi-vec[curele-1].fi,++curid,cur-1,curele,curele-1}); par[curid].fi=id; par[curid].se=1; } } cursum-=vec[siz-1].fi; } } printf("%d\n",int(concerts.size())); for(int i=0;i0) { seq.pb(par[lasid].se); lasid=par[lasid].fi; } vi ans; for(int i=0;i=0;i--) { if(seq[i]) {curid--; ans[curid]++;} else ans[curid]++; } for(int x:ans) { printf("%d ",vec[x].se); } printf("\n"); } } int main() { int t; scanf("%d",&t); while(t--) solve(); } 
 » 4 years ago, # |   +21 MikeMirzayanov codes are still not visible, will it be fixed or it will remain like this ?
•  » » 4 years ago, # ^ |   0 In fact, codes of a problem in this contest will be visible after you solve it.
•  » » » 4 years ago, # ^ |   0 For me visible are codes of problems which I solved. If you see codes of all problems maybe it is because of coach mode.
•  » » » » 4 years ago, # ^ |   +1 It's the same to me. I can't see the solutions of problems I haven't upsolved. If you want to find a solution of a problem in this contest, you can search tutorial in this blog. Other users may have posted their own solutions. If the tutorial of the problem is not posted, you can ask about it. I will try to help you.
•  » » » » » 4 years ago, # ^ |   0 Thanks, can you tell the solution of C and N.In N I came up what is the main idea, but I don't know how to implement it easily.
 » 4 years ago, # | ← Rev. 2 →   0 Does this competition have any influence on ratings?
•  » » 4 years ago, # ^ |   +3 of course not
•  » » » 4 years ago, # ^ |   0 Thanks a lot.
 » 4 years ago, # |   +3 Is there any solutions to these problems ？ Officially or unofficially.
 » 4 years ago, # |   0 Can anyone provide a link to there submission for problem B and J. Thanks
•  » » 4 years ago, # ^ |   0 in J you should binary search the amount of soldiers in one row. in B you should sort teams by size and consider you put 1st and last together, then 2nd and last-1 ans so on for each capacity you must check amount of rides and minimal capacity*number of rides among them will be the answer
•  » » » 4 years ago, # ^ |   0 can u provide link to your solution.. Thanks for replying..
•  » » » » 4 years ago, # ^ |   +3
•  » » » » » 4 years ago, # ^ |   +1 Thanks for providing the solutions, it help me a lot...
•  » » » » » 4 years ago, # ^ |   0 Can you explain why your solution works. You have explained your approach and I understood what you have done. But I can't really understand how we can restrict possible values for "Maximum capacity of single ride".
•  » » » » » 4 years ago, # ^ |   0 Thanks, nChurgulia! Can you explain what's the magic is here:  if(arr[i] + rem < c){ rem = arr[i]; }else{ rem = (arr[i] + rem)%c; } Why this does not work: ans += (arr[i] + rem)/c; rem = (arr[i] + rem)%c; 
•  » » » » » » 3 years ago, # ^ |   0 Because difference of heights can not be greater than 1, in this case you are accumulating rem
•  » » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 If you set rem = (arr[i] +rem)%c, there are chances that you will have soldiers of three different heights in a single row and you don't want that to happen. So, it is mandatory to check whether (rem+ arr[i]) >=c. If (rem+arr[i]) < c and you still carry on with making the row, then this row will have soldiers of height (i-1 i.e. rem) && (i) && (i+1) which are three different heights.
 » 4 years ago, # |   +4 Please write the blog for editorial, it will help in upsolveing the problem. Thanks
 » 4 years ago, # |   0 Can you please make all sources visible?
 » 4 years ago, # |   +3 How to solve G?
•  » » 4 years ago, # ^ |   +5 Enumerate on the position of last Reset operation, then we can use binary search to determine if this is possible. Also we need to know at least how many Reset operations we need to do before this one, which can be preprocessed using dynamic programming. The transition can be done using either binary search or two pointers. Time complexity should be $O(n\log{n})$.
•  » » » 4 years ago, # ^ |   +3 Can you explain your approach in more details?
 » 4 years ago, # |   0 How to solve L ?
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Just find the answer with a binary search.We can assume that $a \geq c$ because they are symmetric, then for an answer $k$ wee need to check whether we can satisfy the condition.Suppose we have all $a$ in set $A$, $b$ in set $B$ and $c$ in set $C$, then we need to adjust it.If $a \leq k$, obviously $c \leq a \leq k$, we only need to check if we can put some person b to $A$ or $C$.If $a \geq c > k$, we failed, otherwise we put $a - k$ person a in $B$, and we can take at most $b$ person b from $B$ to $C$, just to find out whether it is possible.
 » 4 years ago, # |   +10 I am wondering if everything is ok with checker for task I.During contest I've submitted solution. After contest with some assertions it turned out that test 9 is maxtest ($n, m = 10^6, k = 10^{18}, a_i = 10^{12}$). So I asserted to check if my answer is correct and I got wa instead of rte. To check if I haven't made any mistake (in asserts etc) I took accepted code from comments and with diff checked on my laptop that I calculated answer correctly. Now I have no idea what's wrong with my code/output, can someone investigate this (maybe I made a mistake, but I just can't see where)?
•  » » 4 years ago, # ^ |   +10 You solution prints lines like 999998 999998000000000000 in the bottom of the output.
•  » » » 4 years ago, # ^ |   0 Thank you. Sorry, I made a stupid bug in assertions.
 » 4 years ago, # | ← Rev. 2 →   0 Can anyone provide a solution for L? It will help me a lot... Thanks!
•  » » 4 years ago, # ^ |   0 Here it is.
 » 4 years ago, # |   0 How to solve problem K ?
 » 3 years ago, # |   0 Can anybody please help me in solving the F problem?
•  » » 3 years ago, # ^ |   0
•  » » » 3 years ago, # ^ |   +3 I think you can't see other solution in a gym, so it is better to convey your approach.
•  » » 3 years ago, # ^ |   +3 https://blog.csdn.net/hrd535523596/article/details/109006239 Maybe this will help, use google translate
»
9 months ago, # |
0

1250A - Berstagram- — Explanation We have to keep track of the highest and lowest position of each post. The algorithm can be explained as below:

Initially, we set the current position of each post to their post number. For each like received, we check the post that was liked, say it is k. If the current position of k is not 1, then we move k up to the position immediately above it (i.e., from cur[k] to cur[k]-1). The post that was previously in that position will move down to cur[k]+1. We update the current positions of k and the post that moved down. We update the highest and lowest positions of both k and the post that moved down. The above steps are repeated for all likes received.

Finally, we output the highest and lowest positions of each post.

Time Complexity The time complexity of the above algorithm is O(n + m), where n is the number of posts and m is the number of likes received The below code is near to final solution It does the swapping but not the indexing

# include <bits/stdc++.h> // include all standard libraries

using namespace std;

int main() { int n, m; cin >> n >> m; vector v(n); vector s(m);

for (int i = 0; i < n; i++) {
v[i]=i+1; // input the permutation vector
}

for (int i = 0; i < m; i++) {
cin >> s[i]; // input the vector of values to swap
}

for (int i = 0; i < m; i++) {
auto it = find(v.begin(), v.end(), s[i]);
int idx=it-v.begin();// find the index of the element to be swapped
if (idx > 0 && v[idx] == s[i]) { // check if the element is found in the permutation vector and is not the first element
swap(v[idx], v[idx-1]); // swap the element with its preceding element
}

}

return 0;

}