Hocky Yudhiono

hello

4 minute read 

// ==UserScript==
// @name         CF Printer
// @version      0.1
// @author       hocky
// @match        https://codeforces.com/problemset/problem/*
// @match        https://codeforces.com/contest/*/problem/*
// @match        https://codeforces.com/blog/entry/*
// @icon         https://www.google.com/s2/favicons?sz=64&domain=codeforces.com
// @grant        none
// ==/UserScript==

// https://gist.github.com/TianyiChen/329edfd7c02327c2a0c9e1307816abb8
(function() {
    'use strict';
    $('#sidebar').hide();
    $('#header').hide();
    $('#footer').hide();
    $('.menu-box').hide();
    // $('.second-level-menu').hide();
    $('#pageContent').removeClass("content-with-sidebar");
    // print();

    // Your code here...
})();

// ==UserScript==
// @name         cf-remove-solved-and-rating-and-info
// @version      1.0
// @description  Remove participant solved from codeforces also the rating and where the problem came from
// @author       Hocky Yudhiono
// @match        https://codeforces.com/*
// @match        http://codeforces.com/*
// @grant        none
// ==/UserScript==

;(function () {
    'use strict'
    $('a[title="Participants solved the problem"]').remove();
    $('span.tag-box').remove();
    $('table.rtable').remove();
    $('div.header div.title').remove();
    $('head title').remove();
    const colors = ["gray", "green", "cyan", "blue", "violet", "orange", "red","legendary"];
    for(const color of colors) {
        const currentRating = `.user-${color}`
        const userNames = $(currentRating);
        userNames.each((key, name) => {
            // console.log(currentRating.slice(1));
            // name.classList.remove(currentRating.slice(1))
            if(parseInt(name.textContent) > 0)
                name.remove();
        })
    }
    const problemRatings = $('.ProblemRating');
    problemRatings.each((key, problemRating) => {
        if(parseInt(problemRating.textContent) > 1800) problemRating.remove();
    })
})()


// @match        https://codeforces.com/problemset
// @match        https://codeforces.com/contest/*
// @match        https://codeforces.com/gym/*
// @match        https://codeforces.com/profile/*
// @match        https://codeforces.com/problemset/page/*
// @match        http://codeforces.com/problemset
// @match        http://codeforces.com/contest/*
// @match        https://ioi.contest.codeforces.com/*
// @match        http://codeforces.com/gym/*
// @match        http://codeforces.com/profile/*
// @match        http://codeforces.com/problemset/page/*

Problem Description

You are given $1 \leq n \leq 2 \cdot 10^5$ segments, $1 \leq l_i < r_i \leq 5 \cdot 10^5$, and you ‘re given $1 \leq m \leq 2 \cdot 10^5$ queries. Each query $u_i, v_i$ will ask you minimal segments to pick in order to cover the entire range from $u$ to $v$.

Observation 1

If we are at one point $x$ of the range, we would know that the function of using $k$ segments is monotone. Define $f(x, k)$ as the furthest point we can reach from $x$, using any $k$ segments, the equation $f(x, k) \leq f(x, k + 1)$ applies.

Observation 2

The equation $f(x, k) \leq f(x + 1, k)$ is also true.

Thus, from here we can do binary lifting, computing the function $f(x, 2^i)$ for each $1 \leq i \leq \log (5 \cdot 10^5)$. We may use sparse table for this. WLOG, let’s change the function to $g(x, i) = f(x, 2^i)$

Set the base case as $g(x, 0)$ using a simple priority queue. Then, we can do $g(x, 1) := g(g(x, 0), 0)$, it makes sense because both observations are correct, we can just compute the binary lifting for each range using this precomputed table.

Merging Two Balls

Observation 1

The intuition of reducing $l$ and $r$, wlog is reducing indexes and pick $2$ consecutive indices in the set.

Observation 2

By the nature of the problem, “bigger” elements will just get bigger, “smaller” elements will just get smaller. Thus giving another observation: big elements indices are special and thus are always included in the answer. The opposite holds, the smaller elements doesn’t seem to scale, so unless it has duplicates, the smallest element will never be picked.

Observation 3

Each indices can be “greedied” and picked as a candidate and solely focus on that element to scale to the final answer. Another observation, this element can only interact with its adjacent.

Observation 4

Develop an algorithm to greedily incorporate its left and right element to this certain element, and check whether it can be reduced into this single one.

This can be solved using dynamic programming in quadratic time.

Define a function $f(l, r)$ to be a boolean function meaning this $f(l, r)$ can either extend to $f(l - 1, r)$ or $f(l, r + 1)$. If our index $i$, which starts from $f(i, i)$ can make its way to $f(1, n)$ then it means the answer is yes.

So we can do a bfs from $f(1, n)$ to $f(i, i)$.

Lets create another function $g(l, r, right)$ to be another function meaning this $f(l, r)$ can extend to its right counterpart, which is $f(l, r + 1)$. Thus giving $f(l, r) = g(l, r, right) \lor g(l, r, left)$

Observation 5

There is a monotonic property of $f(l, r)$, if $g(l, r, right)$ is true, then $g(l^{pre}, r, right)$ where $l^{pre} < l$ is also true. The reverse variant of this property also holds. This is implied by $a[r + 1]$ constant values while extending the segment to its left will just increase the sum of the segments before $r + 1$. Thus storing this $(l, r)$ pairs might be a good idea.

Observation 6: Hidden scaling property

The worst case of way for this to happen is when you want to extend a single index, but it can only goes left right left right.

Something like:

((2 <- (1 -> 1)) -> 4)

By constraint, the number of jumping direction is in order of $\log n$, which is sublinear. So an algorithm of which we iterate each index and check it manually, (which will results in final $n \log^2(n)$) is feasible to solve this problem.

So if we can solve this following new problem A:

suppose we are at segment $(l, r)$, what is the furthest $r^{last}$, which \(g(l, r, right) \land g(l, r + 1, right) \land g(l, r + 2, right), \dots g(l, r^{last}, right)\) holds. Note that $g(l, r^{last} + 1, right)$ is false.

Combining with observation 5, we can build a data structure which holds the segments for each $y \in [1, n]$, describing the all this pair $g(x, y, right)$, where $g(x + 1, y, right)$ is false.

Now we can use a RMQ data structure to check the segments, which $g(x, y, right)$, will map to the array $a[y] = x$. Querying for the problem A will be something like rmq.getLastValid(r, l) which will find the last valid $r < r^{last}$ which value $a[r^{last} + 1] > l$

You may also enjoy