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

Автор awoo, история, 8 часов назад, По-русски

2004A - Ближайшая точка

Идея: BledDest

Разбор
Решение (BledDest)

2004B - Игра с дверьми

Идея: BledDest

Разбор
Решение (Neon)

2004C - Делим предметы

Идея: BledDest

Разбор
Решение (adedalic)

2004D - Цветные порталы

Идея: BledDest

Разбор
Решение (Neon)

2004E - Это не задача про ним

Идея: BledDest

Разбор
Решение (BledDest)

2004F - Сделай палиндром

Идея: BledDest

Разбор
Решение (Neon)

2004G - Сжатие подстрок

Идея: BledDest

Разбор
Решение (awoo)
  • Проголосовать: нравится
  • +13
  • Проголосовать: не нравится

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

finally it is released.!!!

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

In D, also you can use bellman-ford after construct a graph: 276620074

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

The implementation / logic of F makes me feel I am the dumbest man on planet.

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

    Same, it is very unintuitive for me how you can just add the cumsums; This implementation makes a lot more sense to me: 276838911

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

Отличные задачи! Особенно понравилась D) Довольно сложная, чтобы задуматься, но при этом решаемая.

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

can someone explain to me what is wrong with my solution of problem C : 276692116

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

    It is actually causing Overflow, check your output. You can see negative value. When we add positive numbers, we can never get negative values, unless you got memory overflow.

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

    I faced something like this... maybe using Long Long can fix it.

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

Здравствуйте, в разборе задачи D опечатка.

X < Z < Y

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

Hello ..

Can anyone tell me that for problem D , why this solution is giving wrong answer https://mirror.codeforces.com/contest/2004/submission/276820238 or can anyone suggest some test cases where this failed

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

    You can actually find the failing test yourself.

    Checker's output says "wrong answer 248th numbers differ — expected: '3', found: '-1'". That means you only need to add something like "if (test_id == 248) then print(all input)" to your code (and don't print anything else so that the output is not too large). The verdict will still be WA but at least you'll get to see the problematic test.

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

      damn, i was actually looking for something like this thanks

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

      It says 248th number, and not 248th testcase. So we don't know which testcase number it really falls under :(.

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

    you are considering wrong combination of string to search. i.e) if temp1 is RY and temp2 is BG then your first combination would be RB which is not possible

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

    Take a look at Ticket 17471 from CF Stress for a counter example.

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

В разборе задачи B ошибка — сказано, что в отрезке пересечения min(R,r)-max(L,l)-1 дверей, на самом деле их min(R,r)-max(L,l).

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

finally the text editorial is here, still waiting for rating recalculation :(

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

can anyone tell why this solution for problem D is giving tle ?

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

why did problem E get so much hate and backlash ? the problem is actually really nice and high quality even tho there were 10+ videos that leaked the solution first hour which had nearly 5k views combined that doesnt take from the quality of the problem i honestly found it really interesting and gives a new way of approaching problems atleast for me

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

    I said the same in original Contest post. and guess what, heavily downvoted. I would say it again. E was a nice problem.

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

      i think they are missing the core idea tbh i always underrated trying to prove facts from realizing a pattern but this problem proves that sometimes looking at the pattern and trying to build intuition then proving it (proofs for this problem are really easy and i 100% believe most experts+ will be able to reason enough to prove the pattern) actually is a valid idea and sometimes solves even hard problems

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

    ik this is off topic but wow dude how did you go from grey to purple in less than a year? as someone who's given about 5 contests it looks lowkey impossible for someone like me

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

In the editorial for problem F, it is written that: "It can be shown that it doesn't matter which of these actions we take".

Please mention in the editorial how it can be shown. I have an intuition for this, but I don't have a rigorous proof.

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

    i dont get this part aswell if u understand it please explain it below here

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

    A rigorous proof would be something like that:

    Consider the prefix sums of an array, and denote $$$s$$$ as the sum of all elements in it. An array of positive integers is palindromic if and only if its prefix sums are "symmetric" with $$$\frac{s}{2}$$$ as the center (i.e. if an integer $$$\frac{s}{2} + x$$$ exists in the array of prefix sums, then the integer $$$\frac{s}{2} - x$$$ should also exist, and vice versa). If there is a pair $$$(\frac{s}{2}-x, \frac{s}{2}+x)$$$ such that only one of these elements exists in prefix sums, this pair violates the condition, and we need to "fix" every such pair.

    Now consider what our actions do to the array of prefix sums. When we merge two adjacent elements, we delete a prefix sum. When we split an element, we add a new prefix sum between the existing two. Every such action can "fix" one of the violating pairs $$$(\frac{s}{2}-x, \frac{s}{2}+x)$$$: merging two elements deletes one element from a pair, and splitting an element adds an element into the pair. So, if we have a pair that violates the condition, it doesn't matter whether we fix it by split operation or merge operation — we will still spend one operation to fix this pair.

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

Any idea why this submission for Problem D is going TLE? As per my understanding, the time complexity for this should be O(q * 6 * logn) which should be within limits I guess. Thanks in advance!

https://mirror.codeforces.com/contest/2004/submission/276826924

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

    Ok I see, issue was with 1., deep copying of vector. 2. Solves it. So dumb, it was going to be the first time I solved a D in div 2!!

    1.vector<int> nodes = colorToNodes[all_colors[j]];

    2. vector<int>& nodes = colorToNodes[all_colors[j]];

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

Can anyone please correct my code for D please request help me out ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ void solve() { int n, m; cin >> n >> m; vector v(n+1);

for(int i = 1; i <=n; i++) {
    cin >> v[i];
}

while (m--) {
    int a, b;
    cin >> a >> b;


    if (v[a][0] == v[b][0] || v[a][1] == v[b][1] || v[a][1] == v[b][0] || v[a][0] == v[b][1]) {
        cout << abs(a - b) << endl;
    } else {
        // if(n > 2) {
            int pos = -1;
            int pos2 = -1;
            int ans = INT_MAX, ans2 = INT_MAX;


            int maxi=max(a,b);
            int mini=min(a,b);
            for(int i = 1; i< maxi; i++) {
                if(v[i][0] == v[maxi][0] || v[i][1] == v[maxi][1] || v[i][1] == v[maxi][0] || v[i][0] == v[maxi][1]) {
                    pos = i;
                }
            }

            for(int i = maxi + 1; i <=n; i++) {
                if(v[i][0] == v[mini][0] || v[i][1] == v[mini][1] || v[i][1] == v[mini][0] || v[i][0] == v[mini][1]) {
                    pos2 = i;
                    break;
                }
            }


            if(pos != -1) {
                ans = abs(maxi - pos)+abs(pos-mini);
            }
            if(pos2 != -1) {
                ans2 = abs(mini - pos2)+abs(pos2-maxi);
            }

            int final_ans = min(ans, ans2);
            if(final_ans != INT_MAX) {
                cout << final_ans << endl;
            } else {
                cout << -1 << endl;
            }
        // } else {
            // cout << -1 << endl;
        // }
    }
}

} ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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

I thought of applying dfs for D but will it give tle?

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

    probably yeah

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

    Yes. If you're checking every possible index, then time complexity will be approximately O(N*Q) because in the worst case, let's say, you will be getting the same x and y each query, and every other string will be suitable. Then, for each query you will be checking N-2 elements. Rounding up, it is N*Q

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

    It will be o(nq) so yeah

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

When will rating update?

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

Can someone tell me why my code here isn't necessarily correct? 276831391

I understood the idea quite well, as you essentially need to check if there exists a city in between x and y, as well as if the closest two cities not in the range to x and y respectively, but I'm not certain why my above submission is WA, while this submission 276831747 is.

Thanks in advance :D

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

    Take a look at Ticket 17468 from CF Stress for a counter example.

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

      I see, I understand what I was doing wrong now. In my head I thought I was checking the two possible city locations, but I guess my code didn’t reflect that :/. Thank you very much!

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

Idk how the B task was for you guys. But for me, as a beginner, it's very tricky.

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

    To be honest, I was also confused by this problem. I tried to solve it by math first, but decided to just write brute force.

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

Hello ...

https://mirror.codeforces.com/contest/2004/problem/D

Could anyone tell why this is giving TLE for Problem D and how could i improve .

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

I always skip problem C. Every contest, If I can not come up with solution as soon as I read problem C then I used to skip it. Then I would solve the next problem D. Educational Codeforces Round 169 is one example. I skipped D, then solved E. And in the EPIC Institute of Technology Round August 2024 (Div. 1 + Div. 2), I skipped C, then solved E. After contest, I was disappointed that I did not solve C. Could anyone explain me about this? I can not sure the reason.