"Unfortunately, due to network issues, we are forced to reschedule the round. Let's do it in the coming days. Apologize."

Hope contest will provide positive delta to all.

Хочу пожелать всем удачи на предстоящем соревновании! Надеюсь, я смогу решить две задачи!

Can I cancel my registration? I dont think I can attend today for the new, rescheduled date.

Hi, what is the difference between a normal div 2 and an educational div 2?

almost 30k registered in edu round *_*.

Hope to perform better

I want to request a feature where participants can submit their own authored and properly documented solutions. I know people do share the approach they used to solve the problem but I feel if something other than editorial is available, it can be helpful to each and every one.

I received 10 penalties because I set INF to 1e16 for problem D. Feel free to laugh :') https://imgur.com/a/F5VcnwL

when that error came up I got almost sure that the contest is cursed. I submitted at 10 seconds remaining am I the last correct submission though.

how to solve c?

How to solve B?

My approach in D was to iterate on the number of elements to remove, If we remove i elements then we'll remove those which contribute most to the number of inversions(leftmost 1s or rightmost 0s) Is there something wrong?

Edit : Just saw some solutions of other people and looks like I went completely off tracks..

i try some inversion contribution type things in d problem But i didn't get anything Any hint for d problem

Can someone teach me or refer me to a resource where I can learn to make my DP not ugly? I learned DP on Leetcode and for multidimensional DP I will do something like:

int dp[MAX_N][b][c][d] = {};

memset(dp, -1, sizeof dp);

But this doesn't work on Codeforces because testcases may be <= 1e5 and initializing the DP array for this many testcases results in TLE. So on Codeforces like this contest's problem D I ended up using:

vector<vector<vector<vector<vector>>>> memo(s.length(), vector<vector<vector<vector>>>(2, vector<vector<vector>>(2, vector<vector>(2, vector(2, -1)))));

But surely there's a better way to do this, right?

include<bits/stdc++.h>

using namespace std;

define endl "\n"

define ll long long

int main() { ios::sync_with_stdio(false); cin.tie(0);

int t; cin>>t; while(t--) { string s; cin>>s; map<char,int>mp; for(auto i:s) { mp[i]++; }
if(mp.size()==1)cout<<-1<<endl; else if(mp.size()==4)cout<<4<<endl; else { if(mp.begin()->second==1||mp.begin()->second==3)cout<<6<<endl; else cout<<4<<endl; } }

}

Why this code don't work 1st problem... Can anyone help me out?

in C++20 inbuilt sqrt() is giving wrong answer but in C++17 it's accepting?? sqrtl() worked for C++20

How did so many people figured out answer for B is sqrt(n-1) is this some known concept or if someone could share how they landed up on this solution.

In the beginning 5min, the server was heavier than usual, hope the situation becomes better until the coming Div1+2.

I'm waiting for the proof of B.

I think the round should be made unrated

Problem B might be my least favorite problem ever, hopefully I can understand the solution when the editorial comes out, not just have people say they've guessed it :D

OOOOOOOOOOMG!I finally passed a C in div2

Badly stucked in B.

Other than a terrible Div2 B, this was a great contest.

B is so hard. how does it get so many ACs? What's the solution for B? I used binary search for even and odd count of points on one side and do a sum series. But it's so complex. What's the easier solution?

...(sorry for multiple comments caused by internet connection issue)

First time solved div2 A-F in 1.5 hours. (1801B - Buying gifts: What did you say?)

A: We can count the occurence of each color. There are only 5 ways to divide 4 bulbs into different colors: 1111, 112, 22, 13, 4. The answer for these situations are 4, 4, 4, 6 and -1.

B: The optimal way to place chips: choose an upper bound k, place chips on all points (x, y) with |x|+|y|<=k and (k-|x|-|y|)%2==0. We can find the optimal k by binary search.

C: We consider array {s[i]}=a[1]+a[2]+...+a[i], where 0<=i<=n, then {s[i]} will have exactly n*(n+1)/2-k inversions. First we let s[i]=i, the initial inversion number is 0. Then we swap some pairs of adjacent elements to increase the number of inversion. We can do this like what we do in bubblesort: first for j=0...n-1 do swap(s[j], s[j+1]), then for j=0...n-2, then for j=0...n-3, and so on. Every swapping will increase inversion number by 1. When we reach n*(n+1)/2-k we stop swapping and output {s[i+1]-s[i]} as answer.

D: It's optimal to use at most 1 swap operation (that's something like 00010111 -> 00001111). We need to choose an index i, remove all occurences of 1 on its left, and remove all occurences of 0 on its right. But if there are something like ...[1]0|11..., instead of removing [1], we can move it to right by swapping and save 1 coin. Similar for something like ...00|[1]0... , so we can solve the problem by prepare prefix-sums, suffix-sums and look for all choices of i.

E: Consider for all pairs of (c, d) with same value of t=c+d. Let v1 and be the current volume of water in the first and second tank. Then in the whole process, we have 0<=v1<=a and 0<=v2<=b. since v2=t-v1, we can write the second inequality as t-b<=v1<=t, then we have max(0, t-b) <= v1 <= min(a, t). Then for all possible values of c in this range, the lower bounds and upper bounds of v1 are the same, so we can let f(v;i,t) be the value of v1 after we do the i-th operation if v1=v before the operation and v1+v2=t, then the answer is the composition of functions f(_;1,t), f(_;2,t), ..., f(_;n,t). We can observe that every possible compositions can be determined by a tuple (f0, x1, x2), which means:

-if x<x1, f(x)=f0.

-if x1<=x<=x2, f(x)=f0+(x-x1).

-if x>x2, f(x)=f0+(x2-x1).

For each value of t we can find the answer for (c, d) with c+d=t by doing function compostions by some caseworks, and we can solve the problem in O(n*(a+b)+ab).

F: The optimal solution is: Fill fuel for the remained journey at cities with b[i]=1, and fill fuel to reach the next city at cities with b[i]=2. Thus when we leave a 1-city, we have at most k-a[i] liters of fuel for following 2-cities, which means we can save min(k-a[i], a[i+1]+...+a[j]) liters of fuel, where [i+1, j] is a maximal block of 2-cities. So the answer of all 1-cities are the same, and for some 2-cities we need to consume more fuel because we lost the opportunity for saving fuel.

there's no way to get a correct answer on B unless you binary search the square root, did none of the testers notice this?

You can solve B by this observation: one way to start placing chips is to start at [0,0] and then place chips a total distance 2 from the first one on positions [0,2], [1,1], [2,0], [1,-1] etc., forming a kind of a "star" this way, following this pattern you can place 8 + 1 starting chips, then each next amount of chips is greater than the previous one by 8 and the distance is going to increase by 2, so we end up with an arithmetic series which total sum is equal to:

1 + (k / 2) * (8 + (k-1) * 8), this should be equal or greater than the total amount n of chips that we want to place. After solving the quadratic, the minimum distance would be equal to 2 * k.

Another way to start is by placing 4 chips on positions [1, 0], [0, 1], [-1, 0], [0, -1], this way we can minimize the initial cost of placing chips to 1. Similar to the previous case, each next step we can place 8 chips more than the last step, each time increasing the total cost by 2.

In this case we end up with sum looking like this: 4 * k^2 = n, so the total amount of times k we should place portions of chips should be equal to k = sqrt(n) / 2 (careful with the rounding). The total cost in this case will be 1 + (k-1) * 2.

After we calculated the cost for each of two methods we should take the minimum one, that is our answer.

...(sorry for multiple comments caused by internet connection issue)