awoo's blog

Educational Codeforces Round 169 Editorial
By awoo, history, 3 months 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
  • +64
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it +3 Vote: I do not like it

finally it is released.!!!

→ Reply
»
3 months ago, # |
  Vote: I like it +15 Vote: I do not like it

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

→ Reply
»
3 months 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.

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +19 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

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

      I like this kind of solution. This solution is completely different from author's solution.

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

      Can someone please explain this marked solution? How is looking at the difference in the prefix sums giving the answer? The ranges (i,j) with same Prefix sums can be completely disjointed after all

      → Reply
      • »
        »
        »
        »
        2 months ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        What do you mean by disjoint? Lets denote the first range as $$$i_0$$$-$$$j_0$$$ and the second one as $$$i_1$$$-$$$j_1$$$. We can only account for $$$i_0 < i_1$$$, Also we can say $$$j_0 < j_1$$$ because other ways the second range will always have smaller sum than the first.

        This means that the first range always describes a prefix and the second one a suffix, that have a unique start and end point. Now it is just counted how often they are the same.

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

    Enjoy the process in thinking problems.

    → Reply
»
3 months 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

→ Reply
  • »
    »
    3 months 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.

    → Reply
    • »
      »
      »
      3 months 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.

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

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

    → Reply
»
3 months 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://codeforces.me/contest/2004/submission/276820238 or can anyone suggest some test cases where this failed

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +3 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.

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

      damn, i was actually looking for something like this thanks

      → Reply
    • »
      »
      »
      3 months 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 :(.

      → Reply
      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

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

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

          Can you explain more clearly how to do this ?

          where to put test_id ?

          → Reply
          • »
            »
            »
            »
            »
            »
            3 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            You can do something like this
            → Reply
            • »
              »
              »
              »
              »
              »
              »
              3 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              it won't work for failure on large tests.. like my this submission failing on some 27610th test case... that much input is also not available on that test case..

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

              ohk thanks

              but it won't work for system

              tests as it will wrong answer

              on querry no. 248 of some previous test case and programm will itself terminate

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

          can you explain a bit more? Like how & where to do it?

          → Reply
    • »
      »
      »
      3 months ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      Hey could you please tell what am i missing in this D problem :- 276639203. This got WA .

      But this got AC :- 276654708

      Could you please tell what is the difference

      → Reply
  • »
    »
    3 months 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

    → Reply
  • »
    »
    3 months 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.

    → Reply
»
3 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 months ago, # |
  Vote: I like it +54 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

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +16 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.

    → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +8 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

      → Reply
  • »
    »
    3 months 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

    → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

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

      → Reply
»
3 months ago, # |
← Rev. 10   Vote: I like it +9 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.

→ Reply
  • »
    »
    3 months 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

    → Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +26 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.

    → Reply
  • »
    »
    3 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    I think a rigorous proof might also go like this:

    Given the array $$$b[1\cdots n]$$$ after doing the minimum number of operations to make it a palindrome.
    While possible, pick any element $$$b_i$$$ that was obtained by a split operation, and do the following:

    $$$ \textbf{Case 1:} \text{ if } i > \left\lceil \frac{n}{2} \right\rceil \text{or } i < \left\lfloor \frac{n}{2} \right\rfloor \text{, undo the split operation in any possible direction, and fuse } b_{n - i + 1}$$$
    $$$\text{in the opposite direction that } b_i \text{ got unsplit towards.This increases the number of operations by at most 0.} $$$

    $$$ \textbf{Case 2:} \text{ if } i = \left\lceil \frac{n}{2} \right\rceil \text{or } i = \left\lfloor \frac{n}{2} \right\rfloor \text{, do the same as case 1 but if the direction of unsplit of } b_i \text{ is towards } b_{n - i + 1}$$$
    $$$\text{don't do anything after the unsplitting step. This also increases the number of operations by at most 0.} $$$

    $$$ \textbf{Case 3:} \text{ if } i = \frac{n}{2} \text{, unsplit } b_i \text{ and fuse the result in the opposite direction.} $$$

    Note: when you fuse two elements $$$b_i$$$ and $$$b_j$$$, the state of the resulting element is the union of the split directions of $$$b_i$$$
    minus the direction $$$b_i \rightarrow b_j$$$ and the split directions of $$$b_j$$$ minus the direction $$$b_j \rightarrow b_i$$$.

    This process has to end because in each iteration you decrease the number of split elements by at least 1.

    A similar argument can be constructed to convert all fuse operations to split operations.

    → Reply
»
3 months 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://codeforces.me/contest/2004/submission/276826924

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +3 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]];

    → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    probably yeah

    → Reply
  • »
    »
    3 months 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

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

    It will be o(nq) so yeah

    → Reply
»
3 months 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

→ Reply
  • »
    »
    3 months 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.

    → Reply
    • »
      »
      »
      3 months 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!

      → Reply
»
3 months 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.

→ Reply
  • »
    »
    3 months ago, # ^ |
    ← Rev. 2   Vote: I like it +8 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.

    → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello ...

https://codeforces.me/contest/2004/problem/D

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

→ Reply
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    In this line 

    set<int> temp=m[s];

    you're copying a whole set which maximum size can be $$$2 \cdot 10^5$$$. Potentially this copy can be done for each query (again $$$2 \cdot 10^5$$$) and moreover a function solve() is called 8 times for every query.

    If you really need this temporary variable, you can use a const reference:

    const set<int>& temp=m[s];
    → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For G, how do you get the digit you placed in the last odd block if in your transition you put a dummy state c=0? Thanks!

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

    I was thinking of it like that. If you are in a state with $$$c > 0$$$, you are always placing the next (the $$$i$$$-th) digit into an even block. And you always add $$$c$$$ to the answer with that. You can opt to go to $$$\mathit{dp}[i + 1][0]$$$, telling the $$$(i + 1)$$$-st digit to be in an odd block. With that, you'll know that digit when you are in that state.

    → Reply
»
3 months ago, # |
  Vote: I like it +3 Vote: I do not like it

so slow

→ Reply
»
3 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Idiot me, who wrote 500 lines of code in D :] 276672729

→ Reply
»
3 months ago, # |
  Vote: I like it -7 Vote: I do not like it

Can anyone please correct my code for D ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~` 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 {

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

    }
}

} ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~`

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please tell what am i missing in this D problem :- 276639203. This got WA .

But this got AC :- 276654708

Could you please tell what is the difference

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can some1 please help me understand why this won't work for prob C??

https://codeforces.me/contest/2004/submission/276886399

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

    In your code inside accumulate function you are declaring 0 as L i.e Long int but for large values you must declare it as 0LL i.e Long Long, rest everything is correct.

    Link for corrected code: Solution

    → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain editorial of e , i read it many times still i didn't get approach , i understand concept of nim problem because there are alot of editorial are exists already but i'm not getting approach of this problem can anyone explain please ??? thanks

→ Reply
»
3 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

F. Can you tell me in more detail what what the line means: ans -= (s % 2 == 1 || !binary_search(p.begin(), p.end(), s / 2)); As far as I understand, this is a check for a palindrome of odd length. But why there are two checks here is not quite clear.

→ Reply
  • »
    »
    7 days ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    If S is not specifically determined to be odd, then S/2 will automatically be rounded down, which may cause some problems.

    → Reply
»
3 months ago, # |
  Vote: I like it +6 Vote: I do not like it

In problem E tutorial's induction proof, author writes "if x is a composite prime number", this should be corrected to "if x is an odd composite number".

Great explanation otherwise :)

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.me/contest/2004/submission/276672351

this solution is O(n+q) but still gave TLE just because I was using python

→ Reply
»
3 months ago, # |
  Vote: I like it +3 Vote: I do not like it

I had some trouble grasping that the solution for F actually worked (going in increasing order through sizes of segments) because I thought you could end up counting disjoint segments. But all the elements being non-negative makes that impossible, that is, all arrays with equal p[l] + p[r] are one inside of the other.

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone pls explain the idea behind D solution once again

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Who can tell me why, in problem F, when the sample input is 1 2 3 4 4, the result is 18 instead of 15?

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone help me with D,I failed in the test 2 2651th number for lots of times:#277004006

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Good problems!

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can we get hidden testcases like we can get in cses problemset

→ Reply
»
3 months ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

where is my code getting wrong for problem D? Link to submission

based totally on tutorial idea

UPDATE:- ok, got the problem, it is giving -1 for this test case:

4 1
BY RY RY BG
3 4

answer should be 5, my bad :(

My Code
→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

please help me with this 277073432 it will be very helpful

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

    Use V<int> &ds = mp[temp[i]] instead of V<int> ds = mp[temp[i]] at Line 98 to avoid copy.

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

      can you please provide some reason for this it will be very helpful for me in future cases

      → Reply
»
3 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Nevermind, All this time in problem F, I thought we're asked to form a "PERMUTATION" NOT PALINDROME

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm very curious why my code with primitive array in java 8 should get timelimit in 21 tests int a []. But the same code with Integer a[] should pass all tests and should be accepted the same logic. Can someone explain me why is that in java solutions.

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

    In Java 13 and earlier versions, Arrays.sort for primitive types doesn't guarantee $$$O(n\log n)$$$. You can refer to this and this.

    → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Sorry, I am dumb in F what does the ans minus two values represent?

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I tried all source shortest path (Floyd-Warshall) in D and apparently got tle. There have been many problems that I tried to solve with the algorithm yet failed again and again at the time limit. Can anyone tell me better approach to solve problems like these? (and also if there is a faster variant of the algorithm)

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

    It will TLE. There is no cutting corner around Floyd-Warshall that would help you, the algorithm is doing its best (sort of, this is excluding any research paper improving it to an extreme, but as far as I understand, this cannot have a better complexity than quadratic).

    D is more of an exercise to practice implicit graph. That is, you know what you are solving is a graph, but it has special attributes that you should take advantages of instead of blindly jumping into a regular graph algorithm just because you deduce "shortest path" from the problem statements.

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

      What are the other implicit graphs properties are like? I think this codechef problem has also graph/tree like properties yet still my methods leads to tle.

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

        Yes, your example is one out of many incidents. The vague term "implicit graph" simply implies a graph by concept and formulaic constraints — there is no fixed algorithm to solve them all since each constraints would leave different observations/loopholes that contestants must figure out.

        → Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why algorithm described in solution for F problem is optimal? function f(l, r) is defined as minimum operations required to make a palindrome from a[l..r]. there's no proof in solution. can you explain it plz BledDest?

→ Reply
»
3 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

In the tutorial for problem E (Not a Nim Problem), the last paragraph says "if x is a composite prime number...", is this probably a typo? I think it would be correct to write "if x is an odd composite number..."

upd: I saw such a comment with such content, I apologize

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello guys! Can someone tell me if it was possible to solve D using a graph + Dijkstra's algorithm? For some reason I have some problems)

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it 
If z < x < y
ans = (y - z) + (x - z) = (x + y) - 2* z
Considering z = (x - a)
ans = (x + y) - 2 * (x - a)
    = x + y - 2x + 2a
    = y - x + 2a.  eq(1)

If x < y < z
ans = (z - y) + (z - x) = 2z - (x + y)
Considering z = (y + a)
ans = 2 * (y + a) - (x + y)
    = 2y + 2a - x - y
    = y - x + 2a   eq(2)

From eq(1) and eq(2) it is clear that z can be either close to x or close to y and it should not matter. I don't understand how is D being solved.

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

~~~~~~~~~~~~~~

include <bits/stdc++.h>

using namespace std;

define ll long long

define pb push_back

define MOD1 1000000007

define MOD2 998244353

define NO cout << "NO" << endl

define YES cout << "YES" << endl

ll expo(ll a, ll b, ll mod) {ll res = 1; while (b > 0) {if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b = b >> 1;} return res;} ll mminvprime(ll a, ll b) {return expo(a, b — 2, b);} ll mod_add(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a + b) % m) + m) % m;} ll mod_mul(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a * b) % m) + m) % m;} ll mod_sub(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a — b) % m) + m) % m;} ll mod_div(ll a, ll b, ll m) {a = a % m; b = b % m; return (mod_mul(a, mminvprime(b, m), m) + m) % m;} void print(vector &ans){for(auto x: ans) cout<<x<<" "; cout<<endl;} void input(vector &v,int n){for(int i=0;i<n;i++){int e;cin>>e;v.pb(e);}} //===========================================================================================

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~```

void solve(vector &a,int n,int k){ sort(a.begin(),a.end(),greater<>()); ll i=1; while(i<n && k>0){ a[i]+=min(a[i-1]-a[i],k); k-=min(a[i-1]-a[i],k); i+=2; } ll alice=0,bob=0; for(int i=0;i<n;i++){ if(i%2==0){ alice+=a[i]; } else bob+=a[i]; } cout<<(alice-bob)<<endl;

}

int main(){ int T;cin>>T;

while(T--){
    int n,k;cin>>n>>k;
    vector<int> a;
    input(a,n);



    solve(a,n,k);

}

}

Can someone please point out the mistake in my code?

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello， can someone tell me in f, why the ans should do ans -= (s % 2 == 1 || !binary_search(p.begin(), p.end(), s / 2)); ?? Thanks!

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey guys, I don't know why my solution for C got TLE. Can anyone tell me where it went wrong? Thank you ^^

→ Reply
  • »
    »
    3 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Avoid using custom comparator function, instead using inbuilt greater () function to sort the array in descending order, as:

    The use of a custom comparator function introduces additional overhead due to function calls, which becomes significant when sorting large arrays. On the other hand, greater() is a highly optimized standard library component that avoids this overhead, leading to better performance and preventing TLE (Time Limit Exceeded) in competitive programming or performance-critical applications.

    In most cases, prefer using standard library comparators like greater() for better performance unless you need custom behavior that can’t be achieved otherwise.

    link for corrected solution: https://codeforces.me/contest/2004/submission/277758988

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

    Same problem: TLE 9 in 280240613 I'm using built-in qsort and have no idea how to speed this code up...

    → Reply
»
3 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

// This is Code ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

void sol(){
    ll n,q;
    cin>>n>>q;
    std::vector<string> v(n);
    vector<vector<int>>u(6);
    unordered_map<string,int>m;
    m["BG"]=0;
    m["BR"]=1;
    m["BY"]=2;
    m["GY"]=3;
    m["GR"]=4;
    m["RY"]=5;
    for (int i = 0; i < n; ++i)
    {
        cin>>v[i];
        u[m[v[i]]].push_back(i);
    }
    // for(auto a:u){
    //     for(auto b:a)cout<<b<<" ";
    //         cout<<endl;
    // }
    for (int i = 0; i < q; ++i)
    {
        int a,b;
        cin>>a>>b;
        // cout<<a<<" "<<b<<endl;
        a--;
        b--;
        unordered_map<char,int>mp;
        mp[v[a][0]]++;
        mp[v[a][1]]++;
        if(mp.find(v[b][0])!=mp.end() || mp.find(v[b][1])!=mp.end()){
            cout<<abs(a-b)<<endl;
            continue;
        }
        else{
            string s=v[a],t=v[b];
            int ans=INT_MAX;
            for (int i = 0; i < 2; ++i)
            {
                for (int j = 0; j < 2; ++j)
                {
                    string temp;
                    temp+=s[i];
                    temp+=t[j];
                    vector<int>vec;
                    if(m.find(temp)!=m.end())vec=u[m[temp]];
                    else {
                        reverse(temp.begin(),temp.end());
                        vec=u[m[temp]];
                    }
                    if(vec.size()==0)continue;
                    // sort(vec.begin(),vec.end());
                    auto it =upper_bound(vec.begin(),vec.end(),a);
                    if(it!=vec.end())ans=min(ans,abs(*it-a)+abs(*it-b));
                    if(it!=vec.begin())ans=min(ans,abs(*(it-1)-a)+abs(*(it-1)-b));
                }
            }
            if(ans==INT_MAX)cout<<-1<<endl;
            else cout<<ans<<endl;
        }
    }
    return;
}

int main(){
    int t;
    cin>>t;
    while(t--){
        sol();
        // cout<<endl;
    }
}
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
// Rest text
why it's give TLE on testcase 15 [submission:277746211]

746211

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Did anyone try to solve D with using BFS?

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

278709370 can someone pls help me why my code always gets wrong answer at test 422

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone find the issue with this Code for the Problem D?

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

problem B was beautiful

→ Reply