awoo's blog

By awoo, history, 6 hours ago, translation, In English

2004A - Closest Point

Idea: BledDest

Tutorial
Solution (BledDest)

2004B - Game with Doors

Idea: BledDest

Tutorial
Solution (Neon)

2004C - Splitting Items

Idea: BledDest

Tutorial
Solution (adedalic)

2004D - Colored Portals

Idea: BledDest

Tutorial
Solution (Neon)

2004E - Not a Nim Problem

Idea: BledDest

Tutorial
Solution (BledDest)

2004F - Make a Palindrome

Idea: BledDest

Tutorial
Solution (Neon)

2004G - Substring Compression

Idea: BledDest

Tutorial
Solution (awoo)
  • Vote: I like it
  • +15
  • Vote: I do not like it

»
5 hours ago, # |
  Vote: I like it +2 Vote: I do not like it

finally it is released.!!!

»
5 hours ago, # |
  Vote: I like it +12 Vote: I do not like it

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

  • »
    »
    4 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you explain your construction of graph?

»
5 hours ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    112 minutes ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
5 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      5 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yeah, in accumulate i had to write 0ll instead of just 0. Thanks.

  • »
    »
    5 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
5 hours ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      4 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      damn, i was actually looking for something like this thanks

    • »
      »
      »
      3 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        2 hours ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        Then you could replace test_id == 248 with query_id == 248

  • »
    »
    4 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

  • »
    »
    3 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
4 hours ago, # |
  Vote: I like it +2 Vote: I do not like it

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

»
4 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    youre using maps and sets a bit too much probably

    • »
      »
      »
      4 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      ig time complexity is O(q*4*log(n)) which should not give TLE

      • »
        »
        »
        »
        4 hours ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        ohh yeah, you just have to add & before st "for(auto st:mp[a[x]])", i just added the & and it passes 276829023. by adding &, you iterate over the elements by reference which is much faster.

  • »
    »
    4 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    change auto st to auto& st

»
4 hours ago, # |
  Vote: I like it +20 Vote: I do not like it

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

  • »
    »
    4 hours ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    • »
      »
      »
      4 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

  • »
    »
    4 hours ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      3 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      it also looked impossible for me after 5 contests but after 60 u will realize its not

»
4 hours ago, # |
Rev. 10   Vote: I like it +4 Vote: I do not like it

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.

  • »
    »
    4 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 hours ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

»
4 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    105 minutes ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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]];

»
4 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 hours ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    probably yeah

  • »
    »
    3 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

  • »
    »
    2 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It will be o(nq) so yeah

»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      2 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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!

»
2 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    74 minutes ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    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.

»
77 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

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 .