awoo's blog

By awoo, history, 2 years ago, translation, In English

1728A - Colored Balls: Revisited

Idea: BledDest

Tutorial
Solution (Neon)

1728B - Best Permutation

Idea: BledDest

Tutorial
Solution (Neon)

1728C - Digital Logarithm

Idea: BledDest

Tutorial
Solution (awoo)

1728D - Letter Picking

Idea: BledDest

Tutorial
Solution (awoo)

1728E - Red-Black Pepper

Idea: BledDest

Tutorial
Solution (awoo)

1728F - Fishermen

Idea: BledDest

Tutorial
Solution (BledDest)

1728G - Illumination

Idea: BledDest

Tutorial
Solution (awoo)
  • Vote: I like it
  • +113
  • Vote: I do not like it

| Write comment?
»
2 years ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

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:

Source code
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    It can be proven that Bob have no winning strategy for every string. And a draw can be if and only if string have form ABC, where C is reversed A and B consists of pairs of identical letters standing next to each other (i.e. have form aabbcc...)

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

    I wanna know the intuition about your approach . Y does Bob never loose ?

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      Since Alice always goes first, she can just pick the most optimal letter which remains. If there is a letter that Bob can pick to beat Alice, Alice can just pick that letter instead of the last letter she chose.

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        This seems like a plausible explanation. But always going first doesn't guarantee a win(even though in this case it does). A good example would be of zugzwang in chess.

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

        But Alice can not pick s[2], s[n — 1] before s[1] or s[n] be picked。

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

          True, Alice can't pick s[2], s[n-1] in the first turn. But she can force Bob to not be able to pick one of them.

          For example consider: "zazz"

          Obviously if Alice picks s[1] then Bob will win by picking s[2]. So instead, Alice can force the game so that she will be the one to pick s[2]. If Alice picks s[n] on her first move then Bob has to pick one of s[1] or s[n-1] and Alice wins.

          You can apply the same logic to larger strings:

          "zabcaz" Alice picks s[1] Bob picks s[2] Alice picks s[3] Bob picks s[4] Alice picks s[5] Bob picks s[6]

          • »
            »
            »
            »
            »
            »
            2 years ago, # ^ |
              Vote: I like it +4 Vote: I do not like it

            Thank You! This greedy approach is cool

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

            Will this approach work for "yabz"? Because for both the choices Alice has, she'll lose.

            • »
              »
              »
              »
              »
              »
              »
              21 month(s) ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Yes it will. Remember, the chosen character needs to be prepended and not appended. So, the game can go as follows : Alice chooses z, Bob chooses b, Alice chooses a and Bob chooses y. Hence, Alice wins. You can try all possible combinations and you'll notice that Alice will win in all of them.

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

      My approach to Problem D is an O(n) solution. Since Bob never wins(Can check using strings of length 2,4,6 and manually verifying cases), what we need is to find the condition for the conclusion when the game ends in a draw. Firstly let us modify the input string given from s->s' where s' is s after removing all consecutive letters from start and end such that s[i]=s[length-1-i] and break the loop when s[i]!=s[length-1-i]. The reason is that if Alice picks one such letter then Bob can pick the letter from the opposite end to get a string to be the same as Alice's. Next the string s' left after removing all such letters (even 0 letters can be removed) ought to be of the form AABBCC.....ZZ where A,B,C,Z represents any letter. Reason is that if the string was AABBCC.....YZ,then Alice can pick Z and Bob has no other option but to pick either A or Y....i.e. He can never Draw with Alice and hence can only lose.

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think the most important thing to note here is that the length of the string is even + the chosen letters are prepended in the string. If either of the above conditions were not true, then Bob could have had a chance to win.

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

    please explain your approach

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

      It was just like what magni93 described. I guessed heuristically (proof by lack of counterexample) that Bob can't win, so that he can at best force a Draw. Additionally, a Draw can be forced only if the string looks like this: ABC, where A is an arbitrary sequence of characters, C is its reverse, and B is a sequence of pairs of adjacent identical numbers. Example: abcgghhddcba. Thus, for the first part (palindromic part), if Alices chooses a side, Bob can choose the other and maintain the Draw, and for the second, Bob can always choose the same side as Alice.

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        this is outta my league.. for now.. thx for explaining though i need more experience with questions

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

      If we already know that Bob can never win, then we can proof as below.

      Proof: One necesary condition for a draw is "The occurence number of Every letter cnt[letter] is even".

      Let's proof that s=ABC by induction (where C is reversed A and B consists of pairs of identical letters standing next to each other).

      For len(s) == 2, it's obvious. Suppose len(s) > 2 and cnt[letter] is even for every letter.

      In the first turn, if Alice's best choice is s[1], and Bob's is s[n], s[1] == s[n], then by induction, s must be s[1] ABC s[n] which is also a form of ABC.

      If the first turn Alice's best choice is s[1], and Bob's is s[2],then s[n] = s[1] or s[n] = s[n — 1] or else Alice will win. If s[n] = s[n — 1],Alice can alway pick one from the same side before a letter equals s[n] is met,by the induction s is the form of B. If s[n] == s[1] and s[n] != s[n — 1], Alice can choose s[n], Bob can choose s[1], and the remains must be draw too, otherwise Alice have no reason to choose s[1]. By induction, s also has form B.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Me after seeing other's D codes after contest and finding everyone used the same 100+ line dp algorithm and that doesn't remotely resemble my code.

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

(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!

»
2 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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://codeforces.net/contest/1728/submission/171533183

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

    Your greedy approach doesn't work. For instance, if the distinct elements are a = 11, b = 12345678901. In this case, you have f(b) = a. In your approach, you would need more steps.

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

    You were doing ans++ instead of ans += i.second on lines $$$296$$$ and $$$304$$$. Also, iterating and changing elements in map at the same time can cause bugs. For some reason, just using map instead of unordered_map does the trick in this case, but I am not sure why. I used to think that changing values while iterating would always mess the map's pointers up. Anyway, avoid using the standard unordered_map, you can get hacked in a contest. You can read more about it in this blog.

    AC solution

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

    As pointed out by brenner1, there was a trivial error in the code. I was wondering if the algorithm can be deemed incorrect even if it passes the test cases. Because it doesn't solve a more general problem (with higher constraints).

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

      For higher constraints, we can keep repeating the steps in a while loop until both arrays are equal (won't have much impact on time complexity aswell). Also I think this is more of a brute-force kind of approach.

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

      A problem is a problem under the given constraints. If you make a problems constraints higher of course a lot of solutions won't pass. But this given problem is for this given constraint and he only has to solve for it.

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

        I just find it convenient to believe that the correct algorithm is more important. A correct algorithm is correct independent of the constraints. That's the only difference between a problem and an algorithm ig. I now realize that it's futile to discuss/categorize this.

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

          No algorithm is correct independent of constraints unless the algorithm works in constant time. Sieve of erastothenes is an algorithm in O(sqrtn), which would only work work upto n<10^18. So would you not call it an algorithm?

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

            What does time complexity have to do anything with whether the algorithm is correct or not? Given any n, I can always find primes less than n using the Sieve of Eratosthenes. Hence, it's an algorithm. Just as a brute force check for prime is also an algorithm. However, some trick that would be able to calculate primes only less than a certain number 'm' would not be termed an algorithm.

            • »
              »
              »
              »
              »
              »
              »
              2 years ago, # ^ |
                Vote: I like it +1 Vote: I do not like it

              Ah u were talking like that. In that case you just have to get used to the fact that in a contest its better so solve the problem with given constraints than not at all.

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

    My solution is as same as you and I get accepted https://codeforces.net/contest/1728/submission/171984436

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

How to prove that Bob never wins in Problem D ?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    One way would be to look dp transitions. Having dp[i][i + 1] being equal to "Alice" or "Draw" there's no way to build winning dp of longer length.

    The other way would be the following: if Bob's string does not equal to Alice's, then it is no draw for sure. Consider there is some letter in result so Alice's string differ in that letter of Bob's string and all the other on prefix are the same. No matter how Bob plays Alice manages to take smallest letter when the left string is xSS...SSy. Regardless the step we encounter this configuration at. In fact Alice's strategy to take smallest letter at each step also leaves Bob no place to win.

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Even if the limit on C was larger, this algorithm would be fine if we just replace $$$9$$$ by the max digits that any of the array element can have.

»
2 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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

»
2 years ago, # |
  Vote: I like it +24 Vote: I do not like it

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

»
2 years ago, # |
Rev. 3   Vote: I like it +16 Vote: I do not like it

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.

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

    If I am not wrong, your solution runs in $$$O(N \log{(N)} + N \cdot K \log{(K)} + M \frac{N}{K})$$$.

    So on setting $$$K = \sqrt{N}$$$, your complexity is $$$O(N \cdot \sqrt{N} \cdot \log{(N)} + M \cdot \sqrt{N})$$$.

    Now you can improve the part of your solution which is contributing $$$N \cdot K \cdot \log{(K)}$$$. Instead of iterating over all numbers from $$$1$$$ to $$$K$$$, just iterative over all factors of $$$N-j$$$ which are smaller than $$$K$$$. This improves the constant factor.

    Here's my submission. I obtained a runtime around $$$1150$$$ ms by setting $$$K=500$$$.

    Edit: On putting $$$K=1000$$$, my submission runs in $$$826$$$ ms.

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

      You're right — thank you!

      I thought the bottleneck was the query part of the program because I had analysed the complexity incorrectly. Constant factor optimising by iterating over smaller factors sounds like a good idea.

      Also, I believe you you meant to write $$$O(N \sqrt{N} \log_2{(\sqrt{N})} + M \sqrt{N})$$$ instead of $$$O(N \sqrt{N} \log_2{(N)} + M \sqrt{N})$$$.

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        It was intentional as $$$O(log(\sqrt{N})=O(log{N})$$$ :p

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

      Can you explain your approach folks ? I understand the concept that you use , but it's still kinda hard to read

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

    I solved it in $$$O(N log_2(N) + NK)$$$ this is my solution

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

Very good round, hope more. -w-

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

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

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

    It's kinda non-increasing if you look at it from the maximum outwards. I meant to show that both parts behave the same.

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

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

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

    I solve it greedy in O(n) : if string s writing as s1 + s2 + s3 and s1,s3 is palindrome and s2[i]==s2[i+1] for any i :i is even then it is a draw else Alice win example string s=abbcca ,s=abeerrba ,s=abccba ,s=aabbcc here it is a draw here my submission :https://codeforces.net/contest/1728/submission/171626668

    but I suggest to solve it using DP suppose we have string of length n : s[l],s[l+1],,,,,,,,s[r-1],s[r] we have four cases : p1 : Alice choose s[l] and Bob choose s[l+1] ,p1=solve(l+2,r) if p1==0 then you need to compare s[l] , s[l+1]

    p2 : Alice choose s[l] and Bob choose s[r] ,p2=solve(l+1,r-1) if p2==0 then you need to compare s[l] , s[r]

    p3 : Alice choose s[r] and Bob choose s[l] ,p3=solve(l+1,r-1) if p3==0 then you need to compare s[r] , s[l]

    p4 : Alice choose s[r] and Bob choose s[r-1] ,p4=solve(l,r-2) if p4==0 then you need to compare s[r] , s[r-1]

    then the ans[l][r] = max(min(p1,p2),min(p3,p4)) you should calculate any substring with length 2 before here my submission using DP : https://codeforces.net/contest/1728/submission/171633331

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

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

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    You can build the same dp table as before, except in each entry, you also write down which indices $$$\ell$$$ and $$$r$$$ the dp value was copied from. The implementation gets a lot more annoying, but it's ultimately doing the same thing.

    After that, once the table is filled up, you can construct Alice's and Bob's strings by going backwards on the dp table. Start with $$$dp[0][n]$$$, check whether the value came from $$$dp[1][n]$$$ or $$$dp[0][n - 1]$$$, add the appropriate character to the Alice string, and then go to that corresponding entry. Use the same process to add the appropriate character to the Bob string, and so on, until the string has no characters left.

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

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

»
2 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like 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?

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

    Since the letters are being prepended to the player's strings, if Alice chooses 'b' and then Bob chooses 'a', Alice will chose the other 'a' forcing Bob to take 'b' resulting in these strings below which makes Alice win:

    Alice : "ab"

    Bob : "ba"

    So Bob also chooses "b" in his first chance and in the end both have string "ab" which would result in a draw

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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)

»
2 years ago, # |
Rev. 4   Vote: I like it +10 Vote: I do not like it

Some clarifications on the tutorial for 1728G - Illumination

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

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; }
»
2 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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

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

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

    They do nothing except for separating parts of the code.

»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like 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.

»
2 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

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))$$$

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

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)

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

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.

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

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.

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

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