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

Автор Vladosiya, история, 2 года назад, По-русски

1702A - Округли цену

Идея: MikeMirzayanov

Разбор
Решение

1702B - Поликарп пишет строку по памяти

Идея: MikeMirzayanov

Разбор
Решение

1702C - Поезд и запросы

Идея: MikeMirzayanov

Разбор
Решение

1702D - Недешёвая строка

Идея: MikeMirzayanov

Разбор
Решение

1702E - Раздели на два набора

Идея: MikeMirzayanov

Разбор
Решение

1702F - Уравняй мультимножества

Идея: MikeMirzayanov

Разбор
Решение

1702G1 - Проходимые пути (простая версия)

Идея: MikeMirzayanov

Разбор
Решение

1702G2 - Проходимые пути (сложная версия)

Идея: MikeMirzayanov

Разбор
Решение
Разбор задач Codeforces Round 805 (Div. 3)
  • Проголосовать: нравится
  • +74
  • Проголосовать: не нравится

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

Problem Solved

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

Sorry, can someone explain me, how to solve problem E with DSU and how these formulas works. I only realized that if two elements should be in different sets, the formula will be to unite(x, y + n), unite(y, x + n). And if in one then unite(x,y), unite (x + n, y + n)

  • »
    »
    2 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    Uniting dominos sharing the same number and checking if there is a set of odd size would suffice.

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

    As Editorial said, each number must exist exactly two times, i.e. every node has exactly two edges. Graphical representation of this will be just a set of disjoint cycles. Just use DSU to check if any of the cycles is odd lengthed.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится
    0...n-1 ==> blue 
    n...2n-1 ==> red
    

    In bipartite graph each edge end (edge: x-y) should have different colors so (Blue, Red) or (Red, Blue). so we unite(x,y+n) or(x+n,y) In Bipartite odd cycle doesn't exist. since cycle must start with vertex x and end with vertex x. Lets say cycle starts with vertex x of red or vice versa and start assigning colors alternatively then if it is

    Even cycle ends with vertex x of red [ x(Red) -> y(Blue) -> x(Red) ]
    Odd cycle end with vertex x of blue [ x(Red) -> w(Blue) -> z(Red)-> x(Blue)]
    so if x(Red) and x(Blue) which is (x,x+n) belongs to same component then odd cycle exists. Hence answer is "NO".
    
    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      why can we add an edge between the two sides of the domino, because they must be in the same component?

      • »
        »
        »
        »
        2 года назад, # ^ |
        Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

        First, if any number appears more than $$$3$$$ times, print NO. For $$$n$$$ dominoes entered, it contains $$$2n$$$ numbers. According to Pigeonhole Principle, every number appears inevitably $$$2$$$ times.

        If we think of numbers as vertices (graph theory) and dominoes as edges (graph theory), the graph $$$G$$$ will be constructed by many cycle (graph theory).

        Consider two dominoes $$$a=\lbrace 1, 3 \rbrace$$$ and $$$b=\lbrace 1, 4 \rbrace$$$. Because they have a common number $$$1$$$, they must be placed in different sets. Without loss of generality, we can think of $$$a$$$ as the outgoing edge and $$$b$$$ as the incoming edge. It's like we dyed the edges in Red and Blue. two different colors. In a circle (graph theory's circle), bijection from edge to point can be constructed. So we can transform the edge dyeing problem into the vertex dyeing problem.

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

    I solved using DSU.

    https://mirror.codeforces.com/contest/1702/submission/189937922

    The reasoning:

    If a pair {a, b} exists, then we know that another pair that contains {b, c} must be in a different set. We can visualize this by creating 2n nodes (one node if the ith pair is in the first set, and another node if the ith pair is in the second set). In my code, I used Node "a" to denote that a is in the first set, and Node "a + n" to denote that a is in the second set.

    We can create 2 edges per pair. Connect {a, b + n} and {a + n, b} for every pair {a, b}. This is because if we know that "a" is in the first set, then b must be in the second set, and vice-versa.

    It's easy to see that a solution only exists if Node a is not connected to Node a + n.

»
2 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Video Solutions for the complete problemset.

»
2 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Problem C had anti hash test cases got accepted during contest but TLE after the hacking phase :)

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

We can use priority queue to solve problem F yet the implementation is the same.

»
2 года назад, # |
Rev. 2   Проголосовать: нравится -6 Проголосовать: не нравится

Analysis of the third problem: just to start, we need to store the start and end positions of each individual number. And then we compare if the first position of a[j] is less than the last position of b[j] then the answer is YES, otherwise the answer is NO:

ll n, k;
cin >> n >> k;

map < ll , ll > first;
map < ll , ll > last;

for (int i = 1; i <= n; i++) {
    ll u;
    cin >> u;

    if (first[u] == 0)
        first[u] = i;
    last[u] = i;
}

while (k--) {
    ll a, b;
    cin >> a >> b;

    if (first[a] == 0 || first[b] == 0) {
        cout << "NO\n";
        continue;
    }

    if (first[a] < last[b]) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}
  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    hey, I did the same but I used unordered_map and it showed tle but when I used map only got AC why?

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

      unordered_maps are ridiculously slow in C++, and can easily be hacked to TLE. Someone must have hacked an unordered_map solution, and that hack would have made it into the test cases. map on the other hand is kinda fast (sometimes even faster than unordered_map), and will give AC because the log(n) factor doesn't impact the solution much. use map, not unordered_map, or you will be hacked

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

        Or you can use unordered_map with a custom hash function that uses chrono::steady_clock::now().time_since_epoch().count()

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

        Yeah, initially I too used unordered maps/sets a lot and got unexpected TLEs which is never fun. Although, in some rare cases, we don't have log(n) space. Here is a custom hash that I use when using unordered maps/sets is the only way. Hope this helps.

        Custom Hash
        Usage
»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Implemented Q3 as it is in the tutorial. But still getting TLE for Python Soulution. Any improvements?

https://mirror.codeforces.com/contest/1702/submission/163751004

»
2 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится
»
2 года назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится
»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem C:Do not cin, but scanf.

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

I solved G2 using Heavy-light Decomposition during contest. After finding both ends of the path, we can do a lazy range addition of 1 on the path between them in the HLD. Now every node in the query must have the value 1. Again range add -1 to reset the HLD.

https://mirror.codeforces.com/contest/1702/submission/163628298

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

    i used hld too, but i've added 1 to every node in the query and then calculated sum on path so, if it equals to k, the answer is yes, otherwise no

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

    Once you find the both ends of the path you actually don't need HLD though. If a node $$$w$$$ lies on the path between $$$u$$$ and $$$v$$$ then $$$dist(u,w)+dist(w,v)=dist(u,v)$$$ so just checking this for every node in each query gonna suffice.

»
2 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Can someone explain the dfs function of Tutorial of G1? I understand that first we precalculate each node's depth and choose the deepest node as the start point of our dfs as it will be one of the end points of our path, but I can't understand the dfs working.Thanks...

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

    The idea like this: Denote the set of selected vertexes as S. And we already get the start point which has deepest depth and denote it as root. And in a DFS from the root, we say a vertex is a leaf if it is selected and none of its children vertexes is selected. If the selected vertexes can build a path, we should have only one leaf if we DFS from the root. So just calculate how many leaves we have. You can check whether this submit is easier to understand: https://mirror.codeforces.com/contest/1702/submission/163945410

»
2 года назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

Problem E:

Code

Which case is my solution missing??

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    1
    6
    1 2
    2 3
    4 5
    3 4
    5 6
    6 1
    

    Your answer is NO.

    Now if we swap the order of input to:

    1
    6
    1 2
    2 3
    3 4
    4 5
    5 6
    6 1
    

    Then, now your answer is YES.

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

solved g1 later since I didn't have time to do in the contest. just bashed it with lca 163805347

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

Can somone please explain to me why when using unordered_map I get TLE and when changed to a normal map it just get accepted.

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

I wanted to mention that F appeared in a recent AtCoder contest: https://atcoder.jp/contests/abc254/tasks/abc254_h

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

Hello,

In problem E, is it obligatory that the two sets must have equal size. If yes, where is problem statement this is written?

Thank you :)

  • »
    »
    2 года назад, # ^ |
    Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

    There are $$$n$$$ dominos with value from $$$1$$$ to $$$n$$$.

    If each number appear exactly twice, both sets must contain all number from $$$1$$$ to $$$n$$$, thus have the size of $$$\frac{n}{2}$$$

    Edit : the size is $$$n$$$, not $$$\frac{n}{2}$$$, my bad

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

My solution to G2 with dfs and range query data structure(BIT for example):

First get the pre-order sequence of the tree, store the time stamp when you enter/exit each node.

For each query, find the node X with max depth, and node Y with min depth.

As described in the solution, X must be one end of the path. Let's enumerate the other end.

We put +1 on the timestamp you enter each node, and range_sum(X,Y) gives us the number of points covered by path X-Y.

Now we enumerate each node Z in the set, skip it if it's on path X-Y(can be determined by timestamp), otherwise see if range_sum(X,Y) + range_sum(Y,Z) = |S| + 1.

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

In problem F, why do we have to take the largest number from array b? The solutions works even if we take random number from b.

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

    I would assume that it would be easier to just start from the largest number. Do you have a proof as to why it would still work even if we just take a random number from b?

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

    I think you start with a larger number, because in the worst case that you divide it, you could still use it for smaller numbers. That's much more efficient than taking smaller numbers, because you don't know if you'll be able to use them again.

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

      tgp07 Can You help where my approach went wrong in problem F ? My basic idea was to reduce every number in array A and B to their largest odd factors (by dividing them 2 as long as possible) and store the values in two different multisets.
      First multiset contains all reduced values of array A.
      The second multiset contains all the reduced values present in array B. Then I would simply iterate over the second multiset and for each value in this multiset I will check if there is a matching value in first multiset.
      If yes then I will delete that value from first multiset else I will further reduce this element further by 2 and again try to match with first multiset as long as this element is > 0. >br> After iterating over all values of 2nd multiset, if first multiset is empty then my answer is YES, otherwise it is NO.

      UPDATE : I figured out the issue, which was due to continue statement in one of my while loops.
      The wrong submission here

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

Can u explain why Graph solution for Problem E works?

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

Average round

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

can someone tell at which test case my code for E fails 186018543

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

In problem F,once we make each element odd in multiset a, then I think it is not necessary to start with largest element in multiset b, we can start with smallest element too since we use only second operation in multiset b.

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

Can anyone be kind enough to see my solution for problem E ones. https://mirror.codeforces.com/contest/1702/submission/237575015 My logic was to check if there is any domino which has both side the same number, if so then output "NO"; else made 2 sets and inserting the number on dominoes after checking if any of the number already exist in any one of them. If so, then output "NO"; else "YES";

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

    Try this test case

    1
    6
    1 6
    3 4
    2 3
    1 2
    5 6
    4 5
    
    • 1 6 -> S1: 1,6 — S2: empty
    • 3 4 -> S1: 1, 3, 4, 6 — S2: empty
    • 2 3 -> S1: 1, 3, 4, 6 — S2: 2 3
    • here when it checks 1 2, it will find 1 in S1 and 2 in S2, so it will output NO while the correct answer is YES. That's because the solution tries to build the 2 sets based on the order of the dominos in the input which is not optimal every time.
»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For the first time, I found problem F in div3 to be very easy

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

Can anyone pls explain G1?