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

Автор ItsNotMeItsYou, 3 месяца назад, По-английски

Sorry for underestimating the difficulties of the problems, especially B2 and D. We tried to serve as many cool problems as we could. And apparently, this led to some difficult ones.

Thank you for participating in the round. We all hope you enjoyed all of our problems.

2258A - Odd Eraser Idea: ItsNotMeItsYou, mychecksdead

Hint1
Solution
Rate the problem

2258B1 - Carrot Chopdown (Easy Version) Idea: mychecksdead

Hint1
Solution
Rate the problem

2258B2 - Carrot Chopdown (Hard Version) Idea: mychecksdead (This problem was originally designed with only $$$k=2$$$; thanks to ItsNotMeItsYou for expanding on the idea.)

Hint1
Hint2
Hint3
Hint4
Solution
Rate the problem

2258C - Far Cities Idea: Seferoglu (This problem was originally designed simply to find the furthest node from the root; thanks to cadmiumky for expanding on the idea. Thanks to robert9524 for providing stronger tests on cutting random solutions without an adaptive grader.)

Hint1
Hint2
Solution
Rate the problem

2258D - Magic Tiles Idea: ItsNotMeItsYou

Hint1
Hint2
Hint3
Solution
Rate the problem
Challenge

2258E - DivMEX Idea: ItsNotMeItsYou, carcinisation (This problem was actually designed differently. Thanks to anpaio for this version.)

Hint1
Hint2
Solution
Code (anpaio)
Rate the problem

2258F - Plus Minus Tree Idea: ItsNotMeItsYou

Solution
Alternative Solution
Rate the problem
Разбор задач Codeforces Round 1118 (Div. 2)
  • Проголосовать: нравится
  • +44
  • Проголосовать: не нравится

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

On clist.by we can check the hardest div2D since 2026:

wonderful 2500 difficulty!

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

.

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

I enjoyed the contest! (despite being one of the goobers who killed all their time on B2 :P)

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

editorial: "Thanks to robert9524 for providing stronger tests on cutting random solutions without an adaptive grader"

me: AC'd with a randomised solution and feels like the 0.01% of bacteria that don't get killed by soap

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

    what was your randomized appraoch?

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

      basically because so many interactive problems have binary search, my brain went straight to binary searching for the exact distance when you find a new farthest node, instead of realising that you can just increment it by one and that will happen at most $$$n - 1$$$ times.

      here's what i ended up doing:

      • same general idea of the two DFS passes

      • in each pass, keep track of furthest node $$$u$$$ and its distance $$$d$$$

      • maintain a variable $$$h$$$ as the maximum length a path in this graph can have (initially $$$n - 1$$$)

      • when considering a new node, first check if it beats the distance by at least 1. if not, stop and go to the next node. otherwise, binary search between $$$[d + 1, h]$$$ to find distance of this node. then update $$$h$$$ to be $$$MIN(h, \text{new distance + number of nodes left})$$$.

      • the randomised part of the solution is that instead of starting at vertex $$$1$$$, and then querying $$$2, 3, 4, ... n$$$ in order, I shuffle the vertices so that I should only need to do $$$O(log(n))$$$ binary searches, so on average, I should have $$$2 n - 2 + O(log^2(n))$$$ queries. The worst case is still just $$$n log(n)$$$.

      • intuitively, the worst case for such a solution should just be a path, so i wrote a program locally to simulate the process on a bunch of randomised paths, and it never exceeded $$$3n$$$ queries there.

      submission: 388829880

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

kawasaki, Synd209, elotelo, Anfeco tested the contest.

Can someone tell me how many problems they solved?

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

In D, why do you use biginteger when one can compare vectors lexicographically?

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

I really don't understand the solution to B2 in the editorial. Can someone who solved it please explain.

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

    388828299

    Instead of the editorial's approach, you can solve this very cleanly using a Harmonic Series and counting thresholds.

    To find how many pieces of target size i we get, we usually calculate a / i for each carrot.

    But instead of dividing, we can just count how many carrots are >=i, plus how many are >=2i, plus >=3i, and so on.

    A carrot of size 3i will naturally be counted exactly 3 times.

    my logic :

    Outer loop: Target piece size i (from 1 to m).

    Inner loop: Multiples j (1, 2, 3... up to m/i).

    Add the number of carrots >= i*j to a running count .

    The Cap: The problem states k cuts can only extract a maximum of 2^k — 1 pieces from an oversized carrot. So, the exact moment j hits 2^k — 1, our running count perfectly represents the capped answer for k cuts,

    The Bonus: We just add the frequency of exact matches freq[i * 2^k] to the count, because perfectly sized carrots yield exactly 2^k pieces, not 2^k — 1.Because the inner loop only runs m/i times, the total iterations are m/1 + m/2 + m/3..., which is O(m log m).

    My total solution is O(nlogn + mlogmlogn)

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

Why B2 feels harder than C

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

    See the score distribution: B2 is $$$1750$$$, C is $$$1250$$$

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

    Let,
    $$$f_l$$$ = cnt of $$$a_i$$$ such that $$$(a_i = l)$$$ and,
    $$$S_l$$$ = cnt of $$$a_i$$$ such that $$$(a_i \ge l) = f_l + f_{l+1} + \dots + f_m$$$

    For $$$k = 1$$$:

    $$$ ans = \max_{1 \le i \le m} (S_i + f_{2i}) $$$

    For a specific target length $$$i$$$ and $$$k$$$ operations, the count of pieces of size $$$i$$$ = ( pieces from carrots $$$\ge i\ $$$) + ( pieces from carrots $$$\ge 2i\ $$$) + ... + ( bonus pieces from carrots exactly $$$2^k \cdot i\ $$$)

    or,

    $$$\sum_{j=1}^{2^k-1} S_{j \cdot i} + f_{2^k \cdot i} $$$

    (The summation from $$$j = 1$$$ to $$$2^k - 1$$$ counts all the guaranteed pieces we get from large carrots)

    For general $$$k \le m$$$:

    $$$ ans_k = \max \left( ans_{k-1},\ \max_{1 \le i \le m} \left( \sum_{j=1}^{2^k-1} S_{j \cdot i} + f_{2^k \cdot i} \right) \right) $$$

    (Prefix max bcuz if we can get $$$X$$$ pieces with $$$k-1$$$ ops, we can get at least $$$X$$$ pieces with $$$k$$$ ops)

    code (c++)

    upd: fixed url

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

      Thank you so much, appreciate it mate (code url is not working)

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

        Don't know why unable to add this spoiler above ...

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

isn t editorial for E false? for example take a=[1,2,3,4,5] f(1,5)=7>max(a)+1=6

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

Interactive problems look easier (they’re less algorithmic).

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

Could you please include proofs for the lemmas used in the B2 editorial as well? The main point of the problem seems to rely on these lemmas, but they are stated without any proof or justification.

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

nice round write more plz

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

Nice problems. Humbled the shit out of me :(. Too weak.

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

Overall, not a bad contest, I just kind of sold on B1, because I thought there was some smart solution rather than the brute force (with prefix sums).

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

code of F is not viewable, can you check it pls

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

Hi, I'm unable to view the code solution of the problem. Anyone has any idea why this is happening?

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

Then repeat the process to find the other end of the diameter. This yields a total of 4n−4 queries. But, as previously written, distance can increase at most n−1 times. So this yields a total of 3n−3 queries.

can someone explain how 3n-3 queries instead of 4n-4?

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

B2 editorial use k + 1 cuts?

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

For problem C the editorial should say "For each node, first determine whether it is farther to the first vertex than the longest distance seen so far." Otherwise the solution logic doesn't make any sense.

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

Hello! I am trying to view the code solutions for the problems but clicking the submission link just redirects me to the editorial with a notification saying "You are not allowed to view the requested page."

Can anyone help me on why this is happening?

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

contest was great b2 got time from me but thumbs up for u guys nice round <3

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

why no nlog²m allowed for B2

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

Are we really voting Terrible on B2 because it's hard? I didn't solve it in contest but it's my fault for overcomplicating it. The difficulty distribution isn't good, but the problem is nice on its own.

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

whats wrong with this randomised approach 388836021

I thought that the probability of randomly picking a node with average distance(in between the max and min) would be high , so if that node's distance is $$$\ge \text{CURR_MAX} + 1$$$ , I apply binary search from $$$\text{CURR_MAX} + 2$$$ to $$$\text{n}-1$$$ ,otherwise I just pop it. Doing the same for the 2nd loop too, but like I cant figure out why this random approach is wrong? Please point out the total max queries with this approach.

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

    I am not sure if my reasoning is right but I made an attempt to show that your code may fail with a good probability. Firstly, your code always asks at least 2n — 2 queries

    Take example of this graph, here the distances from node 1 will be of the form [1,1,1,1,2,2,2,3,3,3], in the absolute worst scenario, you will ask queries in order of distances 1 -> 2 -> 3, this will contribute an additional $$$\log_2 (n - 2)$$$ + $$$\log_2 (n - 3)$$$ + $$$\log_2 (n - 4)$$$ to the queries. Now after you have chosen the first end of the diameter, say, node 7. You will have distances in the order, [1, 2, 3, 4, 4, 4, 5, 5, 6, 6] and again for the worst case scenario you will select in order of distances as 4 -> 5 -> 6 which will contribute $$$\log_2 (n - 5)$$$ + $$$\log_2 (n - 6)$$$ + $$$\log_2 (n - 7)$$$ to the queries. In our case, for n = 11, this will surpass the 33 queries limit with $$$\approx$$$ 35 queries. The probability of this happening in a single test case is actually the the chances of selecting 1 -> 2 -> 3 and then 4 -> 5 -> 6 and it comes to around 0.083% however the probability of exceeding 3n will be slightly more because here we chose the absolute worst case so to make thing easier let's say it is 0.1%. For t = 500, the probability of passing every test case is around $$$(0.999)^{500}$$$ $$$\approx$$$ 60%. A 40% probability of failing is actually pretty high in my opinion.

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

      makes sense tysm, I guess it couldve worked if the query limit was not too tight for example for 4n queries, Should've just dumped the randomised approach during the contest! Although the actual solution is just too adhoc to think that it would work..

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

B2 and D are just incredibly difficult, first time seeing <300 ppl solve a D in div 2(correct me if im wrong). B2 was nice tho but i cant found a way to do D :Sob:

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

"You are not allowed to view the requested page" Anyone facing this problem to see code

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

By clicking on the code. It's showing "You are not allowed to visit the requested page". Authors ItsNotMeItsYou please have a look.

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

Why i can't look at the code ? It is saying you are not allowed to look .

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

Gave a contest after a very long time and somehow ended up going from Specialist to Pupil

But I enjoyed every bit of it. What a wonderful contest. Brainstormed B2 for quite a while but couldn’t get it through.

Will upsolve it today.

Thanks to the contest writers!

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

The editorial about B2 states that the optimal order is $$$x \cdot 2^k, x \cdot 2^{k-1}, \dots, x \cdot 1$$$.However, this sequence actually contains $$$k+1$$$ operations instead of $$$k$$$. Furthermore, if we start with $$$x \cdot 2^k$$$, a carrot of exact size $$$a_i = 2^k \cdot x$$$ would remain unaffected during the first cut (since $$$l \le x \cdot 2^k$$$), which wastes an operation and prevents it from reaching the maximum $$$2^k$$$ pieces.The correct sequence of exactly $$$k$$$ operations should start from $$$x \cdot 2^{k-1}$$$, i.e., $$$x \cdot 2^{k-1}, x \cdot 2^{k-2}, \dots, x \cdot 1$$$.Just wanted to point this out! Thanks again for the nice problem.

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

Oh no. B2 was harder than C. Could not solve it, should have gone for C

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

I don't think B2 is that easy. It could even be around Div. 2 D difficulty, though it's also possible that this problem just happens to be outside my strengths.

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

I had an alternative implementation for B2.

Once you grasp the solution, the challenge becomes efficiently computing the following:

for a fixed $$$k$$$ and target height $$$x$$$ find $$$\sum\limits_{i = 1}^{n}{\min(\frac{a_i}{x}, 2^k)}$$$

Note that for $$$a_i \gt 2^k * x$$$ we should subtract $$$1$$$ as these carrots will leave an unwanted long piece.

The above expression can be computed efficiently computed by using the identity

$$$\left\lfloor \frac{a}{x} \right\rfloor =

\sum_{j=1}^{\infty} [a \ge jx]$$$

Thus over a series of numbers we want to calculate

$$$\sum_{i=1}^{n}\left\lfloor \frac{a_i}{x}\right\rfloor =

\sum_{i=1}^{n}\sum_{j=1}^{\infty}[a_i \ge jx] =

\sum_{j=1}^{\infty}\sum_{i=1}^{n}[a_i \ge jx]$$$

For each target $$$x$$$, we first use a suffix count array to get the number of carrots with length at least each multiple $$$jx$$$, then build prefix sums over those counts. This lets us evaluate $$$\sum_{i = 1}^{n} \lfloor a_i/x\rfloor$$$ in $$$O(1)$$$ for any fixed $$$k$$$.

Building these prefix sums costs $$$O(m/x)$$$ for target $$$x$$$, so over all targets the total is $$$\sum_{x=1}^{m} O(m/x)=O(m\log m)$$$ via the standard harmonic series argument. We also check $$$O(\log m)$$$ values of $$$k$$$ for each of the $$$m$$$ targets, adding another $$$O(m\log m)$$$, so the total runtime is $$$O(n+m\log m)$$$.

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

For D, My approach is, select the longest contiguous segment and update the remaining segments by adjusting their start and end pos, but this fails can anyone spot what goes wrong here?

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

The code link isn't working. "You are not allowed to view the requested page"

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

I had a different implementation for D without BigInteger.

After coordinate compression, let

$$$ p_0 \lt p_1 \lt \dots \lt p_{k-1}. $$$

For every (j), let (st_j) be the smallest index such that some black interval contains

$$$ [p_{st_j},p_j). $$$

Then the DP is

$$$ dp_j= \max\left( dp_{j-1}, \max_{i=st_j}^{j-1} (dp_i+\{p_j-p_i\}) \right). $$$

The main difference is how I compare DP states.

I store the multiset of chosen segment lengths in a persistent segment tree. To compare two states, I find the largest length where their frequencies differ.

Each node stores two 64-bit additive hashes. So I can check subtree equality in (O(1)), go to the right child first, and find the first differing length in (O(\log 10^{18})).

The hashing makes it probabilistic, but I use two independent 64-bit hashes.

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

it took me much longer than i'd like to admit to figure out that the author's username is not ItsNotMeltsYou instead of ItsNotMeItsYou

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

Hi everyone,

In problem C, the editorial uses the standard tree diameter trick: start a DFS/BFS from any vertex s, take the farthest vertex u, then DFS/BFS again from u and the farthest vertex v gives the diameter.

I understand the algorithm, but I can't convince myself of the key claim: why is u (the farthest vertex from an arbitrary s) guaranteed to be an endpoint of some diameter?

I tried to break it with this tree: s — p, p — u, p — q, q — a, q — b, where a and b are the deepest leaves of two subtrees under q. I wanted a-b to be the diameter with u being farthest from s, but it seems u being farthest from s forces d(p,u) >= 1 + d(q,a), which makes u-a longer than a-b, so it always works out. But I don't see the general reason.

Is there a short proof or intuition for why the farthest vertex from any s is always a diameter endpoint? A case analysis (path s-u intersects diameter / doesn't intersect diameter) or a "center of the tree" argument would be great.

Thanks!

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

How to prove the correctness of the alternative solution of 2258F?my idea is similar: using a regret greedy approach.Of course, Without the help of kinetic to lower the time complexity of a segmentree, the idea is proved to be TLE.Does anyone know how to prove the correctness of the greedy algorithm?that would be very helpful,thx.

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

    I'm also curious about this.However,i dont understand why this solution can be fasten by only HLD.i mean that how to lower the time complexity of a segamentree is easy,but how to lower the time complexity of the process of change every node's score and compare them once again?

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

What's the rating for B2 then?

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

thanks for the editorial