ch_egor's blog

Pinely Round 2 Editorial
By ch_egor, 8 months ago, In English

Thanks for the participation!

1863A - Channel was authored by Endagorion and prepared by irkstepanov

1863B - Split Sort was authored by Endagorion and prepared by ch_egor

1863C - MEX Repetition was authored by Endagorion and prepared by amethyst0

1863D - Two-Colored Dominoes was authored by Endagorion and prepared by AndreySergunin

1863E - Speedrun was authored by Endagorion and prepared by Golovanov399

1863F - Divide, XOR, and Conquer was authored by Endagorion and prepared by ch_egor

1863G - Swaps was authored by Endagorion and prepared by zemen

1863H - Goldberg Machine 3 was authored by Endagorion and prepared by Endagorion, irkstepanov

1863I - Redundant Routes was authored by Endagorion and prepared by Endagorion, irkstepanov

1863A - Channel

Solution

1863B - Split Sort

Solution

1863C - MEX Repetition

Solution

1863D - Two-Colored Dominoes

Solution

1863E - Speedrun

Solution

1863F - Divide, XOR, and Conquer

Solution

1863G - Swaps

Solution

1863H - Goldberg Machine 3

Solution

1863I - Redundant Routes

Solution
  • Vote: I like it
  • +216
  • Vote: I do not like it

»
8 months ago, # |
  Vote: I like it -14 Vote: I do not like it

thanks for fast editorial

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

what is test 81 in test case 2 in D ?

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

E is a really good problem!! Thanks for fast editorial.

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

Slowforces

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

can't understand editorial of b

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

    take for example a permutation where 2 appears after 3 whereas to make the permutation sorted 2 needs to appear before 3. For this to happen we must choose 2 as our x and perform the operation this will reposition 3 after 2. Hence we do this for all x where x+1 lies before x in the given permutation.

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

      How do you understand the institution, or did you saw any pattern in this? I'm very slow, any suggestions to solve questions related to strings and arrays on competitive platforms, I feel they are tough for beginners like me

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

        My advice is solve more problems,for improving your implementation so you can crack A quickly solve topcode div2 and for constructive problems just keep solving more problems as time goes on ideas will repeat i know it seems like impossible but yes and this way you train your brain to think of different patterns. So as conclusion if you want to have intuition solve problem especially constructive but don't forget about learning other new algorithms and implementing them or using them to solve the problems.You need to find the balance that's it and of course it takes real time to improve so you need to keep hardwork.

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

      The worst case for this will be O(n^2). Won't it give me TLE?

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

        it can be done in O(n) using map or visited array or it can also be done as mentioned in this comment

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

      thanks for the help and apologies for the late reply

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

    It says that if the pair of values $$$(k, k+1)$$$ appears inverted in the input permutation, then you need to perform the operation with $$$x = k+1$$$ in order to get rid of that inversion. Now, just note that if you consider all these pairs and perform the operation when needed, starting from $$$k = 2$$$ until $$$ k = n$$$, the permutation will be ordered.

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

      thanks for the help and apologies for the late reply

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

    let's start from k = 1 and see if the (k + 1) position comes after the k position we stop when the condition fails and count it as a turn we chose x as the last item that we get, then we pick another k just the last item we didn't get from the previous turn, Each time we write a set of numbers in the correct order as much as we can, So the answer is the number of turns. To do that just count how many pos[i] > pos[i + 1] for all i from 1 to n — 1. It's exactly this problem : Collecting Numbers

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

      thanks for the help and apologies for the late reply split sort and Collecting numbers can be done like this sort the array keeping their index start iterating from i = 2 if(index of i < index i — 1) ans++

      it can further be optimised as number are 1 — n, we can just place the index of x to the index x in sorted array

      thanks suggesting the Collecting Numbers as it made me understand the concept https://cses.fi/paste/17d0c105267da8d76a177b/

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

Video tutorial for problems A&B&C in english: https://youtu.be/X08zbEDtaI8

Thought would be useful to the community

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

really liked D and E. I hope there will be more such great contests!

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

Video Editorial for problem A,B,C,D.

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

how is O(N^2) possible in F with the given constraints on N? also can you provide test case 3? 1863F - Divide, XOR, and Conquer

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

Finally, editorial written not in broken English

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

Can't understand E. explain

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

    Let, firstly, solve simpler problem. Assume starting time is $$$0$$$ (meaning the first imaginary quest which is prerequisite of any other quest was done at day 0, hour 0). Maintain a $$$dp$$$ array, where $$$dp[v]$$$ is the day when the quest $$$v$$$ is completed. It's clear that if the quest has no prerequisite it's $$$dp$$$ value is zero. Otherwise, let $$$u_1,...,u_k$$$ be prerequisites of $$$v$$$, then $$$dp[v] = max(dp[u_i] + f(u_i))$$$ where $$$f(x) = 1$$$ if $$$h[x] > h[v]$$$ and $$$f(x) = 0$$$ otherwise. Answer to the problem is maximum value of $$$dp[v] * k + h[v]$$$ (Since we are counting starting time as $$$0$$$ and $$$v$$$'s quest is done after $$$dp[v]$$$ days on $$$h[v]$$$ hours). However, we need to choose optimal starting time and somehow maintain the answer. Notice that optimal starting time is some $$$h[i]$$$, where $$$i$$$'s quest has no prerequisite. Assume $$$v_1,...,v_k$$$ are such quests and WLOG assume $$$h[v_1] <= ... <= h[v_k]$$$. We will update starting time from $$$0$$$ to $$$h[v_1]$$$, from $$$h[v_1]$$$ to $$$h[v_2]$$$ and so on to $$$h[v_n]$$$. Let assume we are making transition from $$$h[v_i]$$$ to $$$h[v_{i+1}]$$$. So firstly we must update $$$dp[v_{i + 1}]$$$, then we mist update it's children. So we can simple use DFS. Also notice that every quest will be updated only once, so it should pass the time limit.

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

      don t you update dp[vi] in the transition?

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

      We only going deeper from the current vertex only if dp[v] is increased by one (and this can happen only once). Correct me if I am wrong, please.

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

      oh, you're so helpful. It confused me a lot, I'm always thinking why the complexity is right, thank you.

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

Would someone please help me understand why my submission for E (221172178) giving TLE. According to me, the time complexity of this code should be O(m+n*lgn), since I am traversing through each edge only once while doing DFS.

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

    Your final for loop is O(N^2) since you call max_element

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

      Ohh, got it. Thanks!
      I was stuck finding mistake in recursive function, just ignored this. Thanks a lot :)

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

EFG are all excellent problems. Failed to solve F because I mistakenly thought that 1<=n<=1e5.

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

Why for problem E f(x, y) is defined only with y?

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

    Has to be a typo. In the definition they meant to write z >= max(x, y).

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

Thanks for the fast editorial!

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

Thanks for this nice round, and fast editorial!

Here is my advice about the problems:

A
B
C
D
E
F

Also, could you please clarify a bit the second part of the editorial of F please ? Maybe I'm just bad at english but I don't understand what mask_start and mask_end correspond to

Thanks :)

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

    For point $$$i$$$, if the xor of an interval $$$[i, r[$$$ contains a bit of $$$maskStart_i$$$, then it means it is obtainable, since at one point prior, an interval $$$[i, r'[$$$ with $$$r' > r$$$ had that bit for most significant bit of the xor. Same for $$$maskEnd_i$$$.

    So you keep these $$$2N$$$ masks as you iterate over subarrays in length non-increasing to know which ones are obtainable.

    By the way I love your profile picture, where is it from ?

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

    Can u pls clarify how upper/lower bound is used in B.

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

C can also be solved using binary lifting. Overkill, but if you spot it quickly, you could just a use a template for insta solve Here is my solution

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

In problem E, can ternary search be used for finding the optimal starting point?

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

    I thought on the same idea during the contest, but couldn't do it. The problem with the ternary search was that the function isn't strictly increasing/decreasing, meaning there is some value x, for which $$$f(x) = f(x + 1)$$$, but $$$f(x)$$$ isn't extremum of the function.

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

      I think it's not just about $$$f(x) = f(x + 1)$$$, but that the function can also alternate going up and down wildly (or at least, that's what I saw when testing this locally).

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

        You could be right. I just tested the given examples and noticed the problem I mentioned above. I didn’t dig deeper.

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

Hi all, it would really help if you can post some insights/hints for the problems of this contest on https://starlightps.org ! Here's a link to the problems: https://starlightps.org/problems/collection/cf-pinely-2/. This will help us get more data so users can have a platform to:

  • share/discover hints/insights on various problems
  • find similar problems given insights they struggled with.

Check it out if you're interested. Thanks!

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

i think the problem C was very easy especially compared to B too bad i did not read it early.

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

thanks for the exciting tasks, as for me the gap between D and E is too big

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

For problem E, I didn't understand the editorial, and most other solutions seemed to use some form of Dynamic Programming, which seems different from what I did.

I start by calculating the maximal end time when you start questing at the earliest possible time, which is easy to calculate in O(V + E) time using the topological ordering of the DAG. However, this might not be optimal: it can be better to defer some quests to day 2 so we can start later in day 1, without affecting the end time. So I consider all the starting times of quests that have no dependencies. The key is that I update the end times for other quests incrementally, for an overall O(V + E log V) solution.

Submission with a (too many) comments: 221200048

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

    There's no need for that log, that's what I did as well. Your first step is dp, so I don't get why you're talking about others "using some form of DP".

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

    mark me if I am wrong ? What I got from your code is that particular (ith) quest with (0 dependency) can either be done at (h[i] or h[i]+k) hours so after that you are checking effect of (h[i]+k) ending on other quest so , its complexity will be O((number of 0 dependency node)*(ElogV)) how its possible to get accepted , or It is like each quest can be updated one ,if it is then why it is updated once , please explain

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

      I tried to explain that in the last two paragraphs of the comments at the top of the file. It's not immediately obvious, but for each vertex v, we increase end_time[v] at most once, by exactly K. That means it's actually just O(V + E log V) time overall, not O(V + VE log V) as it would otherwise be.

      And tfg pointed out, correctly, that the priority queue is not needed, so instead of O(E log V) it could be something like O(E), but the really important part is that it's not O(VE), which would be much too slow to pass. The difference between O(E) and O(E log V) is relatively small.

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

    Honestly, your explanation should be to the editorial. It's so much simpler to understand.

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

    Thank you so much. Easy to understand.

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

It is the greatest contest I have ever seen

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

How to solve D if you must colour all cells, not only the domino ones?

→ Reply
»
8 months ago, # |
← Rev. 2   Vote: I like it +29 Vote: I do not like it
Why I didn’t solve F
→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Here's my wrong idea on F: (maybe it's right, I don't know)

    Let $$$s(l,r)=a_l\oplus a_{l+1}\oplus\dots\oplus a_r$$$.

    First let's reverse the operations. Instead of changing subarray $$$[1,n]$$$ into $$$[i,i]$$$, we try to expand $$$[i,i]$$$ into $$$[1,n]$$$. For a subarray $$$[l,r]$$$, we need to find an adjacent subarray (either $$$[r+1,x]$$$ or $$$[x,l-1]$$$) which has a smaller $$$xor$$$ value than $$$s(l,r)$$$, and merge them.

    Let's look at the maximum most significant bit of all $$$a_i$$$. Let $$$cnt$$$ be the number of $$$a_i$$$ s that have this bit. Let $$$b_1,b_2,\dots,b_{cnt}$$$ be all $$$i$$$ that $$$a_i$$$ has this bit.

    If $$$cnt$$$ is odd, then only $$$b_1,b_3,\dots,b_{cnt}$$$ are valid.

    If $$$cnt$$$ is even, then all $$$i\in[b_{2k-1}+1,b_{2k}-1]$$$ are invalid. We can merge all $$$a_{b_{2k-1}}\ \ ,a_{b_{2k-1}\ \ +1},\dots,a_{b_{2k}}$$$ into one number, which is $$$s(b_{2k-1},b_{2k})$$$. Then, the maximum most significant bit is gone and we go on to solve the problem for a smaller bit. What I still can't figure out is how to solve for $$$a_{b_i}$$$. Maybe it could be solved using Segment Tree.

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

I love F very much.Hope there will be more problems like this.

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

https://codeforces.com/contest/1863/submission/221150801

Can I ask? Why my 7th test got a negative number? I didn't see any "out range" in my variety (for example, when I'm finding the missing number, I'm using long long)

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

    (n+1) * n will overflow because n is an int. Cast n to long long or declare it that way from the beginning

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

    When you multiply (n+1) and n, because they are both int values, it overflows before stored into variable missing. Just change one of them into long long then multiply.

    long long missing = (n + 1) * (n) / 2; should be changed to long long missing = 1ll * (n + 1) * (n) / 2; or long long missing = (long long)(n + 1) * (n) / 2;.

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

is there any other solutions to f？

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

Can someone explain F more clearly?

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

what is test 72 in test case 2 in D?

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

Can someone help me with P5? My idea was to perform a dfs to find pairs (s1,s2) of optimal start time and end time for each component of the directed graph. If d is the number of connected components in the graph, then we will have d such (s1,s2) pairs. Then, I sorted this vector of pairs and found the optimal time.

Issue is I am getting TLE on test case 18. I don't see which operation is being so expensive. Any help will be highly appreciated.

Source Code

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

What is test 72 in test case 2 of D

Getting wrong answer for that https://codeforces.com/contest/1863/submission/221170325

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

In problem E can anybody help me understand why every node's time is going to be updated at most once ??

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

    If you start the process on the 2nd day instead of the first, every value will increase by 1. So, if you had started earlier (meaning on any time of the day 1), values couldn’t have been bigger. Hence, they can increase only once.

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

How difficult are the H and I questions? How come no one has worked them out during the contest... Including our dear Tourist, Radewoosh, JiangLY and so on...

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

221228312 please help me with the test case on which this submission is failing in the problem 1863D - Two-Colored Dominoes

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

I just want to ask what happens if the number in the array provided is not in 0 to n as it is obvious that it wil come in 0 to n+1 with leaving the last element but how can a person do that question because in c it is already given it is in 0 to n So what wil be the difficulty of the above with the present C?

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

    If the original array could have duplicates or values outside of range [0, n] the solution would be still pretty much the same. You can manually perform one operation on the original array, now all values are going to be MEX of some arrays of length $$$N$$$, so that guarantees that all values are now in range [0, n], moreover, after performing such an operation there can't be two duplicate values in the array. All that's left to do now is to decrease k by one and calculate the cyclic shift for k modulo n + 1.

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

      Yes it's true but can you please explain how to implement this in O(n). Thanks for replying.

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

        Well this is the approach I came up with during the contest, my submission: 221139985

        Although I believe it has $$$O(nlogn)$$$ time complexity because I used a set<int> to calculate the MEX values, also you might want to be a little bit more careful to handle the out of range and duplicate values correctly

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

          Ohh thankyou so much that's what my intention is your code is same like that

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

In problem C, let n=1,k=1,arr={3} then MEX would result " -2 according to code " but in question its states that mex cannot be negative. Please justify.

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

In the solution of problem F，should the condition be $$$s & mask_start_l > 0$$$ or $$$s & mask_start_r > 0$$$

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

    Yes, a symbol ^ represents AND logical operation in mathematics.

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

In the solution of problem F，should the condition be s & mask\_start_l > 0 or s & mask\_start_r > 0？

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

Endagorion, big thanks to you for enchanting problemset!

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

Can someone help with the proof/intuition of D? Why can we color the dominoes in any order? I thought that coloring the dominoes according to a row/column might affect the other rows/columns.

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

I tried to implement my solution in E problem but it was giving TLE on testcase 5. please can someone show the mistakes in my code.
my submission: link

Here I have tried to explain my logic:
1. sorted the given array of time at which quest will start and then mapped the indexes accordingly.
2. made an array ind to store indegree of every node of the graph.
3. then calculated the time needed if we start from each node with 0 indegree(as it can be started independently), using calc function.
x = no. of nodes with 0 indegree.
idx: contains the index of node with 0 indegree.
val: contains the time needed to complete the quest if we start from here (to complete all the quests that are dependent on the particular node).
4. used some prefix, suffix logic to get the final ans. (to decide at which point to start)

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

I didn't get most of the edi, but I think that I is much easier (and I upsolved it this way):

I've stopped reading after getting to the point that we will take whole classes of adjacent paths. So let's connect them and make a directed edge from class of shorter paths to a class of longer paths if they contradict with each other. There surely is a way to extend one of the shorter paths into one of the longer paths if this is the case. So we might as well only use edges from a class to a class of paths longer by one. Aaaaaand this graph turns out to be a tree, where each vertex has a weight (number of paths in this class) and we have to pick a subset such that no pair ancestor-descendant is picked, so easy dp.

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

For problem B, I solved it using OrderStatisticTree. I don't know if anyone got this idea (Maybe the same observation in this editorial but different approach to utilize it). I wish I had an OST handy during the contest )';

Submission: 221492256

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

The solution to 1863E says: So if we define $$$f(x,y)$$$ to be the smallest $$$z\ge y$$$… Is it a typo that the latter $$$y$$$ should be $$$x$$$?

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

For the F solution, why do we want that s ^ mask_start > 0 or s ^ mask_end > 0?

(Also if my understanding is correct, are mask_start and mask_end suffix and prefix xors of the initial array? Or am I potentially misunderstanding this part?)

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

Can someone help me to solve problem E. I want to do it with topological sort, and in order to solve it, I need to solve one subproblem first. How can I get the smallest lexicographic configuration of topological sort. For example, if there are two correct toposort configurations [4,1,2,3] and [1,4,2,3], how can I get the second one? Thanks in advance

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

Is this round unrated now?

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

Why there is so many like? There aren't code in it,I think it bad.

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

can we solve D using graphs in this complexity ??

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

https://codeforces.com/contest/1863/submission/243936605

for d problem why this solution is giving WA

what is the problem in logic ?

→ Reply