Блог пользователя Serval

Автор Serval, 20 месяцев назад, По-английски
Fun Fact 1
Fun Fact 2
Fun Fact 3
Fun Fact 4
Fun Fact suggested by testers

2085A - Serval and String Theory

Hint 1
Hint 2
Solution
Code (Python)

2085B - Serval and Final MEX

Hint 1
Hint 2
Solution
Another Hint
Another Solution
Code (Python)

2085C - Serval and The Formula

Hint 1
Hint 2
Solution
Code (Python)

2085D - Serval and Kaitenzushi Buffet

Hint 1
Hint 2
Hint 3
Solution
Code (C++)

2085E - Serval and Modulo

Hint 1
Hint 2
Hint 3
Hint 4
Solution
Code (C++)

2085F1 - Serval and Colorful Array (Easy Version)

Hint 1
Hint 2
Hint 3
Solution
Code (C++)

2085F2 - Serval and Colorful Array (Hard Version)

Hint 1
Hint 2
Solution
Code (C++)
Разбор задач Codeforces Round 1011 (Div. 2)
  • Проголосовать: нравится
  • +156
  • Проголосовать: не нравится

»
20 месяцев назад, скрыть # |
 
Проголосовать: нравится +59 Проголосовать: не нравится

Nice contest!

»
20 месяцев назад, скрыть # |
 
Проголосовать: нравится +61 Проголосовать: не нравится

If only Hint 1 was available for D during the contest , good problems overall.

»
20 месяцев назад, скрыть # |
 
Проголосовать: нравится +12 Проголосовать: не нравится

First time ever I do have a feel I can solve problems in Div2D and Div2F1.

Great problem setting, thanks for the contest.

»
20 месяцев назад, скрыть # |
 
Проголосовать: нравится -11 Проголосовать: не нравится

very weird that last div2 contest my rank was 419 and delta was 26... now my rank is lower 454 but delta is 33 ... I was expecting it to be 1 digit or maybe negative.

but I am ok with this... ha ha

»
20 месяцев назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

hint 1 for problem D feels like a personal attack, I spent quite some time thinking for DP solution lol.

»
20 месяцев назад, скрыть # |
 
Проголосовать: нравится +34 Проголосовать: не нравится

Nice contest, Even more nice editorial. Thanks to the everyone involved.

»
20 месяцев назад, скрыть # |
 
Проголосовать: нравится +26 Проголосовать: не нравится

You can easily solve D by going backwards in time and doing a regret greedy

»
20 месяцев назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +3 Проголосовать: не нравится

Serval please fix problem C's first hint !

thanks in advance!

UPD: Fixed!

»
20 месяцев назад, скрыть # |
 
Проголосовать: нравится +7 Проголосовать: не нравится

Finally hit CM! Very enjoyable round imo (definitely not biased), peak problems.

»
20 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Good contest with fast Editorial. The problems are interesting will try them all.

»
20 месяцев назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +3 Проголосовать: не нравится

Solution to the C is out of the box, wow. i was able to get upto (x + K ) and (y + k) = 0. I think hard after this. but that was the wrong direction.

»
20 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Can someone explain D to me? that % one is not very intuitive

»
20 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

One of the best contests in a while , not many prerequisites and just logical stuff . And also the solutions are surprisingly short :pray:

»
20 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

serval my glorious king im honored to give a contest written by you

»
20 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

in problem A,can't i just swap s[0] with something smaller than s[0] from the string,or swap s[n-1] with something greater than s[n-1] when s[0]==s[n-1] and if k>0? like abba and k=1 so abab and k=0 thus abab is a universal string. can anyone point out the mistakes in my logic? and if s[0]>s[n-1] we will just swap s[0] with s[n-1] and need 1 operation and no operations are needed if s[0]<s[n-1]

»
20 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Solution for C says "sufficient large" instead of "sufficiently large"

»
20 месяцев назад, скрыть # |
← Rev. 2  
Проголосовать: нравится -15 Проголосовать: не нравится

I absolutely hate these kinds of editorials, where the solution to a problem is written in 4 lines like — oh we can do this for the solution, then do that, then do this greedy approach which we won't explain how it is correct, and then finally find answer with some random data structure which we won't bother to implement. You might as well don't write the editorial please, it will make no difference.

You guys need to understand that a person who comes to the editorial, is expecting a detailed solution with good explanation, so that he/she can learn the idea behind it and use in future problems, and not a 4 line paragraph where half of the things are just written without any proofs or anything. Random people posting explanation in discussion thread are far better than these stupid editorials.

  • »
    »
    20 месяцев назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    I feel you and I will suggest doing some competitions on codechef, they have really detailed editorials

    also try to follow some YouTubers who analyze questions after the contest as they cover lower rated problems quite well. and then you can try to read editorials

    That is what I do when I am not able to make sense of editorial, or I comment on the editorial post asking people for help and questions which are solved by large number of people generally get some explanation. so we can help each other and write different explanations in the comments

»
20 месяцев назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

Can someone explain C again pls ?

  • »
    »
    20 месяцев назад, скрыть # ^ |
     
    Проголосовать: нравится +9 Проголосовать: не нравится

    $$$a$$$ ^ $$$b$$$ = $$$a$$$ + $$$b$$$ - $$$2$$$ * ($$$a$$$ & $$$b$$$) so the equation is $$$a$$$ + $$$b$$$ = $$$a$$$ + $$$b$$$ - $$$2$$$ * ($$$a$$$ & $$$b$$$) That means that ($$$a$$$ & $$$b$$$) = $$$0$$$ — ($$$x$$$ + $$$k$$$) & ($$$y$$$ + $$$k$$$) = $$$0$$$

    We observe that a power of two is represented like that $$$10000...$$$ and any number before it doesn't have the most significant bit on so their ANDing will always be $$$0$$$. We want to add $$$k$$$ to both numbers such that the greater of them becomes a power of $$$2$$$ and the other one becomes less than it.

    If both are equal then their ANDing after addition will never be 0. Otherwise, we can find the first $$$n$$$ such that $$$2^n$$$ >= $$$max(x, y)$$$ and make $$$k$$$ equal to $$$2^n$$$ - $$$max(x, y)$$$

    • »
      »
      »
      20 месяцев назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

      Great explanation, thanks.

      Repeating his explanation, we want the two final numbers to have bitwise AND AS 0. So, one way is, make one number as a power of 2, and the other number somewhat less than the first. Thus, they will have no set bit common.

      Method: Add just enough to the greater of the two (max(x, y)), to make it a power of two. Since the two numebrs are different, the smaller number will also be smaller after adding k.

      Code: 312044416

»
20 месяцев назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

E was too much beautiful for proving me so dumb :(

»
20 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Funnily enough I solved F1 without realizing you need $$$k/2$$$... and reading that hint was enough to solve F2. The data structure was not that heavy, you need a multiset for maintaining the smallest $$$k/2$$$ elements and another one for maintaining the remaining $$$k-k/2$$$.

»
20 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

check(0xc0ffee) Lol nice way to check for a random large mod in Solution for E

»
20 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Problem A with unclear meaning.

»
20 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

surprising problem C solution, i was not expecting O(t).

I was trying to do bitmasks but failed

»
20 месяцев назад, скрыть # |
← Rev. 2  
Проголосовать: нравится -11 Проголосовать: не нравится

Down vote me pls

»
20 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

2085D - Serval and Kaitenzushi Buffet Could someone please help me understanding what is wrong with my approach or code.

Approach:

While processing the time(0-index based) from n — 2(second last) to 0, I am trying to find out if I take the plate at time = i, then what is maximum sum of deliciousness of plates I can take at time > i, such that taking and consuming those plates (k + 1 for each plate) takes time <= n — 1 — (i + k), as this is the time left when I take plate i -> i + k time consumed. For that i am using a segment tree, in which I am storing for time = 0 to n, the (maximum sum of deliciousness, time) for each range processed by far.

Code:

#include <iostream>
#include <vector>

using namespace std;

struct Node {
    long long val;
    int len;
    Node () : val(0), len(0) {};
    Node (const long long& val, const int& len) : val(val), len(len) {};
    void output () {
        cout << val << ' ' << len << ' ';
    }
    const bool operator< (const Node& oth) const {
        return val == oth.val ? len > oth.len : val < oth.val;
    }
};

template <typename T>
struct SegTree {
    int n;
    vector<T> segTree;

    SegTree (const int& n) : n(n), segTree(n) {}

    T comp (const T& a, const T& b) {
        return max(a, b);
    }

    void update (int node, int l1, int r1, T& val, int tl, int tr) {
        if (l1 > r1) return;
        if (l1 == tl && r1 == tr) {
            segTree[node] = max(segTree[node], val);
            return;
        }
        int m = tl + (tr - tl) / 2, n1 = node + 1, n2 = node + 2 * (m + 1 - tl);
        update(n1, l1, min(r1, m), val, tl, m);
        update(n2, max(l1, m + 1), r1, val, m + 1, tr);
        segTree[node] = comp(segTree[n1], segTree[n2]);
    }

    T query (int node, int l1, int r1, int tl, int tr) {
        if (l1 > r1) return Node();
        if (l1 == tl && r1 == tr) return segTree[node];
        int m = tl + (tr - tl) / 2, n1 = node + 1, n2 = node + 2 * (m + 1 - tl);
        return comp(query(n1, l1, min(r1, m), tl, m), query(n2, max(l1, m + 1), r1, m + 1, tr));
    }

    void output () {
        for (int i = 0; i < n; i++) cout << segTree[i].val << ' '; // cout << segTree[i].output() << ' ';
        cout << "\n";
    }
};

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    short t;
    cin >> t;
    for (short tc = 1; tc <= t; tc++) {
        int n, m, k;
        cin >> n >> k;
        int d[n];
        m = 2 * (n + 1) - 1;
        SegTree<Node> segTree(m);
        for (int i = 0; i < n; i++) cin >> d[i];
        for (int i = n - 2; i >= 0; i--) {
            if (i + k < n) {
                int j1 = n - 1 - i - k, j2 = n - 1 - i - 2 * k - 1;
                Node val1 = segTree.query(0, 0, j1, 0, n), val2;
                if (i + 2 * k + 1 < n) val2 = segTree.query(0, 0, j2, 0, n);
                val1.val += d[i];
                val1.len += k + 1;
                segTree.update(0, val1.len, val1.len, val1, 0, n);
                if (i + 2 * k + 1 < n) {
                    val2.val += d[i];
                    val2.len += k + 1;
                    segTree.update(0, val2.len, val2.len, val2, 0, n);
                }
            }
        }
        cout << segTree.query(0, 0, n, 0, n).val << "\n";
    }

    return 0;
}

Submission link: 311909974

Thanks in advance.

»
20 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

the editorial with hints are way better than others

»
20 месяцев назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

Why account named AnotherAccount was banned?

»
20 месяцев назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

Does any $$$O(NK)$$$ solution for D exist? I have been thinking a lot on how to solve it and trying to see if anyone does to solve it, but it's either $$$O(N^2/K)$$$ or $$$O(N^2)$$$ (both of which I have did) or $$$O(N\log{N})$$$ (intended sol)

Why
»
20 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

For Problem D, I understand DP won't work because of the data range. But if I want to write a DP solution, how to do it? What's the transition function?

»
20 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Error_Yuan , Serval ; for problem F , it might be that $$$l[x] = r[x]$$$ at some positions , so how do we really decide which way they shall go ? I observed that if I push them to a side where they are in majority , would be optimal for a given fixed position p , but I submitted few submissions , and perhaps in the optimal answer it doesn't matter where we push them to . Can we formally prove that $$$l[x] = r[x]$$$ case won't happen at some optimal positions or it doesn't matter whether it happens or not ?

  • »
    »
    20 месяцев назад, скрыть # ^ |
     
    Проголосовать: нравится +5 Проголосовать: не нравится

    It doesn't matter. You just need to know that an optimal strategy always use $$$k/2$$$ l-s and $$$k/2$$$ r-s. Thus, if we encounter the global optimal middle point, it does not matter which we choose if $$$l=r$$$ — the answer will keep the same.

»
20 месяцев назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

In Problem D why can't we just take the floor(n/k+1) max deliciousness plates from start to n-k th index?

Edit — NVM I got it. I am super dumb.

»
20 месяцев назад, скрыть # |
← Rev. 3  
Проголосовать: нравится 0 Проголосовать: не нравится

C using digit DP: 312651328. Mostly to practice technique. States dp[carry_x][carry_y]. For every digit try all values and see if we can make sum equal xor for first digits of k.

»
20 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Can someone tell me what's wrong in my solution for E? It's almost similar to the Editorial approach except I don't have that Check thing for s = 0 case. I don't think it's needed either because due to the modulo property, the elements of B can never exceed the corresponding elements of A. So, the sum of B must be <= The sum of A. In case of equality where s == 0, B must be a permutation of A so max_element of A + 1 should always be a valid k.

Rest of the code is almost same as editorial. What's the issue then?

Code — 312319353

»
20 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Could someone prove the optimality of part D? I don't think that the fact this is the best way to go about is it obvious. I get why you must have a = floor(n/(k+1)) sushis but how does this way of picking a sushi's at least as good as any other way of picking a sushis.

»
17 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Problem E: 327326244

can someone please tell me why does this give tle, it runs in $$$nlogn$$$ which should be fine according to the problem constraints.

»
14 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

i just wonder why the code of problem F2 works , can anyone explain ?

»
9 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Problem B I solved like this take consecutive element if any one is zero add {i, i+1} to ans as mex of that will be greater than zero and then if array is odd check last element is 0 or not if so add {second last, last} to ans after that all element are greater than 0 so at last add {1,n}. Maintain index as we delete elements also;

Accepted solution :- 364717400