Awesome problemset; I really liked Red-Black Pepper, even though I couldn't solve it on time!

As for problem D... somehow, my O(n) greedy-ish algorithm passed all pretests and didn't get yoinked out of existence after system testing..... I'll be confused for a while

Edit: Here is my source code if anyone wants to look at it:

#include <iostream>
#include <cstring>
 
using namespace std;
 
int t, n, dr, i;
char s[2010];
 
int main()
{
    cin >> t;
    while (t--) {
        cin >> (s+1);
        n = strlen(s+1);
        for (i = 1; i <= n/2 && s[i] == s[n-i+1]; i++);
        dr = n-i+1;
        for (; i <= dr && s[i] == s[i+1]; i += 2);
        if (i > dr)
            cout << "Draw";
        else
            cout << "Alice";
        cout << '\n';
    }
    return 0;
}

(Problem E)

Let $$$d_1, d_2, ..., d_n$$$ be the sequence of values of $$$-a_i - b_i$$$ in a non-increasing order.

Shouldn't it be $$$-a_i + b_i$$$?

UPD: Fixed now, thanks!

for C my approach is like first remove element if it is present in both the arrays. After that only distinct element remains then decrease all the elements > 9 to single digits and add 1 to ans. Then repeat step 1 to remove duplicates. now only one digit distinct element remains for each of these elements add 1 to ans(if it is != 1). I think that my approach is right but it is not working can anyone tell why https://mirror.codeforces.com/contest/1728/submission/171533183

How to prove that Bob never wins in Problem D ?

Having the maximum values in C as $$$10^9$$$ actually allows for a simpler (imo) solution. A multi-digit number will always become a single-digit number by performing the operation. It's impossible for an operation to produce a multi-digit number.

So after you get rid of all the overlaps from the initial arrays, you can now safely perform the operation on every multi-digit number in both arrays (if a multi-digit number is present in one array but not the other, it's impossible for it to be generated on the latter, so you must apply the operation on it in the former). No sorting needed here.

Now everything is a 1-digit number. We can check for overlaps again, and get rid of them. When there are no overlaps remaining, we need to turn everything that isn't 1 into a 1, so we count how many non-1s we have, add that to our operation count, and get our final answer.

I'm going to link this $$$O(n)$$$ solution for Problem D here: https://mirror.codeforces.com/blog/entry/106726?#comment-951491

I have another solution for (1728E - Красно-черный перец) which runs in $$$O(K^2 \log_2{(K)} + M \frac{N}{K})$$$ where $$$K$$$ is a constant. Using $$$K = 150$$$ in my code has given me a runtime of $$$1606$$$ ms.

My Code: 171530099

I'll copy my approach for problem D from the annoucement :

First, because Alice play first and the length of the string is even, Alice can force Bob to take any particular character in the string by simply never take it. After Bob take this character either the string become empty and the game end, or it become a shorter string with even length, then we use this strategy again for the shorter string. By take advantage of this, when play optimally Alice will never lose.

The only way for Bob to draw is to always take the same character as Alice. Now we reverse the game from the end to begin to see what the original string would look like :

For each double turn of Alice + Bob, we add 2 identical character to the same side or different side of our string (for example : aa→aabb,bbaa or baab)

The critical point is that if we add to the different side, we can't add to same side anymore. Take the example baab→baabcc, here Alice can take b and Bob can't take any b so he will lose

So the form of our string is : half palindrome + some pairs + other half palindrome, the 1st and 3rd part form a palindrome

I have another solution for 1728E - Red-Black Pepper which runs in $$$O(N \log_2{(N)} + NK \log_2{(K)} + M \frac{N}{K})$$$ where $$$K$$$ is a constant. I have been able to obtain a runtime of $$$1606$$$ ms by setting $$$K = 150$$$ in this submission: 171530099.

My solution doesn't require the knowledge of diophantine equations and doesn't use some of the observations given in the editorial above. It relies on a square root idea.

Setting $$$K = \sqrt{N}$$$ results in a complexity of $$$O(N \sqrt{N} \log_2{(\sqrt{N})} + M \sqrt{N})$$$ which, I suspect due to poor constant factor, unfortunately TLEd for me.

Edit: Thanks to satyam343 for pointing out a flaw in my complexity analysis. I've fixed it.

Very good round, hope more. -w-

In the editorial of E:

Then everything to the left of is is non-increasing. Everything to the right of it is non-increasing.

Shouldn't it be "Then everything to the left of it is non-decreasing"?

Can anyone please explain the solution to problem D? Why the question is of DP and not greedy?

Suppose Problem D also asked to print the two optimal strings that the players will select, how do we proceed then?

someone please make a video tutorial for D — Letter Picking... or if there is one then please point me towards it.

Could someone explaine a D problem case "baab": Alice can pick only "b", then Bob picks "a". So "a.." < "b.." anyway. So Bob wins, but the solution contradicts this?

My solution to the C problem was hacked 171387514. Next day I resubmited the same code 171579962 and it passed all the tests. How do I understand my solution basicaly is correct or not? I thought that the hachs are added to tests. Could someone clarify this please? (It's not neccesary to check my code, just explain how the system works)

Some clarifications on the tutorial for 1728G - Illumination

For question D:-171677046 simple o(n^2) solution using min-max We need to observe the fact that since Alice is going first therefore either Alice can win or it will be a draw. 1 means Alice wins and 0 means it is a draw. Also remember, (0|1)=1(bitwise or). I approached it considering all the possibilities when Alice is at [l,r]. It can follow with either Alice choosing s[l] or s[r]. dp[l][r] denotes who will win after considering substring s[l,l+1.....r].

If Alice chooses s[l] then Bob will choose either s[l+1] or s[r]. So, dp[l][r]=min((s[l]<s[l+1])|dp[l+2][r],ans3|(s[l]<s[r])).The first part of min function denotes the case when Bob chooses s[l+1] and the second part denotes the case when Bob chooses s[r]. The or operation is there to take the case that Alice has the advantage of going first. Similarly, if Alice chooses s[r] then dp[l][r]=min(dp[l|[r-2(s[r]<s[r-1]),dp[l+1]][r-1]|(s[r]<s[l])).

using namespace std;
 
int find(vector<vector<int>> &dp,int l, int r,string &s){
    if(l>r)
        return 0;
    if(dp[l][r]!=2)
        return dp[l][r];
    int ans1=find(dp,l+2,r,s),ans2=find(dp,l,r-2,s),ans3=find(dp,l+1,r-1,s);
    dp[l][r]=max(min(ans1|(s[l]<s[l+1]),ans3|(s[l]<s[r])),min(ans2|(s[r]<s[r-1]),ans3|(s[r]<s[l])));
    return dp[l][r];
}


void solve(){
    int n;
    string s;
    cin>>s;
    n=s.size();
    vector<vector<int>> dp(n,vector<int>(n,2)); //initialiazation
    int ans=find(dp,0,n-1,s);
    if(ans==1)
        cout<<"Alice\n";
    else
        cout<<"Draw\n";
    return;
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

Why am I getting TLE in Problem C?It seems like a O(n) solution.

#include<bits/stdc++.h>

using namespace std;

int calc(int k){
    return to_string(k).size();
}

int solve(){
    int i,j=0,n,z,c=0,one=0;
    cin>>n;
    vector<int> b(n);
    unordered_map<int,int> mp;
    for(i=0;i<n;i++){
        cin>>z;
        mp[z]++;
    }
    for(i=0;i<n;i++){
        cin>>z;
        if(mp[z]!=0){
            mp[z]--;
        }
        else{
            if(z>9){
                b[j]=calc(z);
                c++;
            }
            else
                b[j]=z;
            j++;
        }
    }
    if(j==0)
        return c;
    unordered_map<int,int> mp1;
    for(auto [x,y]:mp){
        if(y==0)
            continue;
        if(x>9){
            c+=y;
            mp1[calc(x)]+=y;
        }
        else
            mp1[x]+=y;
    }
    z=0;
    for(i=0;i<j;i++){
        if(mp1[b[i]]!=0){
            mp1[b[i]]--;
            z++;
        }
        else if(b[i]==1)
            one++;
    }
    c+=2*(j-z)-one-mp1[1];
    return c;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t=1;
    cin>>t;
    while(t--){
        cout<<solve()<<"\n";
    }
    return 0;
}

In the solution for D. Letter Picking in the code inside the two for loops after these lines int r = l + len; dp[l][r] = 1; { why this brackets is used, these are used after for loop while loop if statements but what work these brackets are doing here in this code , I am unable to understand it

For problem G,why not DP?Dp from l1 to ln,only the leftmost unilluminated interest is useful,and we can do it similarly from ln to l1.

Alternate solution for G using binary search and inclusion-exlusion -
(POI = point of interest)
Accepted Solution

• Sort lanterns and POIs by coordinate

• For each mask, calculate the number of ways that at least all the POIs whose bits are set are unlit
  (eg. for mask 101001, POI 0, 2 and 5 should be unlit, rest can be whatever)
  To do this, you binary search for leftmost lanterns which have each POI in the mask as their closest, if lanterns $$$l_a$$$ through $$$l_b$$$ have $$$p_i$$$ as the closest POI, then multiply number of ways for that mask by $$$|p_i - l_a|*|p_i - l_{a+1}|*...*|p_i - l_b|$$$, let's call this $$$ways_{mask}$$$

• For each mask, find the number of ways that exactly all the POIs whose bits are set are unlit
  You can do this using inclusion-exclusion, let's call this $$$ways_{mask}'$$$, then $$$ways_{mask}' = [\Pi_m ways_m*(-1^{popcnt(m)+popcnt(mask)})]$$$ where $$$m$$$ & $$$mask = mask$$$

• With $$$ways_{mask}'$$$ computed, we can move to answering the queries -
  Let the new lantern be at $$$pos$$$ For each POI, calculate distance from $$$pos$$$ and sort them in decreasing order, let's say the distances are $$$[4, 2, 1]$$$ for POIs $$$[2,0,1]$$$, then we calculate the sum of $$$ways_{mask}'$$$ where mask contains bit no. 2, for all these masks, if the new lantern has a brightness of 3 or less, all POIs are still not lit. Next we calculate the sum for masks where mask contains bit no. 0 but not bit no. 2, for all these masks, if the new lantern has a brightness of 1 or less, all POIs are not lit. We continue this procedure m times, giving us the final number of ways in which the POIs are not fully illuminated
  For sum of $$$ways_{mask}'$$$ and for calculating $$$ways_{mask}'$$$ in the first place, you would need to use SOS DP

Final time Complexity — $$$O(m*2^m*log(n) + q*m*log(m))$$$

For the tutorial on Problem E — since we're checking how many dishes with black peppers we are going to include in our answer, it should say "Then we would want to check the answer for b*y black peppers" Right ?

Great problem and editorial btw. (y)

I found a simplier soution to problem E. It doesn't need any observations about the "non-strictly convex" property of tastiness and I didn't had to deal with diophantine equations. We can check all possibilities! There is not so much of them.

Sort the shops by their x_j values, (ans secondarily by their y_j values). For considering only the x_j values first, if x_j=1 you have N possibilities, if x_j=2 you have N/2... All in all you have (N+N/2+N/3+N/4+...N/N) possibilities, which is ~ NlogN,2022-12-06 posibbilities. For a fixed x_j, check all possibilities considering y_j too, that is (N/x_j)/(y_j) possibilities.

So all in all, u have to check NlogN+N/2log(N/2)+N/3log(N/3)... possibilities, which is

So this solution runs around O(Nlog^2N) and passes in 1 sec.

For problem F, the tutorial mentions "there are some implementations of Kuhn's algorithm which can run on graphs of size about $$$10^5$$$". It suggests one optimizing strategy that works here (don't always reset visited markers) and one that would fail here (greedy initialization??).

Can someone suggest a source where I could read more about different possible optimizations of Kuhn's algorithm depending on which assumptions are valid about our input graph? I searched around a bit but was not able to quickly find a good source or library code.

1728G — Illumination can also be solved using dp in $$$(n + q) * m ^ 2$$$ complexity. Here's my submission.