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

Автор flamestorm, 2 года назад, По-английски

We hope you enjoyed the contest! Sorry for the late editorial.

1760A - По середине

Idea: flamestorm

Tutorial
Solution

1760B - Любимая задача Atilla

Idea: SlavicG

Tutorial
Solution

1760C - Преимущество

Idea: Errichto

Tutorial
Solution

1760D - Долины с трудностями

Idea: mesanu

Tutorial
Solution

1760E - Бинарные инверсии

Idea: SlavicG

Tutorial
Solution

1760F - Квесты

Idea: flamestorm

Tutorial
Solution

1760G - Любимая задача SlavicG-а

Idea: SlavicG

Tutorial
Solution
Разбор задач Codeforces Round 835 (Div. 4)
  • Проголосовать: нравится
  • +50
  • Проголосовать: не нравится

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

Such a elegant implementation of problem G

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

I believe C can be done in O(n).

  1. Read everything into array a
  2. Find two maximum values — max and pre_max
  3. Do a run:
for (i in a) 
if (i == max) print(i - pre_max) else print(i - max)
»
2 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

I had the exact same idea for G as the tutorial, But I screwed up the implementation in so many ways

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

    I find 'screwing up in so many ways' very relatable and funny, maybe this should be my spiritual quote!!

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

Why is this code for problem C, getting TLE? Code

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

Damn the problem ratings are so inflated

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

    I think only G and F are inflated, G should be 1500/1600, but then again, for some 1500s and 1600s I think trees are a new topic, so it is normally going to be inflated, while F is just a binary search with a few more steps, so I think it should be 1300/1400.

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

In problem F, I also sort the array in descending order and then I made a prefix sum of n elements. (Let's call it p) We have 3 situations:

1.If (c + p[1] - 1) / p[1] > d then there's no way that we can get c coins in d days.

2.If there is p[i] (i <= d) such that p[i] >= c then any value k satisfies.

3. Brute-force k from d to 0 as k >= d + 1 in this situation is not possible anymore.

Time complexity is O(n log n + d)

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

    Hi, @TrendBattles, If the sum of the entire array is greater than the c coins needed, will that not result in infinity? In case 2: you wrote only for a particular element, why so.?? What if a particular element is not greater than c but the entire array sum is greater?

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

For problem G,unordered_map will give you TLE

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

why does my code get TLE for problem G.

#include <bits/stdc++.h>

using namespace std;

int t;
int n, a, b;





void dfs(int u, int now, int father, vector<vector<pair<int, int>>>& g, unordered_set<int>& st)
{
    if (father != -1)
    {
        st.insert(now);
    }
    for (auto [nxt, w]: g[u])
    {
        if (nxt != father)
        {
            dfs(nxt, now ^ w, u, g, st);
        }
    }
}


bool dfs2(int u, int now, int father, vector<vector<pair<int, int>>>& g, unordered_set<int>& st)
{
    if (st.count(now))
    {
        return true;
    }
    for (auto [nxt, w]: g[u])
    {
        if (nxt != father && nxt != b and dfs2(nxt, now ^ w, u, g, st))
        {
            return true;
        }
    }
    return false;
}



int main()
{
    ios::sync_with_stdio(false);
    cin >> t;
    while (t--)
    {
        cin >> n >> a >> b;
        vector<vector<pair<int, int>>> g(n + 1);
        unordered_set<int> st;
        for (int i = 0; i < n - 1; i++)
        {
            int u, v, e;
            cin >> u >> v >> e;
            g[u].push_back({v, e});
            g[v].push_back({u, e});
        }
        dfs(b, 0, -1, g, st);
        if (dfs2(a, 0, -1, g, st))
        {
            cout << "YES" << endl;
        }
        else
        {
            cout << "NO" << endl;
        }
    }

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

How does G solution take care of 2 things?

1.) We may never need to teleport and just reach end node with value 0. In that case inside dfs2, we need to have a condition for that.

2.) I don't see where is the condition to not go beyond end node in dfs2 when we don't get true before reaching end node.

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

    1.) We may teleport from a to a. Consider the following graph Let's say we start at node 1 and need to end at node 3.

    (n) node

    -w- connection with weight w

    (1) -2- (2) -2- (3)
    

    It isn't optimal to teleport to any node however we can compare path from 1 to 2 having XOR value = 2 and path from 3 to 2 having the XOR value equal to 2. In that case we don't teleport but if we had to, we would teleport from node 2 to node 2.

    Alternatively what the functions actually checks is all the possible XOR values starting from a and b. If there is a match answer is yes, else no. In our case we have 2 matches, 0 and 2.

    We get 0 at the start because that's our starting value and 2 by traveling from node 1 to 2. When starting from b we get 0 by traveling from node 1 to 3 and value 2 by traveling from 3 to 2.

    2.) dfs2 starts at node b

        if(dfs2(b, -1, 0)) cout << "YES\n";
        else cout << "NO\n";
    

    It checks if it can hit any optimal values calculated in dfs1. In dfs1 all possible values are calculated where we have the limitation in place.

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

Awesome round.

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

any idea why I'm getting wa2 in e?

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

    It getting WA because of two things:-

    1. You need to handle the case in which you will not do any operations.

    2. Function cal() needs to return long long, because in the worst case ans = (10^10), this will cause overflow of course.

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

someone please explain "Also, we cannot pass b on the path from a→c." in tutorial of G.

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

    It refers to the fact we cannot pass through the node b (end node) when starting dfs from a. Because it's impossible to enter b without our value being 0.

    See the problem statement

    you are allowed to enter node b if and only if after traveling to it, the value of x will become 0.

    In other words, you can travel to node b only by using an edge i such that x XOR wi=0.

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

Can somebody please explain why i am getting WA 182023139 in G . I am storing xor from starting to ending node in a variable then from every node we can go to ending node . and xor will be xor of node from starting to xor of starting to end and then checking if it exists in our set or not.

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

In 1760D - Долины с трудностями you could also insert INF at the start and at the end of the processed array (without successive equal elements) to simplify the job with edges, then check every triplet inside for a[i-1]>a[i]<a[i+1], 182365763

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

Could someone point out where my code fails? ato[i] is xor value of path from a to i. 184338941

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

why does this code fails 185000763 for G.

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

Solved F in O(n) using prefix sum — Code

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

why my solution is failing on test 2 iteration number 53 code

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

Problem G unordered_set gives TLE but set solution Accepted. I also faced similar issues in other problems as well. Can anyone explain me why this is happening ?

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

I have tried stress testing my solution to problem G, and I haven't yet been able to find a test case that breaks my code. Can anyone please take a look at this? 188826168

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

Anyone could help me look at what's the problem of my solution 193477917 for G.

Thanks a lot in advance!

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

202246684 Can anyone tell me why this submission for problem G fails for test 53?

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

G is the best problem

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

I have used a dfs approach for G,but my code is not working,can someone help me with the debugging the following submission, https://codeforces.me/contest/1760/submission/226432202

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

G :/

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

t = int(input()) for _ in range(t): n = int(input()) s = input() a = "abcdefghijklmnopqrstuvwxyz" l = max(s, key=ord) print(a.index(l)+1)

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

in tutorial text for F, shouldn't maximum value for k be d, as we are allowed to not pick a quest on a day, if we run out of quests?