AndreyPavlov's blog

By AndreyPavlov, history, 9 days ago, translation, In English

1780A - Hayato and School

Idea: AndreyPavlov
Preparation: AndreyPavlov
Editorialist: AndreyPavlov

Tutorial
Implementation (Python)
Implementation (C++)

1780B - GCD Partition

Idea: 74TrAkToR
Preparation: qualdoom
Editorialist: qualdoom

Tutorial
Implementation (Python)
Implementation (С++)

1780D - Bit Guessing Game

Idea: AndreyPavlov
Preparation: qualdoom, AndreyPavlov
Editorialist: qualdoom, AndreyPavlov

Tutorial
Implementation (Python)
Implementation (С++)

1780E - Josuke and Complete Graph

Idea: T4M0FEY
Preparation: T4M0FEY
Editorialist: T4M0FEY

Tutorial
Implementation (Python)
Implementation (С++)

1780F - Three Chairs

Idea: AndreyPavlov
Preparation: AndreyPavlov
Editorialist: qualdoom

Tutorial
Implementation (С++)

1780G - Delicious Dessert

Idea: T4M0FEY
Preparation: T4M0FEY, AndreyPavlov
Editorialist: T4M0FEY, AndreyPavlov

Tutorial
Implementation (t4m0fey)
Implementation (AndreyPavlov)

Full text and comments »

 
 
 
 
  • Vote: I like it
  • +358
  • Vote: I do not like it

By AndreyPavlov, history, 12 days ago, translation, In English

Hello, Codeforces!

T4M0FEY, qualdoom and I are glad to invite everyone to participate in Codeforces Round #846 (Div. 2), which will take place in Jan/25/2023 17:35 (Moscow time).

This round will be rated for the participants with rating lower than 0x834 (i.e. 2100). Participants with a higher rating can take part in the round unofficially.

You will have 7 tasks and 2 hours to solve them.

One of the problems will be interactive. Make sure to read this blog and familiarize yourself with these types of problems before the round!

I want to sincerely thank everyone who provided invaluable help in preparing the round and made it many times better:

This is our first official round on Codeforces. We sincerely hope to your participation. We hope that you will like the proposed tasks!

The score will be announced closer to the start of the round.

We wish you good luck and have a good time! See you in the round!

UPD: Scoring distribution: $$$500-1000-1250-1500-1750-2000-2500$$$

UPD: Round is unrated. We're sorry — it's our fault.

UPD: Tutorial and comment about task C Once again, we apologize for the inconvenience caused.

Full text and comments »

 
 
 
 
  • Vote: I like it
  • -628
  • Vote: I do not like it

By AndreyPavlov, history, 6 months ago, In English

Problem

When you learn about Heavy Light Decomposition tree problems take on new meaning. But writing HLD every tree problem with queries so boring. In this post, I will show some problems (as well as ideas for solving them) in which you can write HLD, but with a little thought, the solution becomes easier.

Modifications and receiving at the point

Task: A tree is given, as well as requests to add in a subtree and on the path to the root, as well as to find out the value at the top.

First idea — HLD! But stop, we only need the value at the point, maybe can easier? Yes, we will solve task in offline mode.

Idea: How to find out what changes occurred at the top at time $$$t$$$? Need to store some structure, for example, segment tree and answer for query in time $$$t$$$ is sum on prefix $$$t$$$. Now we have add in subtree and on the path to the root. For subtere adding we will remember for each vertex that in its subtree we need to add the number $$$x$$$ and the query time. Also for path adding we will remember this. Now we run the dfs on this tree with next algorithm:

  1. Checking all subtree addings and remember in segment tree with adding in point $$$t$$$ value $$$x$$$
  2. Go to the childs with dfs
  3. Checking all paths to the root adding and remember as well as in 1
  4. Get the answer on all queries with sum on prefix $$$t$$$
  5. Remove all subtree addings (add $$$-x$$$ on prefix $$$t$$$)

DFS implementation:

// ...
void dfs (int u, int p) {
    for (auto [t, x]: subtree_query[u]) {
        segment_tree.upd(t, x);
    }
    for (int child: graph[u]) {
        if (child != p) {        
            dfs(child, u);
        }
    }
    for (auto [x, t]: path_root_query[u]) {
        segment_tree.upd(t, x);
    }
    for (auto t: query[u]) {
        answer[t] = segment_tree.get(0, t);
    }
    for (auto [t, x]: subtree_query[u]) {
        segment_tree.upd(t, -x);
    }
}
// ...

NOTE: instead of a segment tree, you can use a fenwick tree

Asymptotics is $$$O(n + q \cdot log{q})$$$

Adding on path, get the value at the point

Task: Given a tree and given queries to add x on the path and get the value at the point. Sounds like a normal task on HLD, because we need to add on path of two vertex. But here you can do without hld.

Idea: Find the LCA of 2 vertex, call it $$$l$$$. We will be again work in offline mode, we know of query his time $$$t$$$. First we solve the problem, if first there are change requests and then get requests at the point. We will make next trick — we create a new array let's call him $$$a$$$ add $$$-1$$$ to $$$a_l$$$ and parent of $$$l$$$, add $$$1$$$ to $$$a_u$$$ and $$$a_v$$$. Next we run dfs on this tree and for every vertex $$$u$$$ count $$$\sum{a_i}$$$ where $$$i$$$ is vertex in subtree of $$$u$$$. Note that this sum will be equal to the number that will be written at the top after all requests. How to solve our originially problem? Let's add a segment tree for time $$$t$$$ just like you did in the previous task.

DFS implementation:

// ...
void dfs (int u) {
    for (auto [t, x]: subtree_query[u]) {
        segment_tree.upd(t, x);
    }
    for (int child: graph[u]) {
        if (child != p[u]) {        
            dfs(child);
        }
    }
    for (auto t: query[u]) {
        answer[t] = segment_tree.get(0, t);
    }
}
// ...
void add (int u, int v, int t) {
    int l = lca(u, v);
    subtree_query[l].push_back({t, -1});
    subtree_query[p[l]].push_back({t, -1});
    subtree_query[u].push_back({t, 1});
    subtree_query[v].push_back({t, 1});
}

Note: we also may change segment tree on fenwick tree

Asymptotics $$$O(n + q \cdot log{q})$$$

Tasks

D. Water Tree — assign $$$1$$$ on subtree, $$$0$$$ on path to root and get the value in point.

C. Propagating tree — add alternating sum to subtree and get the value at point.

E. Vasya and a Tree — add $$$x$$$ to the subtree $$$k$$$ level and output all values after.

A. Max Flow — add $$$1$$$ on path and output max vertex value

Full text and comments »

 
 
 
 
  • Vote: I like it
  • +68
  • Vote: I do not like it