BledDest's blog

Educational Codeforces Round 172 — Editorial
By BledDest, 16 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
  • +38
  • Vote: I do not like it

»
14 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
  • »
    »
    9 hours ago, # ^ |
    ← Rev. 4   Vote: I like it +1 Vote: I do not like it

    .

    → Reply
»
12 hours ago, # |
  Vote: I like it -9 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://mirror.codeforces.com/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
  • »
    »
    8 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
»
8 hours ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

.

→ Reply
»
8 hours ago, # |
  Vote: I like it +1 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
  • »
    »
    7 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
»
7 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
»
7 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
  • »
    »
    7 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    read the comment I wrote above

    → Reply
  • »
    »
    4 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
»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
25 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

For Problem-C, you should use int64.

→ Reply