Vladosiya's blog

Codeforces Round #888 (Div. 3)
By Vladosiya, history, 9 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

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

May 19, 2023 what

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

Here before "My first unrated contest" comments

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

hoping to solve atleast 3 problems

→ Reply
»
9 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
»
9 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Waiting for this! Me also hoping to solve at least 3 problems. Best of luck to all contestants :)

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

Hoping to become Expert in this round

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

why is there no cyan, green or gray testers?

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

Palindromic Round!

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

i hope to be blue this time

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

→ Reply
»
9 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
»
9 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I have exam (TT — TT)

→ Reply
  • »
    »
    9 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
    • »
      »
      »
      9 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
»
9 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

→ Reply
»
9 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
»
9 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
»
9 months ago, # |
  Vote: I like it +39 Vote: I do not like it

div3

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

Goodluck to all :333

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

good luck everyone ^-^

→ Reply
»
9 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
»
9 months ago, # |
  Vote: I like it -17 Vote: I do not like it

As a participant of this round, I can confirm that this is a great contest and has great problems, :D

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

I think this will be a good one

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

I hope I become Specialist wihs me luck

→ Reply
»
9 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
»
9 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Good luck

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

how many problems i have to solve to become pupil??

→ Reply
»
9 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
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I want to do it but I can't stay up late!

→ Reply
»
9 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
»
9 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
  • »
    »
    9 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
»
9 months ago, # |
  Vote: I like it +20 Vote: I do not like it

Experts to lower rankings in Div.3 be like:

→ Reply
»
9 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
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Tends to Pupil:)

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

I wanted to add a few friends, although I was just preparing for the contest with the attitude of testing the waters

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

Thanks for this contest!

→ Reply
»
9 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
»
9 months ago, # |
← Rev. 2   Vote: I like it -26 Vote: I do not like it

6

→ Reply
»
9 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
  • »
    »
    9 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
    • »
      »
      »
      9 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
      • »
        »
        »
        »
        9 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
      • »
        »
        »
        »
        9 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
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

hope to be specialist in this contest

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

Don't forget int overflow — use long when you are summing up!

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

I am at the lowest confidence in my life.

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

888 is a special number!!!!!!

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

I missed 777 and 666, at least I won't miss 888 round

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

Good Luck everyone

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

I will solve atleast 5 problems.

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

so she knows what awaits her. emmmmmmhahahahaha~

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

not good, the problem statements were not clear at all and were very ambigous

→ Reply
»
9 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
»
9 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Why I an rated ??????

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

Readforces

→ Reply
  • »
    »
    9 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
    • »
      »
      »
      9 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
      • »
        »
        »
        »
        9 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
»
9 months ago, # |
  Vote: I like it +14 Vote: I do not like it

Yes/NoForces

→ Reply
»
9 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
  • »
    »
    9 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
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      Is there any intuitive proof of this property of xor?

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

        yes, you can read it here

        → Reply
      • »
        »
        »
        »
        9 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
    • »
      »
      »
      9 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
      • »
        »
        »
        »
        9 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
        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I hate that I didn't see this comment ahead of time (although it may have been posted after the game)

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

          Thanks, got it :D

          → Reply
  • »
    »
    9 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
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      Using persistent DSU

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

      Maybe we need to use some persistent data structures.

      → Reply
    • »
      »
      »
      9 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
      • »
        »
        »
        »
        9 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
        • »
          »
          »
          »
          »
          9 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
    • »
      »
      »
      9 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
  • »
    »
    9 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
  • »
    »
    9 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
»
9 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Bad statement for most problems :(

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

Yes-NoForces!!

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

i feel language was bit difficult.

→ Reply
»
9 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
  • »
    »
    9 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    It can be solved using recursion without tries

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

      can you share your implementation

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

        [submission:https://codeforces.com/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
        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thank you :), i am pretty bad at recursion so was not sure about how to implement it even after getting intuition. Since i solve nearly all bitwise problems involving some random function going bit by bit in linear iteration

          → Reply
        • »
          »
          »
          »
          »
          9 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
        • »
          »
          »
          »
          »
          9 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
  • »
    »
    9 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
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      whats the reasoning behind adjacent elements ?

      → Reply
      • »
        »
        »
        »
        9 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
        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Really nice and intuitive explanation makes a lot of sense. So the very first part figuring out that bits of both the numbers need to be either both set or both unset gives us an idea that the closer they are in their binary representation at higher bits, better will be the answer.

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

            Yes that's the key idea thats why taking minimum adjacent xor in the sorted array works but you can check for all the pairs as well

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

              Its is pretty amazing that how value of $$$a$$$ and $$$b$$$ can be chosen independently of $$$c$$$ and the problem boils down to finding the optimal pair with minimum xor and $$$c$$$ can be then found using $$$a$$$ and $$$b$$$

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

    can you share your idea with tries? I tried to solve the problem with it, but I failed.

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

      We have the following function

      $$$f(a, b, c) = (a \oplus c) \wedge(b \oplus c)$$$

      We will get a bit set in the result of this function only when both bits of $a$ and $$$b$$$ have same value and $$$c$$$ opposite of them. That can be done by writing a truth table.

      I stored all the numbers using Trie. Then iterated over all the elements of the and for each element tried to find the one which gave optimal value.

      For that i begin iteration from root node and bits of current element $$$a$$$ and see if i can get bit same as that of $$$a$$$ in $$$b$$$ or not. You can refer my submission 215602305

      → Reply
»
9 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
»
9 months ago, # |
  Vote: I like it +36 Vote: I do not like it

D was awful, imho

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

How to solve E ?

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

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

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

rank 834 can add 39 to become expert?

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

What the hell

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

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

→ Reply
  • »
    »
    9 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
    • »
      »
      »
      9 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Here's what I am doing for B, It is the same as you described.

      //@author: @ihnaqi
//@href: 'https://codeforces.com/contest/1851/problem/B'

use std::cmp;
use std::io;
use std::mem::swap;

fn input() -> String {
    let mut s = String::new();
    io::stdin().read_line(&mut s).unwrap();

    s.trim().to_string()
}

fn main() {
    let s = input();
    let mut t = s.parse::<i32>().expect("Couldn't parse");

    while t > 0 {
        solve();
        t = t - 1;
    }
}

fn solve() {
    let s = input();
    let mut n = s.parse::<i32>().expect("Couldn't parse");

    let mut v: Vec<_> = input()
        .split_whitespace()
        .map(|x| x.parse::<i32>().unwrap())
        .collect();

    let mut v_res = Vec::new();

    {
        let mut v_odd: Vec<i32> = Vec::new();
        let mut v_even: Vec<i32> = Vec::new();

        for i in v.clone() {
            if i % 2 == 0 {
                v_even.push(i);
            } else {
                v_odd.push(i);
            }
        }

        v_even.sort();
        v_odd.sort();

        let mut odd_counter = 0;
        let mut even_counter = 0;

        for i in 0..n {
            if v[i as usize] % 2 == 0 {
                v_res.push(v_even[even_counter]);
                even_counter += 1;
            } else {
                v_res.push(v_odd[odd_counter]);
                odd_counter += 1;
            }
        }

        v.clear();
        v_even.clear();
        v_odd.clear();
    }

    if v_res.windows(2).all(|window| window[0] <= window[1]) {
        println!("YES");
    } else {
        println!("NO");
    }
}
      → Reply
    • »
      »
      »
      9 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
»
9 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
»
9 months ago, # |
← Rev. 2   Vote: I like it -12 Vote: I do not like it

a

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

        ohhh, XD

        → Reply
      • »
        »
        »
        »
        9 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
        • »
          »
          »
          »
          »
          9 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
      • »
        »
        »
        »
        9 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
  • »
    »
    9 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Vlad has bad breath.

    → Reply
»
9 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.com/contest/1851/submission/215620727

Spoiler (explanation)
→ Reply
  • »
    »
    9 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
    • »
      »
      »
      9 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
  • »
    »
    9 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
    • »
      »
      »
      9 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
»
9 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
»
9 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
  • »
    »
    9 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
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I solved it using modified dijkstra, checked the editorial and was confused so read the problem statement again. I think even the top folks solved it using modified dijkstra only.

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

Time to switch to hackforces

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

Problem statement is very hard

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

Forth problem is very interesting, I hope I solved it correctly)

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

    Could you share your approach for G?

    → Reply
    • »
      »
      »
      9 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
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Now, Waiting for the Editorials

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

Hope to become newbie after this contest

→ Reply
»
9 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
»
9 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
  • »
    »
    9 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
»
9 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
  • »
    »
    9 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
  • »
    »
    9 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
»
9 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
  • »
    »
    9 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
»
9 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
  • »
    »
    9 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
    • »
      »
      »
      9 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Thank you. But I'm still kinda confused in test case 1 in samples why we should use potions 2 4 5 for making the first potion (i know it's cheeper i mean why we should use three potions)?

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

        The first number of each line is the number of potions we have to use. The potions itself go afterwards.

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

i took this contest while in an airport lol

→ Reply
»
9 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
»
9 months ago, # |
  Vote: I like it -6 Vote: I do not like it

Can E be solved using Dijkstra?

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

Can someone please explain why this solution is getting TLE in question E. I have used dfs. I have been stuck for an hour.

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

    here's the modified accepted solution. Classic mistake ;p

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

      Thanks a lot!! Also why didn't passing adj[] by value affect the complexity? Edit- I got it, since we have passed a pointer to the array not the whole array thats why it didnt affect the complexity

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

    you need to send the arrays by reference (like sky_full_of_stars did)

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

Why am I not in the standings?

→ Reply
  • »
    »
    9 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
    • »
      »
      »
      9 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
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D and E? Why the problem statements are too boring?

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

F is similar to 1721D.

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

waiting for editorial...

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

    the thing be sey you fit wait tire and nothing fit drop now...I no expect any editorial to drop until like after 1 or 2 days after them don finnish the contest..I no know why dem dey do like that sometimes. Me I feel sey dem supposed to don already prepare the editorial down before dem even start the contest sef..

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

Long statement sucks.

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

can someone explain why we can't solve e with simple array based approach. my code is wrong, but i am trying to update values to 0 for potions which r unlimited and then calculate cost, and simply giving the output by comparing. code

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

    Oga, you no fit understand am be say you no fit understand am..Try to figure am out by yourself or else, I no think sey anybody get time to give you mouth for here

    → Reply
»
9 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
  • »
    »
    9 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
    • »
      »
      »
      9 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
      • »
        »
        »
        »
        9 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
        • »
          »
          »
          »
          »
          9 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
          • »
            »
            »
            »
            »
            »
            9 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
»
9 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
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I could think of better than DP for C in 15 mins but it took me 45 mins to come up with the correct code.

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

    Doesn't require DP though.

    → Reply
    • »
      »
      »
      9 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
      • »
        »
        »
        »
        9 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
        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
»
9 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
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

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

→ Reply
  • »
    »
    9 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
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Who knows, has system testing already ended or not?

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

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

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

Testing has finished.When will rating update ?

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

→ Reply
»
9 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
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    So do I!

    → Reply
  • »
    »
    9 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
»
9 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Reached Pupil after this contest that I'm happy

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

Hoorah! My rating became >1000 this round :D

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

This contest is quite good

→ Reply
»
9 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
»
9 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

https://codeforces.com/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
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It has been a week but still cheaters not removed

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

To the respecful writers of the contest,I apologize for using ideone.com during the Round 888 Div 3. I regret that happended without my knowledge. I usually use codeblocks for c++ and Notepad for Java code in both languages based upon the question.But multiple testcases dont work at once so I used ideone.com. I use my personally mail-id and changed the settings(public access to my code). But for this contest I have used my College mail-id for paticipating the contest without changing the settings of ideone.com. May be from there my code was stealed. I apologize for that I will not repeat the same mistake once again. I will take atmost precautions while attending the test and I won't use ideone.com in my entire life during contest. Kindly Excuse me for this one last time.I won't repeat it.

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

I hope this message finds you well. I am writing to address a concern regarding my submission with 215612482 for the problem 1851D. I have noticed that there are similarities between my solution and that of another user, but I would like to clarify that I have not engaged in any form of cheating or plagiarism.

While I understand that the logic in my solution might coincide with someone else's, I can assure you that my approach and implementation are entirely original. It is not uncommon for multiple participants to arrive at similar solutions, especially for well-defined problems that may have limited viable approaches.

To further support my claim, I would be more than willing to provide a detailed explanation of my thought process, the steps involved in my solution, and any relevant code snippets that may help demonstrate the uniqueness of my approach.

→ Reply
»
9 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
»
9 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
  • »
    »
    9 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
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thanking in advanced for looking into this!!

      → Reply
»
9 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.com/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
  • »
    »
    9 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
»
9 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
»
9 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
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

any idea for problem E (advance)? Where the graph has cycles?

→ Reply