awoo's blog

By awoo, history, 8 days ago, translation, In English

2026A - Perpendicular Segments

Idea: adedalic

Tutorial
Solution (adedalic)

2026B - Black Cells

Idea: BledDest

Tutorial
Solution (Neon)

2026C - Action Figures

Idea: BledDest

Tutorial
Solution (BledDest)

2026D - Sums of Segments

Idea: shnirelman

Tutorial
Solution (BledDest)

2026E - Best Subsequence

Idea: BledDest

Tutorial
Solution (Neon)

2026F - Bermart Ice Cream

Idea: BledDest

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

»
8 days ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

Maybe problems with single algorithms and tricks are not fit for edu round? :(

»
8 days ago, # |
Rev. 8   Vote: I like it -74 Vote: I do not like it

Any ideas or approaches on how to solve the 4th (D) problem? I’m not finding any hints to proceed.

»
8 days ago, # |
  Vote: I like it -16 Vote: I do not like it

Alternate Solution for C in O(n) time -> https://codeforces.me/contest/2026/submission/288737415

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

If anyone did C using 2 pointers and iterate the input string right to left can you explain your approach? I can't understand why we move the left pointer to the left when we hit a 0.

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well you just use the number present at 0 for a previous item instead of the left pointer's item so you decrement that

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Check my submission for left to right approach with 2 queues. I guess you could replace the queues with 2 pointers and it could be like a 2 pointer approach

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Do C really need Binary Search. I wasn't able to solve c during contest because of wasting time on B due to miss reading the problem. My solution link.As a pupil for me I no where thought of Binary Search and I have seen most of the submissions were O(n)

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem F ,

struct mindeque {
        //...
	int get(int p) {
		int ans = 0;
		for (int i = 0; i <= p; ++i)
			ans = max(ans, l.get(i) + r.get(p - i));
		return ans;
	}
        //...
};

When we call get(p) , it returns a subset value with a price exactly p. Because each time it is checking for i from l , and p-i from r. What happens when we want a price not equal to p but below p ? To resolve this issue we should probably make something like

if(dp[i] == 0){
    dp[i] = dp[i-1];
}

But I dont see anything like that in the code. I dont think the code is actually wrong but please correct my mistake.

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

    The $$$\mathit{dp}$$$ array is initialized with all zeros. You can think of it as "pay $$$i$$$ coins to get an icecream with tastiness $$$0$$$". Since you can do this for all $$$i$$$, you can turn buying a subset with total price below $$$p$$$ into exactly $$$p$$$ by buying this empty item with the remainder of the coins. I guess I will add this to the editorial.

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I see , thats a clever trick. Thanks for the help.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

problem $$$A$$$ can also reasoned with the fact that for perpendicular lines $$$slope_{AB}*slope_{CD}=|1|$$$.

try, fixing first segment $$$AB$$$ to $$$(0,0)$$$ and $$$(x,y)$$$ for ease. now $$$slope_{AB} = y/x$$$.

to make them perpendicular to each other, we want to do $$${y/x}*{x/y} =1$$$ therefore $$$slope_{CD}=x/y$$$ $$$(0,x)$$$ and $$$(y,0)$$$. but it may be possible that the $$$x$$$ or $$$y$$$ values that we are selecting (by swapping in $$$CD$$$) are greater than those allowed in the constraints.

as a result, we can only do $$$min(x,y)$$$ as maximum value to satisfy this construction .therefore, we set $$$x=y=min(x,y)$$$

  • »
    »
    8 days ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Please correct me if wrong.

    Consider this example (x, y) = (9, 3). Now consider lines -

    AB (0, 0) -> (9, 3) :- size = sqrt(90), slope = 1/3

    CD (0, 3) -> (1, 0) :- size = sqrt(10), slope = -3

    These are perpendicular but one line is greater than min(x, y) * sqrt(2) !!

    I believe the test cases are wrong to evaluate the problem, and solution exist outside of square box (0, 0) -> (min(x, y), min(x, y))

»
8 days ago, # |
  Vote: I like it +7 Vote: I do not like it

A very simple solution exists for C:

#include <bits/stdc++.h>
#define int long long
using namespace std;
 
const int inf = 1e18;
 
void ac() {
	int n; cin >> n;
	string s; cin >> s;
	s.insert(s.begin(), '0');
	int r = n * (n + 1) / 2, t = n;
	for (int i = n; i > 0; i--) if (s[i] == '1') {
		if (min(i, t) > 1) t = min(i, t) - 2, r -= i;
	}
	cout << r << endl;
}
 
signed main() {
	cin.tie(0)->sync_with_stdio(0);
	int t; cin >> t;
	while (t--) ac();
}

Essentially, we want to get the most expensive toys for free so we iterate the days in reverse order. On day i, if we can visit the shop and there are at least two unbought toys, we buy toy i and the cheapest toy not bought yet. Otherwise, toy i must have been bought on a subsequent day.

»
8 days ago, # |
  Vote: I like it +6 Vote: I do not like it

Problem C The greedy O(n) solution

Of all the figures, we will take some of them for free.

  1. For each figure from this set, we must have a figure to the left, for which we will pay.

  2. Of all the figures that we can take for free, it is advantageous for us to take the most expensive ones.

Let's go from right to left and maintain the number of figures taken for free that have not yet found a pair.

Let cnt be the number of figures that need to be paired.

If s[i] == 1, then we can try not to pay for the ith figure, this is possible if there are enough figures on the left to cover the needs of all the free figures taken before, for which there has not yet been a pair and another + 1 (a pair for the ith figure) If cnt < i, then we will take the ith figure for free, and increase cnt by 1.

Otherwise, we are obliged to pay for this figure, then we can pair it with one of the ones taken for free, or just buy it.

Code
  • »
    »
    8 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    This makes sense thank you

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

    Why the line cnt = max(cnt - 1, 0ll);? Why decrement count as you move from right to left?

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      this is the number of characters that we took for free, but have not yet found a pair of them that we will pay for. when we pay for the symbol i, we can pair it with the free symbol, which means making cnt = max(cnt — 1 and 0)

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

    do you have a proof why greedy gives the min answer , i know its intuitive but how to show that the case of not doing greedy will not make a better answer as such ? how to show its always best to free from rigthmost ? the binary search is easy to prove because we are fixing length of free items , but here we dont have any such constraint in our hand in greedy sol

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This is really elegant, thank you!

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I feel like editorial's code for D is too much complicated, it could have been much simpler 288580929.

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I felt the explanation given for D was quite intuitive and what I thought suring the contest. Do you mind explaining your approach for D in short?

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

      Firstly this problem can be seen as difference of two types of sums, till(r) - till(l-1).

      The blocks of type (1, x), (2, x) ... each can be calculated by first calculating the value for (1, x) then removing contribution of a[1], a[2]...

      Also I used additional array (psps) in which psps[i] = s(1, 1) + s(1, 2) +.... s(1, i), can be calulated as prefix_array of prefix_array of a

      For calculating till(f) for say some f first terms, we can locate the number of blocks used in O(log(n)) as (2 * n + 1 - i) * (i) / 2 <= f for i blocks used.

      Now some remaining terms are left, let them be f2 = f - (2 * n + 1 - i) * (i) / 2 (i is the number of blocks used).

      Now the terms left are s(i + 1, i + 1), s(i + 1, i + 2), ... s(i + 1, i + f2) [First f2 terms of i + 1th block]

      using prefix array of a if we add prefix sum of first i terms of a to all these terms, these is sum becomes s(1, i + 1), s(1, i + 2) ... s(1, i + f2), this can be calculated using the psps array I introduced earlier.

      So sum of first f terms if first i blocks are used and f2 extra terms is

      till(f) = prefix_sum_of_blocks[i] + (psps[i + f2] - psps[i]) - f2 * (ps[i])

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Editorial's explanation is fine, its just I feel uneasy seeing long codes

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

What was the O(n) solution for B?

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    for every query most of the work can be easily done in O(1). The only thing that takes is finding the index pair (i,j) (S[i,j]) from the index given in queries. Which can be done in both O(1) i.e by using quadratic equation root and O(logn), i.e by using binary search

    If you solve it using quad equations. the conde complexity goes upto O(q).

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    for n%2=0 its trivial, and for n%2=1, you can calculate prefix maxima for difference of pairs and also calculate suffix maxima for the same thing, and then take the minimum of the maximum of the 2 values for all odd elements, and thats the answer

»
8 days ago, # |
  Vote: I like it +14 Vote: I do not like it

If you are struggling to write good A problems, I can put some time in order to help.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the O(n) Solution of B. ?

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    First, notice that we only paint a cell that isn't listed if and only if N is odd. Otherwise, just join adjacent cells & output the maximum distance out of all the pairs. For odd N, since we are coloring at most 1 cell that isn't on the list black, this is equivalent to taking out 1 cell, connecting that with an adjacent cell (which is equivalent to a distance of 1), and solving the problem for even N with the remaining N-1 cells. This can be done efficiently in O(N) by maintaining a prefix & suffix max of connecting pairs of cells leading to a particular cell.

    Code: 288522179

    • »
      »
      »
      3 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i committed the amateur mistake of thinkinG we can pair a cell more than once. Maybe they could have explicitly mentioned one cell can be painted black only once/

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

B also has a O(nlogn) solution : https://pastebin.com/AWNxu6MN

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you give some hints about doing B in O(n)?

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can maintain prefix and suffix max and check for each element being removed. Obviously, you do this when $$$n$$$ is odd.

»
8 days ago, # |
  Vote: I like it +8 Vote: I do not like it

Did anyone get AC for E using a randomised approach? This was my closest, WA on test 34.

»
8 days ago, # |
Rev. 3   Vote: I like it +12 Vote: I do not like it

However, we can rewrite popcount(x) as 60−zeroes(x), where zeroes(x) is equal to the number of bits equal to 0 among the first 60 bits in x. So, we have to maximize the value of k+zeroes(x).

I am curious about 'maximize the value of k+zeroes(x)'.
Shouldn't be 'maximize the value of k+zeroes(x)-60'?
Why there's no mention about minus 60 and in code?

UPD:
I saw it.
when calculating the answer it uses 'n-max_flow' which already remove the effect of 60 bits.

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

    n — max_flow is a simplified equation of (n + 60 — max_flow) — 60 this is more intuitive to think about the (n + 60 — max_flow) is your value and u are subtracting 60 because for each bit in the 60 its either zero and added 1 which it should add or 1 and added 0 which it should subtract 1

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

why is n too small in problem E ? even the worst bipartite graph matching algorithms work in n^3 also for this problem specifically we have small V and small E so whats the reasoning behind not using 500 or 800 ?

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Just a dumb question, but because of it I struggle with question "B". If n is even, I don't thing solution of it is so simple.

Let assume case like this [ 2, 100,101,102]. In this case if we paint wall [1,2,100,101,102] then it is possible to to keep k=1.

Only issue is we have to paint wall 101 twice for which I didn't saw any limitation in question.

Feel free to let me know if I miss something or I made a error with the analysis.

  • »
    »
    5 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In question, it was stated, "choose two white cells i and j"

    so u cant pick an already coloured cell

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

does anyone know why this solution 289069335 for b is wrong?