awoo's blog

By awoo, history, 43 hours 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
  • +63
  • Vote: I do not like it

»
43 hours ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

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

  • »
    »
    37 hours ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    Trump is gonna win in a landslide damn

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

    are constructive problems that bad?

  • »
    »
    30 hours ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Now I think there is no difference between Div.2 Round and Edu Round.

    • »
      »
      »
      30 hours ago, # ^ |
        Vote: I like it -20 Vote: I do not like it

      But the last problem in this contest is actually more difficult than most div.1 problems

  • »
    »
    22 hours ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    I like your profile picture

»
42 hours ago, # |
Rev. 7   Vote: I like it -61 Vote: I do not like it

I believe yesterday's contest was excessively difficult for educational rounds. In my opinion, it was the hardest educational round of all time. You can view the statistics from Clist: smash me.

UPD: Sorry for misunderstanding. I didn't saw that it wasn't updated.

»
42 hours ago, # |
  Vote: I like it -8 Vote: I do not like it
»
41 hour(s) 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.

  • »
    »
    23 hours 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

  • »
    »
    12 hours 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

»
41 hour(s) 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)

»
41 hour(s) 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.

  • »
    »
    41 hour(s) 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.

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

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

»
41 hour(s) 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)$$$

  • »
    »
    34 hours 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))

»
40 hours ago, # |
  Vote: I like it +4 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.

»
40 hours 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
  • »
    »
    39 hours ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    This makes sense thank you

  • »
    »
    37 hours 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?

    • »
      »
      »
      36 hours 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)

  • »
    »
    22 hours 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

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

    This is really elegant, thank you!

»
40 hours 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.

  • »
    »
    38 hours 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?

    • »
      »
      »
      37 hours 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])

    • »
      »
      »
      37 hours 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

»
39 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

What was the O(n) solution for B?

  • »
    »
    15 hours 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).

  • »
    »
    12 hours 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

»
39 hours ago, # |
  Vote: I like it +6 Vote: I do not like it

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

»
38 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    30 hours 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

»
37 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
35 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    28 hours 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.

»
33 hours 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.

»
30 hours 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.

  • »
    »
    12 hours ago, # ^ |
    Rev. 2   Vote: I like it 0 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

»
11 hours 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 ?