neckbotov's blog

Technocup 2021 Elimination Round 3 and Round #692 (Div. 1 + Div. 2) Editorial
By neckbotov, history, 4 years ago, In English
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...

Code

Btw, congratulations to Benq on first-to-solve this problem!

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

Comments Comments (137)
| Write comment?
»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Auto comment: topic has been updated by neckbotov (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it -53 Vote: I do not like it

I think pretests are weak for B.

→ Reply
»
4 years ago, # |
← Rev. 5   Vote: I like it -42 Vote: I do not like it

Wishing everyone HAPPINESS,LOVE,JOY and PROSPERITY.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it -13 Vote: I do not like it

    Can div 2 C be solved without graphs usage? if so can someone explain how to solve it without graphs?

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

      You don’t need to find cycles in a graph explicitly, you can use disjoint sets (union find) to group rooks, list out the number of diagonals a group can attack, and add to the number of moves required based on that.

      A group that can only attack one diagonal is already on the diagonal and requires 0 moves(loop), a group that can attack as many diagonals as there are rooms requires rooks+1 (cycle), and a group that can attack more than there are rooks requires rooks moves(tree).

      It’s graph-like, but it’s chess so that’s to be expected.

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

Why in problem Div1C for the test 3 3 abc

the answer is Yes? we have only 2 options here: 1) -a — b + c = -1 — 2 + 4 = 1 2) -a + b + c = -1 + 2 + 4 = 5

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +29 Vote: I do not like it

Time limit for B is awfully tight for python. 101868901 and 101909293 have a mere constant factor difference but one TLEs and the other ACs

my -20 is now a -140 :(

Upd : Got hacked xD

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

    Same thing happened with me. After contest, I used dictionary to store the answers. Here is my AC code.

    CODE
    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      That only works cause no one has bothered to make a counter test for it.

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

    Just hacked your lower constant solution. That one passed only cause there wasn't an early exit counter test case.

    Btw the reason why PyPy is super slow here is that PyPy is 32 bit on CF, so this problem requires you to do a ton of work on big integers. This code would have easily passed on pretty much any other online platform. Remember to always look out for slow big integer operations in the future! Especially in problems like this where a lot of the big integer calculations easily can be avoided.

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

      Thanks for the info, I don't use python during CF rounds often, this was one of the first. I made a few resubmissions with minor changes. 102364715 passes with 1980ms (its the same except for one line) and the same hacked code passes when I add fast IO 102365085.

      Upd: Hacked

      Upd2: AC 102366948

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

        Just hacked both of those with a better counter test case.

        Btw if you really want something not hackable using early exits you should skip mod checks for both 0s and 1s 102367618. My TLE hack makes your solution do % int('1') around 2.5e8 times. By skipping 1s, then an upper bound on the number of operations becomes something like 1.3e8 times.

        EDIT: After looking through your recent submissions, I saw that using ord instead of int helps a ton. So I updated the "unhackable" solution above to reflect this. Looking at the numbers, it looks like doing int('1') 2.5e8 times is the real killer.

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

    After uphacking your code I continued hacking. Currently up to 391 uphacks on Div 2 B. The system tests were definitely lacking.

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

Can someone explain B?

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

    LCM(1,2,3,4,5,6,7,8,9)=2520 So ::>> EVERY MULTIPLE OF 2520 is divisible by all digits( 1,2,3,4,5,6,7,8,9 )

    NOW let x=n(GIVEN NUMBER). SO just iterate x ,i.e., do x++ UNTIL THE given CONDITION in question SATISFIES.This will take at most 2519 iterations.

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

      I think I explained correctly in the rev 1..

      I gave my best .. But I don't know why I was down-voted.

      → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

Problem C is Intresting!!! we can solve it with DSU too.

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

Can someone explain the editorial of Division 2C? I am not getting it

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

    1.Ignore the rooks on coordinates of form (x,x) since they are already on the diagonal

    2.Make directed edge between two rooks if x coordinate of the one rook matches y coordinate of the other rook. Suppose there is rook on coordinate (x,y) and another on $$$(x_1,x)$$$ then there will be edge from rook on (x,y) to rook on $$$(x_1,x)$$$.

    From point 2 we will get a graph . Answer will be number of vertices + number of cycles in the graph . This is because for each vertex we have to do at least one operation . Whereas for cycle , we need to do at-least 2 operation for any one of the vertex on cycle to break the cycle. Note : Here we are not counting vertices (of form (x,x)) in point 1 in our calculation thus no need to subtract as given in the Editorial.

    For example in following 5*5 matrix (sorry for bad picture), minimum number of operations is 5 (4 vertex + 1 cycle). Red dots are rooks and red edges form the graph.

    Try yourself in less than 5 operations and you won't be able to do it.

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

      Very good explanation. I was searching for something like this. Thanks a lot.

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

      Why do we build the edges like this, I can't unserstand.

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

        I hope you got "How" part . Thus i will explain "why" part .

        Suppose rook0 on the coordinate (x,y) and x≠y , in one move we can move it to (x,x) or (y,y) . But if there is some other rook, say rook1 on column x and rook2 on row y then we cannot move this rook on (x,x) or (y,y) . Thus we have to move rook1 or rook2 first in order to move the rook0 on diagonal in one move.

        But it might be possible rook1 and rook2 themselves cannot move on the diagonal if they have case similar to rook0 .

        By forming edges like i mentioned we can find those group (cycles) of rooks where each rook in group cannot move to diagonal in one move until one of it is moving to some diagonal point with "2" moves.

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

          Will undirected edge make a difference?

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

            Number of cycles will remain same in both cases because each vertex will have maximum degree 2. There will be just disjoint cycles (i.e there won't be case like two cycles connected to each other). Hence no difference in answer.

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

              In cases where (x,y) and (y,x) both form edges, the undirected edge will lead to the wrong count of cycles. So, in my opinion, directed edges are more apt.

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

                It depends on what algorithm you are using to find the cycles . Number of cycles won't be effected by directed or undirected edges in this problem.

                Yeah , for most algorithms directed edge will be safer to avoid multiple counts of same cycle.

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

      Won't there be multiple such graph? Consider 4 points (x,y), (x2,x), (x3,y2), (x4,x3). Nice explanation though.

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

    Well i considered it to be a graph with n nodes where each coordinate (i,i) ( 1<=i<=n) are considered as nodes. There is an edge between a node at (i,i) and (j,j) if there is a rook at (i,j). Ignore the rooks placed on coordinates of the type (i,i) because those nodes form self loops. Now simply count the number of cycles in the graph.

    Now the answer is

    number of cycles + number of rooks not on any (i,i)

    This is my submission link 101935324

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

How to prove that ternary search will work in Div1B/2D?

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

What is point of having strict time limit for DIV2 B?
I am storing the digits of a number in set:
Advantage: I don't need to check for same digit again.
Disadvantage: Extra log factor
It is giving TLE.
101869576

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

    Same with me . Don't know whats the point of making those submission fails system test! Atleast , they could have added a pretest that would take longer time, so that people could get that point of log factor!

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

    I think its not due to log factor but constant factor of set. i am not sure.

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

First, note that the last digit will always be taken with a plus sign, and the one before the last — with a minus sign

Isn't it the first digit, not the one before the last?

Edit: Nvm, I understand why now.

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

D1E Walsh-Hadamard transform solution: https://codeforces.net/blog/entry/85746?#comment-735491

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

    Hey neckbotov, can you explain why can't we treat each vertex independently? I mean why not just find out if a vertex is winning or losing by simply traversing topological order in reverse. Essentially, why can't the grundy number for a vertex be 0 or 1?

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

      You may need to learn the nim game and sg number. 0/1 can represent a win/lose state, but it cannot do addition.

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

For Div2 C, how come we only need to consider the edge x->y and not y->x? I understand what is happening with the graph, and why cycles need an extra move to break, but do not understand why/how the graph construction relates to the problem.

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

    I constructed it with bidirectional edges and it worked as well if you accept multiple edges. Otherwise you wont be able to see the cycle of length 2 easily (for such a cycle you need two rooks that have switched coordinates, e.g. 1 2 and 2 1).

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

      That part makes sense now.

      Can you clarify why x->y and/or y->x should even be edges in the first place though? Does not seem intuitive to me why something like rooks={(1, 2), (2, 3)} should create the graph 1->2->3

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

        my idea was that a rook on row r and col c will guard the diag elements r,r and c,c. so if another rook has an eye on at least one of these elements then these two rooks are connected somehow. I came up with idea to use graphs as i recognized that rooks may or may not build cycles (a cycle of size 3 was in the sample). so i build the idea to find these cycles with graph theory and then it is pretty obvious that a rook is the connection between 2 nodes which represent a diagonal element.

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

    My implementation is bit different. I created graph of pairs — $$$(x,y).$$$ You can look at my code. Not sure, if it's helpful.

    I'll try to explain a bit.

    Start dfs from any pair $$$(a,b)$$$ if it is not visited and explore its connected component. A pair $$$(c,d)$$$ is connected to pair $$$(a,b)$$$ iff $$$d=a$$$ or $$$c=b$$$. I'm first assuming there is $$$cycle$$$ in the connected component. Start from $$$(a,b)$$$. If it has $$$0$$$ connected nodes, we are sure there will no cycle as we can put $$$(a,b)$$$ at any of the $$$2$$$ suitable points. If it has only $$$1$$$ connected node, we can be sure that there is no cycle (we can move that rook at only suitable point) but we will still put the only connected node into the stack (if its un-visited) to explore further total number of nodes in the connected component. If it has $$$2$$$ neighbor nodes, put them into stack (if they are un-visited).

    Finally, after each dfs, $$$ans+=x + c$$$ where $$$x$$$ is nodes in the connected component and $$$c=1$$$ if there is a cycle in the component else $$$0$$$

    I'm not sure if cycle is correct term for it but I mean is if in any connected component, if we find any node $$$(x,y)$$$ for which either of it's $$$2$$$ suitable positions is free, we can displace that rook to its any suitable position thus breaking the locks. If we can't find any such position, we have pay 1 extra than the total nodes in the component.

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

    Either will do, but not both. We need to move a rook from $$$(x,y)$$$ to either $$$(x,x)$$$ or $$$(y,y)$$$.

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

In Div1 B, I used binary/ternary search over prefix length, assuming the costs would be decreasing then increasing, but it failed system tests. I later got AC by just also checking the endpoints (0-length prefix and full prefix). I wonder if there is an easy way to characterize the cost function vs prefix length causing this to work.

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

    Another approach would be:-

    Make a copy of the original string (call it "ss"), and fill all '?' with '0' in string ss.

    Then calculate the answer for string ss and store it in "temp".

    Initialize "ans" and assign it the value of "temp".

    Then, start iterating backward in the original string s (i.e. from i=n-1). On positions where s has '?', recalculate temp by subtracting the number of comments if this position had '0' in it, and adding the term if this position would have '1' in it, greedily.

    Then, update:

    ans=min(ans,temp)

    The final minimum number of comments is obtained in "ans".

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

      Since we have to update prefix array(that stores either no of 1 or 0 upto i) every time we change from 0 to 1 in the string ss, so how should we implement that exactly....do we have to use segement tree or something else

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

        Check their submission. Apparently you can directly edit the string? I always thought they were immutable...

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

.

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

I solved A and B under 10 min. Can't solve C after 110 min. didn't read D. result is +31.

What is your advice ?

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

why his code got AC, but the same code I got TLE?

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

    Test case 12 has not been there at the time of the system test! It has been added later. xmt You're lucky to get away with that :D Anyway, you would be gaining CM I guess, Congrats!!

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

    The following change 101919959 fixes the issue. (Using the vis in while loop to validate)

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

can someone explain to me why div 2 c solution of xmt who came 2nd in div 2 is giving time limit exceed on test case 12 when I am trying to submit the same solution but his solution got accepted?[user:xmt][standings:https://codeforces.net/contest/1465/standings]

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

    The following change 101919959 fixes the issue. (Using the vis in while loop to validate)

    → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +41 Vote: I do not like it

I have an offline solution to F that involves pretty much no data structures. First, divide-and-conquer on time so that we only have to process $$$O(q \log(q))$$$ insertions (no deletions).

First, note that checking whether all paths are within $$$d$$$ of a given point is a lot like checking if the "diameter" is at most $$$2d$$$. In fact, this is exactly true; the minimum $$$d$$$ for which there is a vertex in the $$$d$$$-neighborhood is exactly 1/2 the maximum value of the shortest-path between some two paths in our set.

We can actually go a step further; let the "center" of the set of active paths be the set of vertices which minimize the maximum distance to any active path, and let the "radius" be this distance. The center is either the intersection of all active paths if it's nonempty (and the radius is 0), or a single point (the midpoint of the diameter). (Here, we allow points to lie halfway along an edge).

Now, we can show that for any other point, the maximum distance to any path is exactly the distance to the nearest center plus the radius; this follows for essentially the same arguments as for the center of a normal tree. Thus, in order to support new insertions, we only need to maintain the center(s) and radius of our current active set. Updating the center/radius when adding a new path is also easy; we can check if the path intersects our center(s), and potentially move the center towards that path. All of these operations can be implemented using only LCA/level ancestor. With standard LCA, we can solve this problem in $$$O(q \log(q) \log(n))$$$, and with precomputation, this should only take $$$O(n \log(n) + q \log(q))$$$ or even $$$O(n + q \log(q))$$$.

Implementation note: when the radius is positive, instead of maintaining the center, we can just maintain a diameter, i.e. a path with length $$$2 \cdot radius$$$ and midpoint at the center. This allows us to remove the level-ancestor queries.

AC in $$$O(q \log(q) \log(n))$$$: 101920713

AC in $$$O(n + q \log (q))$$$: 101921489

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

    I arrived at the same solution eventually. 101922707

    Instead of time D&C we can build a segment tree on all paths present in queries, and turn them on/off.

    Ideas from yesterday's 1458F - Range Diameter Sum were somewhat helpful.

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

      Ah, right, if you really want it to be fully online, you store the paths in an augmented BBST or a compressed segtree with implicit size $$$N^2$$$.

      It's funny that 1458F is related to a problem in this contest, and also problem B in the OpenCup GP of Xiaomi, all in the same weekend.

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

    Sorry for replying after a long time. I'm referring to your implementation and have some questions about the divide-and-conquer process. I noticed that your code may add an insertion twice to a segment tree node (though it doesn't matter in this problem). Does your solution still function correctly when maintaining information that doesn't have this property (for example, maintaining the sum of all elements)? If not, does raising $$$q$$$ to the nearest power of $$$2$$$ help?

    EDIT: I found this article, but I still can't understand why it is correct.

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

What's the proof for the greedy addition/subtraction in D1C?

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

    This is not a proof but let me share my idea.

    Let's consider the situation where all the signs are a minus sign(i.e. the n — 2 prefix signs are all minus signs) and you can turn an arbitrary minus sign into a plus sign. In this case, the result of calculation will become minimum. Let this value be V.

    When you want to obtain some value greater than V, it is always better to choose as big a number as possible and change its sign(but even after the change, V should not exceeds the value we want) because you want to adjust V with small numbers afterwards. (In other words, why do you use several small numbers to make a big number that already exists? You are missing out!)

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

      Can you please help me with the part on how we can obtain any sign we want on the first

      $$$n - 2$$$

      integers ? It was not clear to me from the editorial.

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

        Since we already have the observation that last is + and second last is -, we can find a way to split.
        For example: ---+++-+-++-+. We split left most - one by one, so it becomes +++-+-++-+. Then if remaining are all +, then we done. Or we find the left most - then split there, +++-+-++-+ => (---+)(+---++-+), so our left part also done. Then we recursively solve for the right part.
        The remaining split will looks like: +---++-+ => (-+)(--++-+) => ++-+ => (--+)(+) => +

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

          Wow ! I got it. So we just focus on the minus signs and do them one by one.

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

            Yeah, right. And choose right place to split so the last two elements are -+

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

    Yeah I also have the confusion, especially when we convert from negative to positive, like: -13 = -16 + 2 + 1 So when we meet -13, how can we decide whether +16 or just leave it here

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

    I struggle with it a lot yesterday, but the solution from ecnerwala convince me a lot, you can take a look at his stream.
    The basic idea is that he treat +-2^S[i] as -2^S[i] + (0 or 2^{S[i]+1}). So we can add all S[i] to T and decompose it into binary with power of i+1.
    More formally, sum(+-2^S[i]) = T => sum(2^S[i+1] or 0) = T + sum(2^S[i])

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 5   Vote: I like it +3 Vote: I do not like it

    Suppose number we need to reach is $$$tot$$$.Since sign of a[n],a[n-1] is fixed , we can subtract and add their powers from $$$tot$$$. Now we initialize $$$s=0$$$ and we need to reach $$$tot$$$ using characters from 1 till n-2 .

    I used following greedy method (and i hope editorial refers to same greedy method) : sort the string from 1 till n-2 . Now iterate from n-2 to 1 and if $$$s>tot$$$ subtract $$$2^{a[i]}$$$ else add.submission

    Proof : Suppose we are at index $$$i$$$ and $$$s>tot$$$ . If in optimal solution we do $$$s += 2^{a[i]}$$$ (contrary to what i mentioned) , then sum of numbers left , say $$$H$$$ , must be greater than $$$2^{a[i]}$$$ (otherwise $$$s + 2^{a[i]} - H > tot$$$ and answer won't exist) . Also since $$$H>2^{a[i]}$$$ and array is sorted , there must be some subset say $$$SS$$$ of $$$a[1],a[2],a[3]...a[i-1]$$$ such that sum of their power of 2 is equal to $$$2^{a[i]}$$$ .We also need to add subtract at least $$$2^{a[i]}$$$ in future , else $$$s$$$ will be greater than $$$tot$$$.

    But then we can do $$$s -= 2^{a[i]}$$$ instead and we can add sum of power of 2 of subset $$$SS$$$ in future. Similar proof for case $$$s<=tot$$$ .

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

    Poman Numbers ( Div2 E/ Div1 C )

    Explanation of the greedy part of the solution + Commented Code

    Code

    103545539

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

Can someone please explain to me D. Grime Zoo? Thanks.

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

Can there be any approach of c without using graphs?

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

Hi, could somebody please explain the following (D2E/D1C): Now the problem is reduced to whether we can get the number X using the first n−2 letters. Since the weights of the items are powers of two, we can choose them greedily.?

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

    Ques- Since the weights of the items are powers of two, we can choose them greedily,how?

    Ans --> Firstly, let T = abs(T) because if we can make T from the array then -T can also be made by just reversing the symbols i.e + to -; and viceversa.

    Now, get the sum of all elements and if sum is less than T then ans is clearly no, otherwise lets assume that T can be made using sum therefore sum_left = sum — T now for our assumption to be true we should be able to make val = sum_left/2 from the array elements :

    i) if sum_left is odd then our assumption is false and print 'no'

    ii)else we can simply check by sorting array in descending order and subtracting a[i] from val if val >= ai

    finally if val becomes 0 our assumption was true i.e print 'yes' else 'no'

    Code Link: 101958203

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

Can you share your solution to Div2 D? It is hard to find and interpret which submission uses the same approach mentioned in the editorial.

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

Can anyone tell why thus code is failing for 1234567890 https://codeforces.net/contest/1465/submission/101931003

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

    Your vector only contains n's digits, not x. Therefore, it will add +1 until the number x is divisible by the every digits n. My english is very bad, so i think you get the main idea

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

How to solve the Div2 C with dsu?

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

    I hope you know about DSU .If not , read here , very easy to understand.

    Suppose we have two vertices $$$v_1,v_2$$$ in the graph formed having edge between them . Then we connect root parent of $$$v_1$$$ and root parent of $$$v_2$$$ in DSU "join" operation . But while joining if we found that they are already in same tree (i.e have same root "parent") then there is a cycle since there was a path between $$$v_1,v_2$$$ earlier and thus adding one edge between them will make a cycle.

    Now count all the cycles using above method and use the formula either described in editorial or here.

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

How to solve div2-D with DP?

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

    From DP I think the time complexity would be O(n^2).

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

In question C, I got WA on test case 5. Here is link to my WA solution: here
Here is link to Accepted solution: here

Can anyone help me, what's the difference in both of dfs? Everything else is exact same.

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

    I also faced a similar issue

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

    Let's say there are 3 rooks at (a, b), (b, c) and (c, d). In your WA solution, if you start your dfs from c, you will mark c and d as visited and then call dfs(a), this will return true because c is marked visited, but it was from a different component, you need a way to differentiate the nodes marked visited in the dfs(a) call and the ones marked earlier, this is what you are doing in your AC solution when you mark them 1 during the call and 2 after the call is finished.

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

Hi anta.baka! What does variable "Roma" mean in your code? Was this code written by you? I can't find the variable "kukold" which you usually use..

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

Someone plss help me with problem B https://codeforces.net/contest/1465/submission/101926615

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

    use long long instead of int to avoid overflow

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

      It is still not working

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

        When you passed by value to your solve() function, it's accepting int, not long long. Change that and it's accepted.

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

Auto comment: topic has been updated by neckbotov (previous revision, new revision, compare).

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

In Div 2 D, how do we find which prefix of ? is optimal to be replaced by 1 (x >= y)? I tried brute force which gave TLE (reasonably so), then thought there might be only one global minimum (WA), and tried minimizing r-l (WA). I think the proof needs to be a bit more elaborate.

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

Can anyone explain D a bit clearly? I dont understand the editorial.

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

    WLOG assume $$$x > y$$$. Suppose we claim that replacing the question marks with a sequence like $$$10010$$$ gives best solution. The editorial just shows that you can change it to $$$11000$$$ to get a better solution (ie swapping 01 by 10 till it is not possible anymore). So in reality we do not know how many question mark get converted to 1, so we go over all prefixes of 1.

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

Auto comment: topic has been updated by neckbotov (previous revision, new revision, compare).

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

In problem Div1C/Div2E, can someone explain to me how the $$$+$$$ $$$-$$$ are chosen greedily, is it only possible if the weights were powers of two?

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

    By binary-search principle. Just sort all powers of two except the last two. Go from maximum number to minimum. Initially all signs is + From each number change the sign if and only if after change sum of all n 2-powers (let's name it sum) greater or equal to T. After all changings, if sum=T then answer is Yes

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

      OOH I got it thanks!!! But is it possible if the weights weren't powers of two?

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

        In this problem weights always are powers of 2, by the formula. If you about all problems, it's impossible. For example, you need to obtain -1 having 3 numbers: 5 4 2. This algorithm will swap sign of 5, sum will be equal to 1. After this, the algorithm won't obtain -1. But if remain sign of 5 and change signs of other numbers, sum is 5-4-2 = -1

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

I got TLE in Div.2\B(Fair Number) although I think that I did almost same as written in editorial. Here is my submission 101881464. What did I do wrong?

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

Another solution for div1E with GP summation of matrices (very similar to editorial, but another way to look)

Let $$$C_i$$$ be the number of grundy numbers with value $$$i$$$.

Since we need to find the number of

Let $$$P(T, X)$$$ be the probability the xor of the grundy numbers will be X after T turns.

$$$P(T, X) = \sum(ans(T-1, Y) * C_{X\oplus Y})/(n+1)$$$

$$$P(T)$$$ can be written as a matrix product of $$$M$$$ and $$$P(T - 1)$$$, where $$$M_{i,j} = C_{i\oplus j}$$$

$$$P(T) = P(T - 1) * M$$$

Probability that Bob wins is, $$$\sum_{t \geq 0} P(t, 0)/(n+1)$$$

$$$Q = \sum_{t \geq 0} P(t) = P(0) \times (M^0 + M^1+M^2..) = P(0) \times (I \times (I - M)^{-1})$$$

Probability that Alice wins is $$$1-Q(0)/(n+1)$$$

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

    Hey, Can you explain why can't we treat each vertex independently? I mean why not just find out if a vertex is winning or losing by simply traversing topological order in reverse. And then if we have X winning vertices[P(x) = X/(n+1)], then calculating the answer is pretty straightforward.

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

so i was little skeptical of the approach described in the editorial for Div 2 Question C — Peaceful Rooks, so i tried proving it on my own. please let me know if anything is incomplete, unclear or incorrect. hope this helps someone understand.

idea: if a set of coordinates form a cycle, it is impossible to move a rook from the set to a main diagonal square that is not guarded by another rook in the set.

for example take {(1,2),(2,3),(3,4),(4,1)}: notice that these 4 vertices are using 2 out of the same 4 numbers as both their x and y coordinates. therefore, every one of these 4 numbers must appear exactly twice in total in the set. (you can count them to check)

furthermore, if one chooses any pair (x,y) and tries to move it to (x,x) or (y,y) (the main diagonal), since there are always 2 pairs that contain any number, you can be sure that both of these coordinates will be guarded by some other rook (either their x or their y coordinate will coincide if it exists, and if there are two in total then it does)

generalizing, if we have n nodes that form a cycle, they choose 2 numbers from n numbers to use in their (x,y) coordinate pair. each of these n numbers appear twice — once as an x coordinate and once as a y coordinate, since no rooks attack each other. therefore none of the rooks can be moved to the main diagonal in this state, so we must waste a move breaking the cycle.

proposal: breaking a cycle necessarily allows the rooks that were originally in the cycle to be moved to the main diagonal (in some order) in exactly 1 move each (no more extra moves needed)

proof: first, note that (m < n) so there is always one horizontal empty and one vertical empty

therefore its always possible to break the cycle (moving a piece changes the set of numbers => cycle broken) now our set of numbers from the coordinates of the k pairs is k+1, and 2 of those numbers only appear once in the set: moving a rook horizontally into an allowed position adds a new x value to our set of numbers, and removes an occurrence the old one. the same holds for vertical by symmetry. so now we have at least 2 main diagonal options that are not guarded by another rook in the same set. (but this is not enough, see below question)

another insight is that once the cycle is broken, the rest of the rooks that did not move cannot form a cycle. this is because each rook has one edge going in and one going out, so if the rest of the rooks formed a cycle then the rook that was just moved has no way to fit in the cycle (the rest would already have 1 in and 1 out if they were in a cycle)

the question is, what if rooks from outside this formerly-cyclic-set-of-rooks guards all the main diagonal square options from this set?

let the rook that is moved to break the cycle be rook (a,b) before moving. now once we move this rook to a legal position (a position where no other rook is attack by this rook), say, (a+k,b) (there is always an empty vertical and horizontal so this is always possible) then the column a is now empty. recall that in the cyclic set, a number appears exactly once as an x coordinate and a y coordinate. so there must be some other rook with coordinates (i,a) to complement (a,b) for whatever column i. so since column a is now empty, (i,a) must be able to move to (a,a) in 1 move.

recursively there is now another rook (j,i) in the set for whatever column j. since (i,a) moved to (a,a), column i is empty. so (j,i) must be able to move to (i,i) in 1 move. so this process can be repeated until all the rest of the rooks in the formerly cyclic set can be moved to the main diagonal in 1 move.

this works without having to worry about the interference of rooks from outside the set, because when we move horizontally onto a new column, there is no rook on the same row and the new column is always empty. therefore it will never be guarded. by symmetry moving vertically is the same

now the only exception is the rook that we moved at first : the rook at (a+k,b). how do we know that it will always be able to move to the main diagonal in 1 move?

if u move (a,b) to (a+k,b), then originally there was some rook on (b,h) for some row h to complement (a,b). but recursively we showed that every rook aside from the first rook can be moved onto the main diagonal, so this rook (b,h) can be moved to (h,h) recursively (it does not move to (b,b) because our moved rook is on (a+k,b)). now after this rook moves away from the b column, that means that the b column is necessarily empty. so therefore our rook on (a+k,b) can be moved to (b,b) in one move

therefore, if a cycle formed by a set of rooks is broken (which it always can be), each rook in the set can now be moved to the main diagonal in exactly 1 move each.

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

    Really appreciate the hard work you have put in writing this explanation. Thanks :)

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

I am having difficulty in understanding the problem Div2D editorial. Can anyone help me understand it with DP?

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

can't understand how the formula from div2.D "sl=0,sr=1 (c1+1)*x+c0*x+out" calculates subsequences of 10 type INSIDE (l, r). E.g. ?101? where did we put "10" inside the formula above? Because out calculates only the cases where one of the elements is outside

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

    when it says sl = 0 and sr = 1, it is only calculating the contribution by sl and sr, thats why any subsequence of type "10" hasn`t been mentioned

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

Can someone explain the meaning of the editorial in Problem F when it says that it boils down to breaking the array into "threes and a remainder". I was not able to understand the solution mentioned.

EDIT — I got it. Ultimately, the permutation consists of some number of cycles. The number of days it lasts is equal to the products of the lengths of those cycles.

It is optimal to make each cycle length

$$$= 3$$$

. And if we have a remainder of

$$$1$$$

, then we must make 2 cycles of length

$$$2$$$

.

Suppose we have a cycle length

$$$L > 3$$$

. We can break it down into

$$$3 \times (L - 3)$$$

and get a greater product.

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

    Hi bro, do you know how to prove it is always optimal to take three?
    UPD: nvm, I find it

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

      We can prove it with Mathematical Induction and seperately with each modulus.

      Anyway, I did not understand how to apply this fact in the solution of the problem. Can you tell me how we construct cycles of length

      $$$3$$$

      in the permutation ?

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

        Sorry, I haven't looked into that part

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

        For any permutation of size $$$n$$$ that is also a single cycle of length $$$n$$$, you can renumber it such that:

        $$$ \left( p_1, p_2, \cdots, p_{n-1}, p_n \right) = \left( 2, 3, \cdots, n, 1 \right) $$$

        This is not a necessary step; just for convenience.

        Now, a cycle of size $$$n=a+b$$$ can be split into two cycles with size $$$a$$$ and $$$b$$$ each by swapping $$$p_a$$$ and $$$p_{a+1}$$$. If you are feeling doubtful, try with some small example (like $$$a=3, b=5$$$).

        On the other way around, you can also join two cycles by swapping any pair of $$$(p_i, p_j)$$$ values from each cycle.

        In this way, the cycles can be arbitrarily split and joined on each swap. Thus, after calculating the size of each cycle in the permutation, you don't have to think anymore about how cycles are made out of permutations. If the sizes of the cycles are $$${5, 3, 2}$$$ (which would mean $$$n=10$$$), then (for example) you can split 5 into $$$5=1+4$$$ or join 5 and 3 to form 8.

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

I tried problem C and my approach was using disjoint set union, however it is resulting in TLE in one of the test cases. The time complexity appears to be O(T*m). https://codeforces.net/contest/1411/submission/102050815 is my submission link. Could anyone please provide some suggestions on how I can improve my code? Thanks a lot in advance!

EDIT: I got it accepted now using fast I/O (and well "cheating"(although it should work even without knowing the test case, as the max size of the board possible is 10^5) on the last test case#12) https://codeforces.net/contest/1411/submission/102057925. But I would still appreciate some suggestions to optimize it further.

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

I find the proof for Div2F/Div1D, about why we want to get more cycles of length 3. Actually the theoretical maximum occurs when you split the given number into parts each of size e (= 2.71828).
Although this conclusion may be common to orange and red coders, but I think most people are unfamiliar with it. So I hope some reference of proof can be added into editorials in future. Thanks!

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

Do you have solution code for these problems?

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

Could anyone please help me to check if my solution of Div.2 C is correct? If it is correct, could you please try to prove that? Otherwise, could you please provide one test case to hack it?

I explain the process of my solution in the following part, you may understand the solution better through it.

First, I try to find rooks on cell $$$(x,y)$$$ such that there is no rook on the $$$x$$$-th row or on the $$$y$$$-th column, so that I can move it there in one move. To do that, I make a function called solve. Every time I move a rook from $$$(x,y)$$$ to $$$(x,x)$$$ or $$$(y,y)$$$, I check if there is going to be another rook satisfied the condition above because of this operation.

I used the function solve(i) for every $$$i$$$ such that $$$1 \le i \le m$$$ but I got WA. Then I change it into doing this operation $$$1000$$$ times so that I get AC.

Then I add $$$1$$$ to the answer for every $$$i$$$ such that $$$x_i \neq y_i$$$. Finally, I use DSU to calculate the number of cycles.

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

How to solve the bonus in Div1C?

→ Reply
»
4 years ago, # |
← Rev. 6   Vote: I like it +19 Vote: I do not like it

I've successfully uphacked 132 solutions now on div 2 B. Mostly PyPy solutions, but also Kotlin, Java, Python, Haskell and some C++ solutions. The hacking I've been doing is very simple. I made a counter test for solutions that abuse early exits (if the digits are read from the left). Note that C++ submissions usually read digits from the right, which is why I was only able to hack a few C++ submissions.

Problem setters, you should really think about what constraints you use next time! And if you for some reason find it interesting to have tight constraints then you REALLY should try to make good test cases for it!

EDIT: Gotten 391 successful uphacks now (on div 2 B)

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

    I agree that pushing constraints till limit is not always a best practice. But I was quite surprised to see that the limits were actually high to deny some solutions!

    If anyone tells me a problem:

    • has 1e3 cases
    • I/O is a single 64-bit integer per case
    • the solving step runs 2520 times at most
    • each step comprises of itoa and a few modular arithmetics

    Then I would have said that 2 seconds are just enough.

    The ×18 underlying in itoa, the early return scheme, and the environment being 32-bit (can I have a reference on this? It's been long since I read it) puts this TLE behavior on a precise blind spot that the setters failed to address.

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

      After testing more, I've realized that the issue with the constraints is mostly just due to $$$1e3 \cdot 2520 \cdot 18 \approx 4.5e8$$$ being huge. With a bad constant factor (like in Python calling int('1') over and over, or in C++ storing all digits in a vector) you simply get TLE.

      The way people avoided TLE during the contest was to abuse early exits in the divisibility checking. Unfortunately there were no good counter tests for this. So far I've TLE uphacked > 400 solutions (many submissions were from the contest). My opinion is that a div 2 B should not have tight constraints unless it stops some kind of unwanted solution. This time around I believe the constraints were simply unnecessarily tight.

      If problem setters for some reason find it fun/interesting to set tight constraints, then they should also make test cases for it. This time around the constraints were tight, but a ton of solutions still got through because of lacking system tests.

      and the environment being 32-bit

      If you are asking about why PyPy is 32 bit on CF: https://doc.pypy.org/en/latest/faq.html#what-is-needed-for-windows-64-support-of-pypy .

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

        So true! The 18 looks innocuously small like alphabetic 26 or digital 10 and that might be why the setters missed it, but it contributes much so that the resulting time complexity became something as large as $$$O(N^2 \log N)$$$ solutions for $$$N \approx 3000$$$ problems, which is dangerous enough.

        On the other hand, I keep thinking of the disaster that would have took place if the test included the worst cases...

        Your PyPy document link was also helpful, I didn't know this. Thank you!

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

Well, second task seems really easy, especially after I've read the solving, but my code is failing due to time error. How it may be optimised?

102395452

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

    As I wrote in the comment above yours I've been TLEing tons of PyPy solutions, and you got TLE on one of my test cases.

    The trick to avoid TLE is just to make your code run slightly faster. Easiest way is to switch x != '0' into x > '1'. Also try switching int(x) into (ord(x) - 48).

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

Help me with a problem for 1411G 1.before the process,what is the number of chips on vertex?0? 2.When Alice and bob are begining to play the game,is it meaning that the process is termitalely? 3.Can we think the number of chips are random?

→ Reply