Vladosiya's blog

Codeforces Round #888 (Div. 3)
By Vladosiya, history, 16 months ago, translation, In English

Hello! Codeforces Round 888 (Div. 3) will start at Jul/25/2023 17:35 (Moscow time). You will be offered 6-8 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating of 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of open hacks.

You will be given 7 problems and 2 hours and 15 minutes to solve them.

Note that the penalty for the wrong submission in this round is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participant of the third division, you must:

  • take part in at least five rated rounds (and solve at least one problem in each of them)
  • do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Problems have been created and written by our team: myav, Aris, Gornak40, senjougaharin and Vladosiya.

We would like to thank:

  1. MikeMirzayanov for Polygon and Codeforces platforms.

  2. tute7627 for red testing

  3. oversolver, sevlll777, pavlekn, zwezdinv, Sokol080808, 74TrAkToR, vladmart, EJIC_B_KEDAX, Vladithur, KseniaShk, Be_dos for yellow testing

  4. moonpie24, FBI, meowcneil, NintsiChkhaidze, Phantom_Performer, SashaT9, spike1236, Kalashnikov for purple testing

  5. TheGoodest, Pa_sha, Sasha0738 for blue testing

  6. Syuzi777, Tahseen for cyan testing

Good luck!

UPD: Editorial

  • Vote: I like it
  • +265
  • Vote: I do not like it

Comments Comments (206)
| Write comment?
»
16 months ago, # |
  Vote: I like it +9 Vote: I do not like it

May 19, 2023 what

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

hoping to solve atleast 3 problems

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

it's ironic that all the testers are not actually eligible for div 3...

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

    except cyan ones

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

      cyan wasnt there when i posted the comment lol

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

Hoping to become Expert in this round

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

why is there no cyan, green or gray testers?

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

i hope to be blue this time

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

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

    A better version of the above given meme.

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

    but, rainboy is blue.

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

      color doesn't matter the thing that matters is your coding skills

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

        Yes Yes Color doesn't matter but what matters is Common sense which I can see is not common in you.
        If you would have checked you would have known that rainboy is blue not purple, or are you color blind.

        Regards;
        Aiman.

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

          rainboy's rating is changing fast, used to be purple, and this picture may be outdated, so you cannot say he/she is color blind (rainboy, on Jul 23, 2023; rainboy, on Jul 16, 2023; rainboy, on Jul 11, 2023; rainboy, on Jun 24, 2023).

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

      rainboy's rating is changing fast, and used to be purple (rainboy, on Jul 23, 2023; rainboy, on Jul 16, 2023; rainboy, on Jul 11, 2023; rainboy, on Jun 24, 2023).

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

I have a really good feeling about that this would be my last rated Div. 3 contest and I would have become a blue expert after this 888ᵗʰ round of Codeforces!! May the Force be with us

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

I have exam (TT — TT)

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

    Obviously, exams cannot be compared to codeforces :) Give up exams and choose to fail, embrace Div. 3

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

      yaaaa Now,Let's ditch the exams and embrace our coding superpowers! (っ▀¯▀)つ

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

Hopefully, we will see a problem connected with number $$$8$$$, lol.

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

I think most of Div.3's are made by Vladosiya

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

div3

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

best part of the comment section is I see anime pfpS and discover new interesting animes

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

I think this will be a good one

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

I hope this round will be the great round of Div.3!

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

Good luck

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

Out of competition, but I'll try my best to do it ^_^

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

It is so good to have a contest every few days, hopefully i can cross 1500 today

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

I don't know if this is the right place to say this, but I've noticed for a while now that div3 round announcements say that you can only qualify as a trusted div3 participant if you "do not have a point of 1900 or higher in the rating." Shouldn't that number be 1600 instead?

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

    I think this is a translation error. My understanding (from the original announcement of the trusted participant system) is that you must never have had a rating above 1900. In other words, if your rating is above 1900 at one point but then falls below 1600, Div. 3 rounds will be rated for you, but you will not appear in the official standings.

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

Experts to lower rankings in Div.3 be like:

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

After playing div2,I feel that div3 and div4 are still suitable for me

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

Tends to Pupil:)

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

In first line of blog "You will be offered 6-8 problems" .Later "You will be given 7 problems and 2 hours and 15 minutes to solve them ".So, 7 problems will be there ?.

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

It's fun that the round will be rated for me.

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

    tbh I don't see it as fun because you may become cm today by spamming div-3 , I think div-3 should be unrated for participants if they are >=1600 during participation even if they registered for div-3 when <1600

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

      But I won't be in this contest because my mom doesn't let me stay up all night.

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

        come on bro stay up , don't be a mommy's kid

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

        Why do you have to stay up all night? Look at tourist. Maybe he just need to wake up and spend about just only half an hour to ac this contest (equal to the time i understood problem E). Maybe u can follow that way :D.

        J4F

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

hope to be specialist in this contest

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

I am at the lowest confidence in my life.

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

Good Luck everyone

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

I will solve atleast 5 problems.

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

so she knows what awaits her. emmmmmmhahahahaha~

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

Thank you Vladosiya very much. This is the best Div.3 contest I've ever written.

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

Why I an rated ??????

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

Readforces

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

    my guy only read A and decided to conclude the entire contest was readforces

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

      It is still readforces because half the time I'm trying to decipher what the problems are saying, the statements can definitely be phrased better which a lot of people have mentioned also

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

        readforces isnt unclear wording, its when u got paragraphs upon paragraphs for a problem statement

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

Yes/NoForces

→ Reply
»
16 months ago, # |
← Rev. 2   Vote: I like it +41 Vote: I do not like it

D: Let difference d[0]=a[0], d[i]=a[i]-a[i-1] when i>0. If the missing prefix sum is n*(n+1)/2, then {d[i]} will be a permutation of [1, n] missing one element. Therefore, for this case we need to check in {d[i]} are pairwise distinct and inside range [1, n]. Otherwise, we will have a[n-1]=n*(n+1)/2, and n-2 elements of {d[i]} will be inside [1, n] and distinct, the last element will be the sum of 2 missing elements. So for this case we need to check if {d[i]} contains n-2 different numbers inside [1, n].

E: First for potions with infinite supply we can just set their cost to 0. Then, if potion i can be obtained mixing {j[1], j[2], ...}, we add a directed edge (j[t] --> i) for each j[t]. Since no potion can be obtained by mixing itself, these edges will from a DAG (directed acyclic graph), and we can run dp on the topological order of the DAG: Let dp[i]=sum(cost[j]) where edge (j --> i) exists, and cost[i]=min(cost[i], dp[i]).

F: If a[i], a[j] and x have only 1 bit, then if a[i]==0, a[j]==0, we can set x=1 then (a[i]^x)&(a[j]^x)=1, if a[i]==1, a[j]==1, we can set x=0 then (a[i]^x)&(a[j]^x)=1, if a[i]!=a[j], no matter how we set x, (a[i]^x)&(a[j]^x)=0. So we need to find (i, j) such that a[i]==a[j]. For general cases, we need to minimize (a[i]^a[j]) so that sum(t: 0<=t<k, the t-th bits of a[i] and a[j] are same)(1<<t) = (1<<k)-1-(a[i]^a[j]) is maximized. This can be processed using a trie, or sort a[i] and find the minimal a[i]^a[i+1].

G: For a single query (a, b, e), the maximum height of nodes on the path cannot exceed h[a]+e, which means, we can pass an edge (u, v) if max(h[u], h[v])<=h[a]+e. Therefore, we can sort queries by h[a]+e and sort edges by max(h[u], h[v]), then solving queries using dsu.

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

    F can be solved by property of xors:

    min(x^y, y^z) < x^z , for all non-negative integers x, y, z (x < y < z)

    so we can sort a, and find min xor of all a[i] ^ a[i + 1]

    sort(all(a));
for(int i = 0;i < n - 1;i++){
    if((a[i + 1].fi ^ a[i].fi) < mn){
      mn = (a[i + 1].fi ^ a[i].fi);
      ans = mn | ((a[i+1].fi ^ ((1 << k) - 1)) & (a[i].fi ^ ((1 << k) - 1)));
      I = a[i+1].se;
      J = a[i].se;
    }
}
    → Reply
    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      Is there any intuitive proof of this property of xor?

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

        yes, you can read it here

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

        Find first bit so that: -it is in some of the numbers -it is not in all of them Then it's either in $$$y$$$ and $$$z$$$ or only in $$$z$$$ (because $$$x < y < z$$$). In both cases it can be seen that this bit is in $$$x \oplus z$$$ but not in $$$min(x \oplus y, y \oplus z)$$$. Later bits won't matter

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

      Why ans can be calculate by ans = mn | ((a[i+1].fi ^ ((1 << k) — 1)) & (a[i].fi ^ ((1 << k) — 1))); ?

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

        actually it is just: ans = (a[i+1].fi ^ ((1 << k) — 1)) & (a[i].fi ^ ((1 << k) — 1));

        at first we want to maximize some (a[i] ^ x) & (a[j] ^ x), now suppose we want to use some Kth bit up to k, then you can see that Kth bit have to be in both of a[i] and a[j], or doesn't appear in both of them,

        proof

        from above it is easy to see that it is efficient to minimize xor

        so we don't care about cases where a[i] has some bit and a[j] hasn't or reversed.

        there left two cases:

        |1. both a[i] and a[j] have some Kth bit

        to get this bit we shouldn't use it in our x, (1 ^ 0) & (1 ^ 0) == 1

        |2. both a[i] and a[j] have not some Kth bit

        to get this bit we have to use it in our x, (0 ^ 1) & (0 ^ 1) == 1

        since we can use all bits up to k, our x should contain all bits up to k, where a[i] and a[j] haven't them.

        |1. (a[i+1].fi ^ ((1 << k) — 1) taking all zeros from a[i] up to kth bit

        |2. (a[i].fi ^ ((1 << k) — 1) taking all zeros from a[j] up to kth bit

        |3. (a[i+1].fi ^ ((1 << k) — 1)) & (a[i].fi ^ ((1 << k) — 1)) combining zeros, where a[i]'s Kth bit = 0 and a[j]'s Kth bit == 0

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

    How do you thing is it possible to solve G if queries are online?

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

      Using persistent DSU

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

      Maybe we need to use some persistent data structures.

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

      For each edge $$$(u,v)$$$, let the cost of the edge be $$$\max(h[u],h[v])$$$. Then for query $$$(u,v)$$$ where $$$u\neq v$$$, the minimum of the maximum height of the nodes on the path is equal to the minimum of the maximum cost of the edges on the path. So we can build MST and use binary lifting to find the answer.

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

        I did try to write the binary lifting solution for G (feeling dumb after finding out doing it offline is much easier). I get a WA on test 4. I'm not sure whether my implementation is wrong or there indeed exists a counter-case that one of the best path doesn't lies on the MST.

        215605164

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

          Maybe my online solution can help you 215601542.

          I write the Kruskal's algorithm and build a tree to solve it.

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

      Build a kruskal reconstruction tree(or dsu tree) and find lca of the 2 nodes in each query

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

    minimizing xor of two elements can be done easier: sort the array, answer will always be the xor of two consecutive elements.

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

    F can be solved by max prefix for the binary presentation, there's maximum two unique numbers with the same max prefix. once we identify the max prefix, we can use a map to collect the ones that have the same max prefix, or we can just sort and compare adjacent elements.

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

Bad statement for most problems :(

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

Yes-NoForces!!

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

i feel language was bit difficult.

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

Learning tries was after all worth it saving me today. Problem F felt really good to AC :)

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

    It can be solved using recursion without tries

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

      can you share your implementation

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

        [submission:https://codeforces.me/contest/1851/submission/215630074]

        The key idea is to find two numbers with miminum xor. Let's try to find to numbers with common $$$k-1$$$ th bit. Divide the array into two so that in two arrays $$$k-1$$$ th bit is common in all numbers. Solve recursively for $$$k-2$$$ th bit and so on. If you put ending conditions correctly, this will work

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

          funny my solution looks almost exactly like yours. mine didnt pass tho :(

          215616590

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

          Can also be solved by taking xor of two closest numbers. (Adjacent elements in sorted array).

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

    You just have to find optimal 'x' for all the pairs of adjacent elements of the sorted array of 'a', whichever pair gives max (ai^x & aj^x) is the ans.

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

      whats the reasoning behind adjacent elements ?

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

        I have an intutive explanation, for a bit to be included in the maximum answer either its not set in the two chosen indices or set in both, exploiting this information note that we can greedily start by trying to get the kth bit set first, so the whole array is divided into two multisets, one which doesnt have this bit set and other one has all the elements with this bit set, how to achieve this? Just sort the array, all the numbers which have kth bit set will be together, this holds(try to visualize this, it will make sense), Now if I want the kth bit to be set in the maximum answer, the final answer is going to be any two adjacent ( Just note that all the numbers with kth bit set will be consecutive, then among those all with k-1th bit will be consecutive and so on, and also numbers with kth bit set the numbers with k-1th wont set will be together, since thats just the nature of sorting), so if you were to write a bruteforce divide and conquer the final set will be some two consecutive numbers. Sorry if its lengthy but its a bit intutive to explain by writing

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

It was hard for me to concentrate on reading those problems, I liked it tho

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

D was awful, imho

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

I think my F is hackable

Submitted just after the contest got over.

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

Overall looks like a decent div3 contest, I have enjoyed solving A-E.

  • A — might be a little bit too much text for a div3A problem, but nothing too extreme
  • B and C — both are fine problems imo
  • D — some case work, nothing too dramatic, but I still have no idea how to prove my solution (also randomly got 50 additional penalty because I trolled myself again)
  • E — a problem about my favorite topic, I can see how this statement can confuse some people, but I myself probably couldn't phrase the condition of a graph being a DAG better
→ Reply
»
16 months ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve E ?

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

    reread the statement and you ll see that if you draw the graph of elements (needing each other) it will be a dag -> just do a simple dp on it. my submission: 215587840

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

I thought that G was about finding a path, so that $$$max - min \le e$$$. Btw, would there be a solution if this was asked?

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

Lets Go Pupil here I come..........

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

rank 834 can add 39 to become expert?

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

    By rating predication, you will get +30

    Use this extension for rating prediction Carrot

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

Nice problems but bad statments for most of them , thanks anyway!

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

What the hell

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

Can someone share their solution to B, C and D.

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

    B — sort odd values and even values while not swapping odd and even with eachother, then check if array is sorted. C — you need to find shortest prefix that there are at least $$$k$$$ occurences of $$$c_1$$$, and the shortest suffix that there are at least $$$k$$$ occurences of last color. If first and last are equal, you just need to check that there are $$$k$$$ tiles with color $$$c_1$$$, else you need to check that sum of lengths of the found prefix and suffix is less or equal to $$$n$$$ D — didn't attempt

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

      Sort the array and compare it with the original array if both elements at same position are odd/even then its YES if NO then NO

      → Reply
»
16 months ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

problem E is an easy version of one of the provincial team selection test for NOI of Ahhui, China 2014(AHOI2014) problem. See in here:https://www.luogu.com.cn/problem/P4042

→ Reply
»
16 months ago, # |
← Rev. 2   Vote: I like it -12 Vote: I do not like it

a

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

can some one explain this sample case for problem E

    4 2
    1 1 5 4
    2 4
    3 2 4 3
    0
    2 2 4
    1 2

how is the answer 0 0 0 0 , here

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

    Notice that Nastya already has unlimited numbers of potions 2 and 4 so the answer for 2 and 4 is 0. Also, to get potion 3 you can use potion 2 and 4 so you don't need any coins for potion 3 and the same for potion 1 so the answer is 0 0 0 0. Hope this helps!

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

    potions 3 can be obtained by potions 2(costs 0) + 4(costs 0) = 0

    potions 1 can be obtained by potions 2(costs 0) + 3(costs 0) + 4(costs 0) = 0

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

In problem A, is there any specific reason why Vlad cannot talk to the person on the same steps of the escalator??

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

    Two people with heights a and b can have a conversation on the escalator if they are standing on different steps It is given in problem statement

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

      I know bro.... it just bothered me becoz it is not so realistic

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

        ohhh, XD

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

        There is one type of escalators that has very narrow steps, that each step can only hold 1 person. I think the author is referring to that type of escalators??? :)

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

          but many people can be on the h+m and h-m step ? weird escalator

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

        It might be realistic because in some cities it is a known rule that people stand on the right and walk/run on the left side of an escalator. So, two people standing and talking on the same step will bother people in a rush.

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

    Vlad has bad breath.

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

Hello, could someone please help me figure out why my code is giving a runtime error on E? I don't usually use python https://codeforces.me/contest/1851/submission/215620727

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

    Maybe it's the python recursion limit/deep recursion issue, I know very little about python but I've seen similar kinds of questions regarding recursion/dfs traversal of a tree popping up here on codeforces.

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

      That must be it! I will try with stack, thanks for the tip.

      EDIT: That was it, AC'd now. Thanks!

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

    By default python has 1000 as the maximum recursion depth. Theoretically you've got to change it via sys.setrecursionlimit(), let's say sys.setrecursionlimit(10**5) and then it works, but in practice it will most likely give you memory limit exceeded on codeforces. So you just have to rewrite it without using recursion sadly, just directly use stack.

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

      Interesting stuff! Glad I used python this time, got to learn :D

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

Lol I didn't even understand the statement of problem E. Eventually, i just did wat-task-told-me-to-do + my guess and intuition and AC-ed :D

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

if problem E, the statement "Moreover, no potion can be obtained from itself through one or more mixing processes." is removed, I guess we need a scc to solve it?

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

    No, because if there is a cycle, then you:

    a) have one of the potions in the cycle which is trivial or

    b) don't have any of the potions. In that case, you will eventually revisit a node. Since a revisit is only possible due to a cycle, you will realize that the node came via a cycle and then can just buy the cheapest potion in that cycle.

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

Time to switch to hackforces

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

Problem statement is very hard

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

Thank you for having blank lines after the answer after every test case in Problem G. It made understanding the sample answer easier.

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

    Could you share your approach for G?

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

      Let $$$H$$$ be your current height and $$$E$$$ your current energy. If we go $$$x$$$ units up, your height changes to $$$H + x$$$ and energy changes to $$$E - x$$$. On the other hand if we go $$$x$$$ units down, your height changes to $$$H - x$$$ and energy changes to $$$E + x$$$. In both cases, the sum of your height and energy stays constant (equal to $$$H + E$$$, the sum of your original height and energy).

      Consider some query where you start from mountain $$$a$$$ with $$$e$$$ energy. This means that anywhere you go, the sum of your height and energy will be $$$h_a + e$$$. In order for your energy to stay non-negative, your height must not go above $$$h_a + e$$$. This means that you can go to any mountain $$$u$$$ with height $$$h_u \le h_a + e$$$ and you cannot go to any other mountains.

      Now, we can solve the problem in the following way:

      Consider the mountains and roads as an undirected graph. We will keep a DSU to tell which nodes (mountains) are reachable from each other.

      Sort all nodes $$$u$$$ in increasing order of $$$h_u$$$ and sort all queries in increasing order of $$$h_a + e$$$.

      When handling a query, we need to add all nodes $$$u$$$ with $$$h_u \le h_a + e$$$ and edges between them into the DSU. We can iterate over all nodes satisfying the above which have not yet been considered and add all edges going from those nodes to nodes with lower height to the DSU. After that, the answer to the query is YES iff nodes $$$a$$$ and $$$b$$$ are in the same component.

      Doing the above for all queries using a two-pointer approach is $$$O(n\cdot\alpha(n))$$$.

      Total time complexity: $$$O(n\log n)$$$ due to sorting.

      (slow) implementation: 215567991

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

Hope to become newbie after this contest

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

I couldn't debug G in time.Loved all the problems.

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

My thiscode gives correct output on my compiler and also on online compilers but somehow this is giving wrong answer on the Codeforces judge , what's the reason , please look into it.

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

    Your binary search could return -1 as index of array which is an undefined-behaviour.

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

I have doubt in problem statement of problem E.It is not mentioned whether cycle will exists or not.

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

    “It is guaranteed that no potion can be obtained from itself through one or more mixing processes.“

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

    "It is guaranteed that no potion can be obtained from itself through one or more mixing processes."

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

In F there is no need to know Trie , my solution is just greedy + binary search

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

    my solution was just sorting array and checking answers for consecutive numbers

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

Can anyone please explain the statement of problem e i still can't get it

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

    There are $$$n$$$ potions, each has its own cost. Each of the potions can either be bought or obtained by mixing some of the other potions. You have an unlimited number of $$$k$$$ potions which means you can use them for free. For each potion determine the minimal cost you should spend in order to obtain it.

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

i took this contest while in an airport lol

→ Reply
»
16 months ago, # |
← Rev. 2   Vote: I like it -12 Vote: I do not like it

can someone help me understand why am I getting runtime error for this code (problem C round 888 div3):

#include<bits/stdc++.h>
using namespace std;
#define int long long int
int32_t main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,k,w,flag1=0,flag2=0;
        cin>>n>>k;
        int l=k;
        vector<int> v;
        for(int i=0;i<n;i++)
        {
            int m;
            cin>>m;
            v.push_back(m);
        }
        int cnt=0;
        if(k==n && n==1)
        {
            cout<<"Yes"<<endl;
        }
        else if(v[0]==v[n-1])
        {
            for(int i=0;i<n;i++)
            {
                if(v[i]==v[0])
                {
                    cnt++;
                }
            }
            if(cnt>=k)
            {
                cout<<"Yes"<<endl;
            }
            else
            {
                cout<<"No"<<endl;
            }
        }
        else
        {
            for(int i=n-1;i>=0;i--)
            {
                if(v[i]==v[n-1])
                {
                    k--;
                }
                if(k==0)
                {
                    w=i;
                    flag1=1;
                    break;
                }
            }
            for(int i=0;i<w;i++)
            {
                if(v[0]==v[i])
                {
                    l--;
                }
                if(l==0)
                {
                    flag2=1;
                    break;
                }
            }
            if(flag1==1 && flag2==1)
            {
                cout<<"Yes"<<endl;
            }
            else
            {
                cout<<"No"<<endl;
            }
        }
        
    }
}
→ Reply
»
16 months ago, # |
  Vote: I like it -6 Vote: I do not like it

Can E be solved using Dijkstra?

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

Why am I not in the standings?

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

    If you check the "unofficial" box, it shows me, but if you uncheck it, it doesn't.

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

      Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participant of the third division, you must:

      take part in at least five rated rounds (and solve at least one problem in each of them) do not have a point of 1900 or higher in the rating.

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

F is similar to 1721D.

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

waiting for editorial...

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

I was able to solve one problem, but still am unrated. Any reason for that?? (This was my first ever contest. Sorry if I'm being dumb)

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

    To qualify as a trusted participant of the third division, you must:

    take part in at least five rated rounds (and solve at least one problem in each of them)
do not have a point of 1900 or higher in the rating.
    → Reply
    • »
      »
      »
      16 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Hey, one thing to clarify, does the triangle sign at the very right of the standings table mean the rating change?

      Another question, Will I get the ratings of my 5 contests added, or won't they be added? (After i become eligible for rating)

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

        It will be rated for you. Wait for the system tests to get over.

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

          but kgb said that I need to be qualified for Div 3, by participating in at least 5 rated contests and solving at least 1 problem.

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

            "Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you."

            This is what's written immediately below in bold.

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

Boy was that a hard round. I could solve A and B in the first 40 minutes, and could only think of a DP solution for C :cry:

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

    Doesn't require DP though.

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

      I'm sure it doesn't; guess I've been practicing way too much DP (and not other things) haha

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

        Lol, initially, I too thought of a DP solution, seeing that it requires subsequence matching sort of problem. However, observing that it only requires checking of possibility of the pattern rather than optimization, I thought of the other solution.

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

          Ah, that's cool! What's the other method?

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

Why the contest is begin shown unrated despite of being written "rated for less than 1600"?

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

    It is rated,ratings will get updated after system testing.

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

seems that I have my first aked Div.3 contest :)

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

    I failed system test on problem D because of integer overflow, and missed the chance to solve all the problems during the contest :(

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

Who knows, has system testing already ended or not?

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

My solve E O(n) has Time Limit 14 bruh?!?!?!

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

Testing has finished.When will rating update ?

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

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

My solution for D fell on system tests because I used int instead of long long in one line where I forgot a_i <= 1e18 when I was writing it. This is really annoying, and I think that a test case like that should've been on main tests. But oh well, lesson learned, from now on I'm always using #define int long long

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

    So do I!

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

    Next message: "My solution got TLE on system tests, then I submitted it without #define int long long and got AC. I think that a test case like that should've been on main tests"

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

Reached Pupil after this contest that I'm happy

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

Hoorah! My rating became >1000 this round :D

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

This contest is quite good

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

Finally made it to Pupil after a year of hard-work 😊

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

https://codeforces.me/contest/1851/submission/216352004

wrong answer Jury has better answer (13) than participant (12) (test case 1)

Jury output: 1 3 14 My output: 1 3 12

(3⊕14)&(1⊕14)=(0011⊕1110)&(0001⊕1110)=1101&1111=1101=13

(3⊕12)&(1⊕12)=(0011⊕1100)&(0001⊕1100)=1111&1101=1101=13

What is wrong with 12 as 'x'?

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

Hello MikeMirzayanov,

Today I got a message from the system regarding the coincidence of my submission with my friend decltype_t submission.It is because of using common resource. In these codes we used the same templates for graph, topological sort, and for debugging. This is the proof for same. Graph template Topological sort template Debug template. However, the main logic is different.

We(Me and decltype_t) hail from same college and follow the same resources for practicing. We also have a combined repository. You can see the same here. I agree that it's my mistake that I didn't give the credit to the author for using his/her template. You can also check our previous graph or tree based question solutions where we have been using the same templates.

Thank you for providing this excellent platform.

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

my solution got skipped just because logic looks like others but i worked it after one wrong submission and just optimized it several times so not my fault it looks like others solutions

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

    Dear MikeMirzayanov , kindly look into this as my logic was based on optimization of if else cluster statements in previous submissions

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

      thanking in advanced for looking into this!!

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

Attention!

Your solution 215580877 for the problem 1851E significantly coincides with solutions Milind_Sharma/215580877, fredreicc_/215618955. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.me/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

This is ridiculous, having same logic does not mean copied code, all of my submissions are now skipped. I have never copied a single code in any of my past contest. This is clearly a false positive.

I fail to see how my code is similar to the other user, also I submitted around 1 hour earlier.

Please take a look at the codes yourself and decide 215580877 and 215618955.

MikeMirzayanov Vladosiya

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

    MikeMirzayanov Vladosiya I have too been plagarised in this contest unnecessarily. I have even solved F problem that too within first 30 min. please check my code its not at all similar with others. I dont understand why I got plag. I had simple dfs call so that i can calculate the answer minimum just by topo sort. PLease see my code and give my ratings back. Its clearly wrong to plag someone who works hard. Kindly look into it and help me out.

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

'MikeMirzayanov Vladosiya Your solution 215615024 for the problem 1851E significantly coincides with solutions steve58/215601188 ...This is something not expected from codeforces the solutions by this guy and me is completely different I have used a simple graph topo sort which is having very common template of dfs call let me show you my code:

Here after taking the cost and making changes in its value depending upon free resources I had topological sorting in my code.I have used a simple dfs function which goes and checks its neighbours ahead then finally in ans array i stored the final minimum value of the cost and after topo sort value. My code is way different from one I am plagarized with . Please look in it and give my ratings back.


#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define ll long long
#define ld long double
#define fuk return
#define getunique(v) {sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());}
#define pb push_back
#define tr(it,a) for(auto it=a.begin();it!=a.end();it++)
#define fo(i,n) for(int i=0;i<n;i++)
#define fop(i,x,n) for(int i=x;i<=n;i++)
#define forv(i,l,n) for(int i=l;i>=n;i--)
#define nl <<endl;
typedef pair<ll,ll> pl;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<ld> vd;
typedef vector<string> vs;
#define inp(v, n) for(int i=0; i<n; ++i) cin >> v[i];
#define opt(v) for(auto x: v) cout << x << ' '; cout nl
const ll mod = 1000000007;
const ll N = 2e5+10;
#define IOS ios::sync_with_stdio(0); cin.tie(0);cout.tie(0);
ll bin_exp(ll a, ll b=mod-2, ll mod=mod){
ll ans = 1;
while (b){
if(b % 2) ans = (ans * a) % mod;
a = (a * a) % mod; b /= 2;
}
return ans%mod;
}
vl ans;
 ll n,k;
vl c;
vector <vector <ll> > v;
void dfs(ll node){
    if(ans[node]!=1e18) return;
    ll q=c[node];
    ll tot=1e17;
    for(auto p:v[node]){
        dfs(p);
        if(tot==1e17)tot=ans[p];
        else tot+=ans[p];
    }
    ans[node]=min(tot,q);
    return;
}
void solve(){
    // fo(i,N) ans[i]=1e17;
    v.clear();
    // fo(i,N) c[i]=1e17;
    cin>>n>>k;
   v.resize(n+1);
   c.resize(n+1);
   ans.resize(n+1);
   fo(i,n) ans[i]=1e18;
    ll p[k];
    ll cost[N];
    fo(i,n){
        cin>>c[i];
        cost[i]=c[i];
        
    }
    fo(i,k){
        cin>>p[i];
        c[p[i]-1]=0;
        // ans[p[i]-1]=0;
    }

   
    fo(i,n){
        ll f;
        cin>>f;
        ll k=0;
        fo(j,f){
            ll p;
            cin>>p;
            p--;
            v[i].push_back(p);
            
        }
    }
    //  fo(i,n){
    //     ll k=0;
    //     ll f=0;
    //     for(auto q:v[i]){
    //         f=1;
    //         k+=cost[q];
    //     }
    //     if(f)
    //     cost[i]=min(cost[i],k);

    // }
    fo(i,n){
        dfs(i);
    }
    fo(i,n){
        cout<<ans[i]<<" ";
    }
    cout nl
}
signed main(){
    IOS
    ll t; cin >> t;
    while(t--) solve();
    return 0;
}
→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello, MikeMirzayanov Today, I've received a message from [email protected] that my code for the problems A and B are similar to the codes of the user kishorenanda. I really don't know this person and even where is he (or she) from. The codes are really short, so they could be similar to the codes of any other person who had just the same idea. But now all the solutions that I've sent to the system are erased from my official sendings. Rewatch my solutions, please. My solution for A: 215511238 My solution for B: 215514366

→ Reply