Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

BledDest's blog

Educational Codeforces Round 172 — Editorial
By BledDest, 27 hours ago, In English

2042A - Greedy Monocarp

Idea: BledDest

Tutorial
Solution (Neon)

2042B - Game with Colored Marbles

Idea: BledDest

Tutorial
Solution (BledDest)

2042C - Competitive Fishing

Idea: BledDest

Tutorial
Solution (Neon)

2042D - Recommendations

Idea: adedalic

Tutorial
Solution (adedalic)

2042E - Vertex Pairs

Idea: BledDest

Tutorial
Solution (awoo)

2042F - Two Subarrays

Idea: BledDest

Tutorial
Solution (Neon)
  • Vote: I like it
  • +45
  • Vote: I do not like it

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

did anybody solved problem C using greedy or binary search only if yes then please provide the code..

→ Reply
  • »
    »
    20 hours ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    .

    → Reply
  • »
    »
    4 hours ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    why is that you only search for those 2 solutions? are you scared of learning a new thing, and a new approach to problems? accept that some problems are weird and require unique solutions. this question cant be binary searched because m+1 does not always yield a better answer than m, and m does not always yield a better answer than m+1. also it cant be solved greedily as you have to consider all suffix differences. stop forcing algorithms just because you're lazy to learn more of them

    → Reply
    • »
      »
      »
      62 minutes ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Thanks for the reply, I coded a greedy solution for the problem but was unsure that i made all observations correctly , just wanted to make sure where i was lacking on greedy solution, but trust me even though I am not good at making mathematical observation yet I enjoy them a lot.. Since you are an expert can you please have a look at my profile and tell where I am going wrong ,I have solved over 400 problems but Still didnt made to pupil even though i am practising questions tougher than my level? I would be grateful to you!

      → Reply
»
23 hours ago, # |
  Vote: I like it -19 Vote: I do not like it

Look at what this idiot did.

Instead of using set upper_bound and lower_bound functions, this guy wrote a whole specialized segment tree. https://codeforces.net/contest/2042/submission/294446705 And it PASSED with only a single penalty.

Guess this is what happens when you solve too many range query problems.

→ Reply
  • »
    »
    19 hours ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    what's the issue, the segtree most likely does have smaller constants, it's not a totally unreasonable decision if you know I think (also idk who asked)

    → Reply
»
19 hours ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

.

→ Reply
»
19 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem C tutorial, shouldn't it be $$$0⋅s_{a_1}+(1-0)⋅s_{a_2}+(2-1)⋅s_{a_3}+⋯+s_{a_m}$$$ the resulting sum?

→ Reply
  • »
    »
    18 hours ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I'd like to add that..

    notice you only pick indexes to start a new group where str[i]=='1' and that group can go from i to the end or you can fraction that group into small groups, but for every index you pick to start a new group, the resultant score (diff bob and alice from i to end) or s[i] is positive cuz even if you divide a group into small groups at index i, you will keep the score of s[i]. Example:

    $$$n=9, k = 5$$$

    011100101

    Array $$$s$$$ will be $$${_, 2, 1, 0, -1, 0, 1, 0, 1}$$$, but you are only interested on making groups at indexes where s[i] have positive values. Now you can make a group at index where $$$s[i] = 2$$$ cuz it's the greatest in $$$s$$$. so you make a group between $$$i-1$$$ and $$$i$$$ where $$$i = 1$$$ and we get two points of score, but even if you don't keep the last group you made $$$[i:n)$$$, you'll still keep those two points: now you have groups [0:0] and [1:9). As we still have values on $$$s$$$, let's take the next greatest. Now you have groups [0:0], [1:1], [2:9), cuz in group [2:9) you have +1 of score, and you are still keeping the previous +2 points, even if you divided the [1:9) group.

    → Reply
  • »
    »
    4 hours ago, # ^ |
    ← Rev. 7   Vote: I like it 0 Vote: I do not like it

    For problem C, can't we use a prefix array to achieve the same result? Let aj denotes where the jth segment ends.

    Then, the sum can be expressed as: 0*pa1 + 1*(pa2 — pa1) + 2*(pa3 — pa2) + .... + (m-1)*(pam — pam-1)

    Simplifying, this becomes: -(pa1 + pa2 + ... + pam-1) + (m-1)*pam However, I am unable to eliminate the last m in the equation above. Can someone help?

    → Reply
»
18 hours ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Waiting for alternative way of problem D solution (Not using trees... ordered set in C++ or SortedList in python).

→ Reply
»
18 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone explain the solution of problem C, or someone give a different approach to problem C

→ Reply
  • »
    »
    18 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    read the comment I wrote above

    → Reply
  • »
    »
    15 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    we can use suffix sums for the same. check out my solution for it

    → Reply
»
14 hours ago, # |
  Vote: I like it -6 Vote: I do not like it

Copy of problem C: 1175D - Разделение массива

→ Reply
»
12 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

For Problem-C, you should use int64.

→ Reply
»
10 hours ago, # |
  Vote: I like it +10 Vote: I do not like it

Problem E can be solved in $$$\Theta(n)$$$ without requiring an $$$O(1)$$$ LCA computation. Instead, we precompute two properties for each subtree: (1) whether it contains all $$$n$$$ distinct values, and (2) whether it contains duplicate values. Using these properties, we can decide whether to select a vertex directly in order.

To facilitate the precomputation, we use the DFS order to represent each subtree as a range and then translate the constraints for a subtree into constraints for its corresponding range. Both properties can be checked in $$$\Theta(n)$$$ using a simple two-pointer technique on the range.

294738728

→ Reply
»
9 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

i tried c using binary search, but couldn't figure out the mistake.. :(

https://shorturl.at/043Sb

→ Reply
»
4 hours ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

For problem C, can't we use a prefix array to achieve the same result? Let aj denotes where the jth segment ends.

Then, the sum can be expressed as: 0*pa1 + 1*(pa2 — pa1) + 2*(pa3 — pa2) + .... + (m-1)*(pam — pam-1)

Simplifying, this becomes: -(pa1 + pa2 + ... + pam-1) + (m-1)*pam However, I am unable to eliminate the last m in the equation above. Can someone help?

→ Reply
»
2 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

For Problem D: What is the reason of the tle ?

void solve(){
    int n;
    cin>>n;

    vector<array<int, 2>> v(n);
    for(auto &curr: v)
        for(auto &it: curr)
            cin>>it;

    vector<array<int, 3>> a(n);
    map<array<int, 2>, int> m;
    for(int i=0; i<n; ++i)
        a[i][0] = v[i][0], a[i][1] = v[i][1], a[i][2] = i, ++m[v[i]];

    vector<int> ans(n);
    sort(a.begin(), a.end(), [&](const array<int, 3> &a1, const array<int, 3> &a2){
        if(a1[0] < a2[0]) return true;
        if(a1[0] > a2[0]) return false;
        return a1[1] >= a2[1];
    });

    set<int> s;
    s.insert(a[0][1]);
    for(int i=1; i<n; ++i){
        int currS = a[i][0], currE = a[i][1], idx = a[i][2];

        auto it = s.lower_bound(currE);
        if(it == s.end()){
            s.insert(currE);
            continue;
        }

        ans[idx] += (*it - currE);
        s.insert(currE);
    }

    sort(a.begin(), a.end(), [&](const array<int, 3> &a1, const array<int, 3> &a2){
        if(a1[1] < a2[1]) return false;
        if(a1[1] > a2[1]) return true;
        return a1[0] <= a2[0];
    });

    s.clear();
    s.insert(a[0][0]);
    for(int i=1; i<n; ++i){
        int currS = a[i][0], currE = a[i][1], idx = a[i][2];

        auto it = s.upper_bound(currS);
        if(it == s.begin()){
            s.insert(currS);
            continue;
        }
        --it;

        ans[idx] += (currS - *it);
        s.insert(currS);
    }

    for(int i=0; i<n; ++i)
        if(m[v[i]] > 1)
            ans[i] = 0;

    for(int i=0; i<n; ++i)
        cout<<ans[i]<<"\n";
}
→ Reply