sevlll777's blog

Codeforces Round 895 (Div. 3)
By sevlll777, history, 16 months ago, translation, In English

Hello Codeforces! Codeforces Round 895 (Div. 3) will start at Sep/07/2023 17:35 (Moscow time). You will be offered 7 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 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 prepared by: Alexdat2000, FairyWinx, sevlll777, Vladosiya, и MikeMirzayanov.

We would also like to thank:

  1. Vladosiya for the amazing coordination, and help with preparing and balancing a problemset.
  2. MikeMirzayanov for Polygon and Codeforces platforms.
  3. Ormlis for black-red testing.
  4. zwezdinv, BledDest for red testing.
  5. Sokol080808, diskoteka, Sweezy, vladmart, Kniaz, Tima, Riblji_Keksic, 74TrAkToR, pavlekn for yellow testing.
  6. moonpie24, gs20036, Kolychestiy for purple testing.
  7. martin0327, tnaito, no_mind, Pa_sha, SashaT9, ctraxxd, ezdp, BF_OF_Priety for blue testing.
  8. NerfThis, _SADIEM_, YudoTLE, sayed_4 for cyan testing.

Good luck!

UPD: Editorial

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

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

I enjoyed the problem set during testing, good luck to all the participants!

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

Problems' quality are just great and fun to be solved UwU

For all participants, May the odds be ever in ur favor❤️

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

As a tester , I can assure that this is the most balanced div-3 problemset I have ever faced and I recommend to read every problem

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

As a tester, I hope you will enjoy this incredible contest

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

I think the problems are nice. Good luck to participants!

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

Big chance to reach green tomorrow

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

    I'll stop saying this... But thank you for the contest, I really enjoyed the problems

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

      Div.2 rounds will be more important

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

I hope I don't get hacked again

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

I will try to solve all :>

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

    you will definitely get expert back :)

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

      This exam is really harder than I thought, I could only solve 5/7 problems: ((

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

        Bro istg i have figured out how E is solved ages ago I just can't implement aparrently

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

As a tester I recommend reading all problems. All problems are really fun, good luck!

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

OMG , Janmashtami round

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

Hope to become Cyan in this contest :)

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

Good luck!

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

MY first unrated Div 3.

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

Hope to reach 1000 in this contest.

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

This is no longer rated for me.. Weird bittersweet feeling

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

I am excited to participate in this contest. Good luck for all participants.

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

Last time, my sister was angry during contest and this time Shri Lord Krishna will be :(

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

    request mike to not schedule a contest on karvachauth 😂

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

Good luck to everyone! I really hope that I get specialist back

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

very balanced contest, loved it.

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

$$$t$$$ test cases forces

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

problem C is such a troll problem

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

NumberTheory-Forces

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

Any hint on how to solve problem E?

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

    Segment Tree

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

      Ohh ok THx, I was trying to solve this using difference array but was getting TLE

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

        I thought about using prefix sums but it would have taken some time to figure out the correct way for it so instead I used segment trees with lazy propagation which was pretty obvious. Still messed up the code and got 2 WA's

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

          It is quite easy. Just observe that if you have the XOR of the ones in the entire array and a XOR prefix array. Then when a query asks you to invert [l,r], that just means you set ones^=prefix[l,r], zeros^=prefix[l,r].

          Because every element is its own inverse over XOR. So when you remove all the 1 elements, thats the same as adding all the 1 elements. So inverting [l,r] is just adding the XOR of that entire array to ones and zeros XOR.

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

            Got it thnx. I first thought about 2 separate prefix xor array's one for ones and other for zeros complicating it that's why i aborted the idea and went with segment trees.

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

              how u implemented segment tree, can u explain?

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

                222304569

                I stored the xor of 0's in the range and xor of all 1's in the range and for lazy updates whenever i find a range that is inside the needed range just swap the values and set its children to do lazy updates whenever they are visited. And before accessing any range check if it has to be updated or not, if yes then update its value and set its children to do lazy update whenever they are visited.

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

                  cool thanks and i presume st[node].second is xor of all values in range right?

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

                  ya insted of storing xor of all zeros i used xor of all values since you can get xor of zeros just by doing xor1 ^ xorall

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

          i think there is no need of lazy propagation just segment tree works fine but my code is giving wrong answer on first test case its giving 3 2 6 7 0 instead of 3 2 6 7 7 , can some one help me with this.My submission link thanks in advance

          → Reply
          • »
            »
            »
            »
            »
            »
            16 months ago, # ^ |
              Vote: I like it +10 Vote: I do not like it 
            if (lx >= a && rx <= b) {
        swap(zero[k], one[k]);
        return;
    }

            I think you cannot do just that since you are not removing outdated nodes below which you update from afterwards... You should tell your child nodes to swap as well which is basically a lazy propagation.

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

            If you swap the values for a node it's children's values also have to be swapped

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

      It can be solved with sqrt decomposition too :)222263672

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

      It could be solved by using prefix Xor (same idea with prefix sum)

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

        I'm too lazy to implement lazy segment tree

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

    Just maintain the XOR of numbers with s[i]=='0', and XOR of numbers with s[i]=='1'. Then for each query of type 1, XOR the above 2 numbers with a special number based on the L and R given.

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

great contest!

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

How to solve E without using segment tree?

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

    We can use a prefix XOR to get range XOR efficiently. Let us define variables g0 and g1, which is the initial XOR of all the 0s and 1s. Then we set up our prefix XOR array.

    Notice that when doing 1 l r, we can just take the xor value and then g0 ^= res and g1 ^= res. This works because when we flip the bits, we flip the whole range of xor for those variables as well

    query 2 is just printing g0 or g1.

    Submission: https://mirror.codeforces.com/contest/1872/submission/222311808

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

    You can use prefix Xor 222276789

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

Problem B explanation was not good, almost wasted 1.5 hours to understand

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

How to solve G? If we have at least >= 20 non-unit elements, the answer is obvious. However, i still don't understand how to find the answer if there are only k < 20 non-units, even in O(2^k) or something like this...

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

    Two pointer / sliding window to test all segments with exactly k non-unit elements for each value of k.

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

    I did brute force in O(k^2) with all indexes l, r (less than 30 indexes in my solution)

    Find the maximum sum(1,l-1) + sum(r+1, n) + product(l, r) and print l, r.

    Sum and product can be calculated with prefix sum and prefix product

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

      But what if the product is really huge, e.g. you have 30 indexes with value = 1e9?

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

        I just print the index of the first and last number greater than 1 in this case

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

          Suprisingly, I thought about everything i heard from you, but still was not able to build the solution. Clearly, something went wrong... Thanks for explanation :)

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

            same here.I thought of all the things but still can't able to get to the proper solution/code.

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

Was it just me who wasted 5 min on problem A because of this:

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

    what is wrong with it ?,for me it was clear and helpful.

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

      Ntg's wrong with it except the fact that my brain decided to stop working for few minutes

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

How my brain processed Problem C:

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

Thanks for the contest. It was really amazing.

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

I really liked the problemset

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

it feels so good after solving E.

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

Amazing contest! Problems were nice and fun to solve. Thanks to Alexdat2000 FairyWinx sevlll777 Vladosiya for the round.

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

amazing contest!! I feel G is much more easier than F. Maybe its just my skill issue on graph problem. haha

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

    How did you solve G?

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

      tbh, i think my solution is not correct, however it got AC, so here how its work.

      you can simplify the problem into "Find subsegment with biggest difference of its sum and product"

      if the multiplication of the element in the array is very large, lets say its over 1e9, then you always can choose segment (l, r), where l is leftmost not 1 element, and r is rightmost not 1 element.

      if the multiplication of the element in the array is not very large, then it only has very few not 1 element (at most 60 element maybe, and the rest is "1", and you can ignore the "1" for product). Then you can do some bruteforce work to find which segment is most optimal

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

        I think that works, thanks!

        For F I copy pasted strongly connected components code. Now all the nodes are split into their own scc, we can find the minimum cost node in the component, then we need to move in that cycle and end at that node that we picked.

        Submission: https://mirror.codeforces.com/contest/1872/submission/222333264

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

          wow i really didn't think of that. Thanks!

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

          My intuition for F was something like this :

          It would be beneficial for us to sell animals which isn't feared by anyone first (because that animal must be afraid) so start sell the animal with 0 in-degree. For this we can use topological sort

          Now we left eith the groups of cycle. For each group, we can see that all animals will be sold for $$$2c$$$ price except the last one. That's why to maximize the sum, we just need to find which animal is the cheapest in the cycle and sold it last

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

          I used the topological sorting after removing an edge at the optimal point to break cycles

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

Have someone did F with path compression ?

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

    What do you mean by path compression? The DSU trick?

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

      Yup

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

        In that case, I did solve it with path compression but only because I frequently use DSU to track connected components. It isn't really necessary (but if you want to use DSU it's absolutely necessary).

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

Quick Editorial:

Problem A
Problem B
Problem C
Problem D
Problem E
Problem F
Problem G
→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How to come up with the formula for problem A?

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

      WLOG (Without Loss of Generality) let us assume $$$a \leq b$$$, then it is optimal to pour $$$c$$$ from $$$b$$$ to $$$a$$$.

      We can see that the differences of $$$b$$$ and $$$a$$$ decrease by $$$2x$$$ if we try to pour $$$x$$$ from $$$b$$$ to $$$a$$$.

      We need to make the differences equal to $$$0$$$, then the intuitive way to find the formula is by using ceiling from the differences of $$$a$$$ and $$$b$$$ divided by $$$2c$$$

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

        Ummm I still couldn't understand how you reached that formula >.< . Ummm can you explain why did we go about dividing 2c ?

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

          In 1 operation, you are not just removing c from the larger vessel but also adding c to the smaller vessel. So, the difference reduces by 2c. You have to find how many operations are required.

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

    Can we say in Problem F , that after eliminating nodes with indegree = 0 (There cost is counted as 2 * C[x] , we are left with only loops (can be different components) , with each node having indegree = 1. Now for each loop , we can just calculate the node that we should remove at the very last so that its cost is counted C[x] while the other ones' cost in the loop is counted 2*C[x] ??

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

      Yes, when there is loop, first you will remove the parent of element with smallest cost first such that element with smallest cost will get removed at last.

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

    In problem G solution is should be a[i] > 1.

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

    In G you brute force if a(i)>1 <=48 , but to be safe I did for <=50

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

    nice solution to G key point was product greater than some max value!!

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

Hey cf folks, looking for a coding friend who wants to upsolve with me, would really help if we could discuss answers after a contest gets over.

Also since the editorial is not out yet, can anyone explain me the intuition for problem C ?

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

    If l != r and r is at least 4 then one of the numbers is 2 and the other is floor(r/2)*2-2, this works. If l != r and r is less than 4 there is no answer

    Otherwise we need to find a divisor of l that is not 1 or l, we can bruteforce until sqrt(l) or use the Sieve of Eratosthenes to factorize l. If l is prime then there is no answer

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

      Still not able to understand it >.< I guess I'll leave it at that

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

        Apologies, I realized I didn't explain properly.

        If l = r then the sum of a and b must be equal to l, so if l is prime there is no answer (suppose there was, then there exists c >= 2 that divides a and b and therefore divides l as well which can't happen.) Otherwise we can choose a = min divisor of l that is not 1, and b=l-a.

        Otherwise, notice that a+b >= 4 because a and b are both at least 2. So if r < 4, there is no solution. Otherwise there exists a solution. Consider a = 2. We can choose b such that b is even and a+b is either r or r-1, assuming l != r (we handled the other case above), which is where b = floor(r/2)*2 — 2 comes from.

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

In problem D, I changed n,x, y type from int to long long and it got accepted. How could this be possible? [n maximum is 10^9]

Wrong answer here

Accepted here

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

    You have the line "using namespace std;" so when you call lcm(x,y) with x and y as int it ignores your custom lcm function and uses std::lcm(int,int) as that matches better, but that returns an int so it overflows.

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

A: The answer will be cd(abs(a-b), 2*c) because you have to move half the difference from the biggest vessel to the smallest one. and this will take you cd(abs(a-b)/2, c) moves.

B: Each trap forces you to be back past it after s-1 seconds. In that time you can move (s-1)/2 units to the right of that trap and sitll have time to return. Each trap puts on such restriction on your trip, so you just iterate over the traps and do ans = min(ans, d+ (s-1)/2)

C:If l and r are at least 4 apart, there is a multiple of 4 between them, lets call it k, and then k/2 is even, so we can set x= k/2 and y=k/2. If l and r are less than 4 apart, we can brute force all divisors of l, l+1, l+2 .. r. And then if d | l, we can return x = l — d and d. This will always find a solution, because if gcd(a,b) = g, and a+b = k, then g | k. So the answer will always be found among the divisors of the numbers between l and min(r, l+4)

D: You want to put the biggest elements of the permutation of multiples on x, and the smallest on multiples of y. You can ignore the indexes that are multiples of both. However, you can't calculate this naively. because n= 1e9. However, you can use triangle number sum n(n+1)/2. the number of multiples of x that are not multiples of y is n/x — n/lcm(x,y) = k. so do n(n+1)/2 — (n-k)(n-k-1)/2. To get the multiples of x, and do -(y-n/lcm(x,y))((y — n/lcm(x,y))+1)/2 to subtract multiples of y.

E: The array never changes, so we can calculate an XOR prefix array. After this we can calculate the XOR of all the ones-position in the array and all the zero-position in the array.

Then, whenever we are queried, we can just set ones^=prefix[l,r] and zeros^=prefix[l,r]. That is, we set our ones and zeros XOR counters to XOR the XOR of the element in [l,r]. The reason we can do this is because when we invert [l,r], we remove all the ones from 1, and add all the zeros. However, removing the ones is the same as adding the ones because every element is its own inverse under XOR. Same logic applies for zero

F: All the nodes with indegree zero, we can remove with no issues, because no one is afraid of them, so we lose nothing by removing them early. After we've done this, there might be new nodes with indegree zero, so we remove those as well (and add to answer in the order we remove them).

After we've removed all the nodes with indegree zero, there will only be cycles left. This is because every node here has outdegree 1 (they are only scared of one other animal).

So we can go through the cycles and find the animal with the least cost, call it s Then we go through the cycle and remove all elements in order, starting with A[s], and ending with s. That way we get twice cost of all the animals except s (which has least cost, so this is optimal).

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

Hi

Just checked out the problems and noticed that problem F was 99% same as abc256E

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

    they are not literally same lol, in this problem you have to construct permutation

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

Problem A: does not have to be an integer

Problem B: best illustration in contest

Problem C: even number, not 2, odd number, not prime, not 1

Problem D: sum top for x, sum bottom for y, duplicate LCM

Problem E: Lazy Segment Tree (but not enough time)

Problems are enjoyable! Thank you guys for the contest!

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

I lost D due to a typo long long -> long T_T

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

I solve C like this 222257731.I don’t want to discuss in categories(because I got Time limit exceeded :(

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

For problem E, I tried to solve it using the segment tree here. I pre-compute the XOR of the entire array a and store the precompute XOR of those values where s[i] = 1 in the tree. So then XOR of those that are zeros in s equals to all ^ one. The time complexity should be $$$O(max(q, n)logn)$$$, but I got TLE. Can anyone tell me what I did wrong?

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

    U don't need segment tree pre calculating XOR of the array just like a prefix_sum is enough. Just think that there's no an actual range update here due to XOR facts..

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

      Oh thanks! I re-implemented and it got accepted!

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

    For range updates you need to use lazy propagation, otherwise if you try to update all values in the range then cost for each update is O(n). If you are given q queries each of size n leading to O(n.q) so the TLE

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

      Ah yes, I forgot the lazy propagation :(. Was spending too much time on thinking about what to store in the segment tree.

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

I made video explaining problems A&B&C&D : https://youtu.be/g7OJ3GVzIhM

I thought it would be useful

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

That's very good contest i liked how does E work i thought that E is segment tree but i did learn a knew thing while thinking that you can make prefix xor , thanks for the contest.

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

In E I did sqrt decomposition lol

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

Does E require square root decomposition ??

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

    it doesn't require but you can overkill with it just like I did

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

Proper Div 3 round after a long time.

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

I didn't expect to learn something new in Div. 3 contests (the lemma about Functional Graphs, I skipped my theory classes :/), so thanks a lot.

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

Video Editorial For problem A to G.

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

Did somebody notice , that in todays G 1<=a[i]<=1e9 , but in examples they took a[i]=0 in some places .

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

My worst div.3, I solved only A-D(lately, beacuse of C) in contest, upsolved F. For me: C>D, E>F. But I couldn't solve F in contest. Hope better next time.

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

I'm not rly good at maths can someone plz explain how did he solve D by steps

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

I want some hints for problem F. If we make a directed edge graph out of the given things, with

$$$a->b$$$

meaning b is afraid of a, it would mean we actually have to implement toposort when the graph is acyclic. The problem arises when the graph become cyclic.

In that case we observe that for a cycle say,

$$$a->b->c->d->a$$$

, if we start from anywhere, let us say, from d, and go in the reverse direction of the edges, (i.e d->c->b->a), we will get the

$$$profit = 2d+2b+2c+a$$$

. In other words, if we start at node x such that

$$$x->y$$$

is an edge in the cycle, the profit we get is : profit = 2(Sum of profits of all the nodes) - y. This hints that we need to keep track of all the cycles in the graph.

Further we observe that the In Degree of any node will not be greater than 1, It means that two cycles cannot have any node in common, and also any two cycles are disconnected (it can be proved by contradiction). So now the problem reduces to finding the strongly connected components of the graph (as the strongly connected components will only have cycles in them), and then to track the minimum of the nodes present in the cycle.

Is there any efficient way to do this?

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

    Hey you're on the right track. Don't make the question too complicated tho. As you said indegree and cycles are important information for this question. Take some of the given samples, and try to reduce them into solvable graphs.

    Hint :- As each vertex has exactly one outgoing edge, so any cycle if present will be a simple cycle. Also each vertex will always have exactly one outgoing edge, so maybe solving for a cycle isn't that hard.

    You'll get the solution if you try to find a way for the given samples. I solved sample 2 and 6 when I did the question.

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

    My solution is Change the problem like this: if we sell Animal i there is a cost sum(C[j], for all animal j that afraid of animal i). Using priority_queue you can sell the animal(i) whose cost is minimum currently. And update cost of animal a[i] and push this to priority_queue.

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

    Kahn's toposort algorithm is still useful — it can give you an ordered list of nodes that aren't in cycles (so can be sold for 2*C). You can then just calculate the cycles for any nodes not in that list (using a simple dfs as there is only one option at each node).

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

.

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

    I'm not 100% sure, but I think the real issue is that your n inside function init is greater than the N you used to declare arrays. This can lead to overflow problems and unknown errors, including Wrong Answer. Your submission got AC when your n is smaller than N.

    Actually, your code always gets RE on my computer. It's a little strange why you didn't have this during contest, maybe because you didn't enable O2 optimization when you debugged locally? Specify -O2 can sometimes help expose some issues like overflow :D

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

I gave the contest and solve 2 questions but still i am unrated and the this contest is showing unrated for me i don't understand what is this if anyone has idea about this please tell me

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

    Don't worry it will take some time to update the ratings

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

    There was a hacking phase...now system testing will take place , after that they will update ratings. Probably wait for 3-4 hours

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

Hope to become an expert, good luck

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

Cannot understand why people are jumping to segment trees to solve problem e. It's a div3 e, not div2 e!

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

    It's easier for me to think using segment trees.

    Also it's not about solving problems the intended way. It's about being able to apply the tools available to you.

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

    I had like 45 minutes to implement and still didn't manage to do it somehow, I guess I'm not experienced enough with seg trees

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

Happy that I solved first 5 problems in this contest , but could have solve little faster to get good rank. Hope to be Cyan again after rating update.

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

Good contest hope pupils touch cyan their first time after rating

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

I put long long instead of long double when doing G (was working with log10) so got WA when rejudge, weak pretest :v but overall i enjoyed the contest.

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

Can someone please identify the problem with my submission for D? I'm pasting it below for easy reference. Thanks.

222341350

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

It was a very cool round, thanks to the creators!

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

Indians are rocking everywhere.

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

Good Luck Everyone for System Testing.

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

Why is this round being retested now?

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

I have got a skip on this problem : 222280755 for the problem 1872E

this template of code is shared with me and my friends as we all are in the same training

and the segment tree code is also a template, you can see my previous codes, all of them with the same template, so please give me the points back

→ Reply