antontrygubO_o's blog

By antontrygubO_o, 5 weeks ago, translation, 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...
 
 
 
 
  • Vote: I like it
  • +150
  • Vote: I do not like it

»
5 weeks ago, # |
Rev. 2   Vote: I like it +43 Vote: I do not like it

My last hour of yellow name :(

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

wow thank you for the fast editorial :D

»
5 weeks ago, # |
Rev. 7   Vote: I like it +222 Vote: I do not like it

F can be solved in $$$O(n^4)$$$. And I guess it can be solved in $$$O(n^2)$$$ per test case.

If $$$(a,b)$$$, then $$$(a+k-1, b+k)$$$ with $$$k\geq 4$$$ or $$$(a+k-1, b+k*(k+1)/2)$$$ with $$$k\geq 2$$$.

There is a tree structure about the permutation, which is called 析合树 in Chinese, named or invented by CommonAnts. We can derive this result directly from the tree structure. You can see these two 1 2 in Chinese for details.

And there are some similar problems with this combinatorial structure of the permutation, like NEERC 2018 I, and China Final 2018 B.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +316 Vote: I do not like it

    The Chinese have a Data structure for everything.

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 2   Vote: I like it +51 Vote: I do not like it

      Nobody:

      Chinese people: Let's make a Data Structure based on this problem.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    I think it is PQ-tree?

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      no you can do it by segment tree

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 2   Vote: I like it +11 Vote: I do not like it

      No, I think they look similar. PQ-tree tries to find a valid permutation with some given consecutive subsets, but “析合树” is to describe all consecutive subsegments of a permutation. The tree structure has two types of nodes, which are similar to Q-node and "P-node which is not Q-node" respectively. I mean, values of all sons of a first-type node (“合点”) are monotonic, and those of a second-type node (“析点”) form a simple permutation.

      I introduced the tree and an $$$O(n)$$$ algorithm to construct it for a given $$$n$$$-permutation on RAM (with linear RMQ). So that many such problems could be solved in linear time. For example, CF997E.

      In fact, this problem F could be solved in $$$O(n)$$$ time. We can make a valid permutation with at most $$$n$$$ items at first with greedy. After that, replace a leaf with remain items as a simple permutation. It's $$$O(n)$$$ by adjusting those conflicts of constant size (including corner cases of greedy, the extra one consecutive subsegment for the simple permutation and inexistence of a simple permutation of length $$$3$$$).

      Another similar structure I've ever seen is "separation tree for permutations". It only cares about the second-type nodes, and are for problems about simple permutations.

      A simple permutation is a permutation without consecutive subsegments.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      If a PQ-tree successfully constructs a permutation, it can be regarded as a virtual tree for a subset of nodes in the permutation's “析合树”, each Q-node is a first-type node “合点”, and each P-node can be either type, “析点” or “合点”, depending on which permutation you choose in construction.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    Problem setter & tester be like

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    I also solved it with $$$O(n^4)$$$ preprocessing with $$$O(n^2)$$$ per test case — I know how to improve this to $$$O(n)$$$ but I didn't bother. This is my idea, I have no idea why but it seems to work:

    If there is a solution for some $$$n,k$$$ then there is also a solution such that you start from some "disorderly" permutation of length $$$m \leq n$$$, and then in $$$n-m$$$ steps you either append a new maximum element to the permutation or append the new minimum to the permutation. A permutation of length $$$m$$$ is "disorderly" if its beauty is exactly $$$m+1$$$. I used dynamic programming to track the longest "increasing subsegment" suffix of the permutation, this tells me how many new good subsegments are added when the new maximum is appended. Code: 59129441

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Fastest Editorial I have seen in a while! Thanks :)

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +40 Vote: I do not like it

    So fastest that it was pulished 2 days ago!

    editorial

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I was able to solve Div2: C with some example that I wrote in the paper. I was trying to understand the derivation of editorial, but I am not able to understand it. Can someone please elaborate it more like why n even always has no answer?

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

    Consider taking some array from the circle. Then take next value and remove last value, on the same circle. The sum cannot stay the same, because that means what we removed and what we added is equal, and we cannot do that. So it either goes up or down by 1.

    Imagine sum increases by 1. We can write +1 near that number. After that, with same logic, next move has to decrease sum by 1, because increasing number twice gives us three numbers on blackboard: sum, sum + 1, sum + 2. So we can write -1 near that number.

    Now consider a circle with +1 and -1 instead of numbers. If it is odd, it starts and ends with same value — easy to see. And if it is even, is ends with different value and we are back at the sum. No two consecutive numbers (+1 or -1) must stay the same, as it is easy to see.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I didn't quite get the last paragraph of your answer, about the circle of -1 and +1. Can you elaborate a bit please? thanks in advance.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Let's create second circle of the same size, but with +1 or -1 inside, instead of numbers we put in. If it has length of n, we can label its nodes from 1 to n inclusive. Even ones have same sign, and all odd — labeled ones have different sign. The only place when it could go wrong is connection of n'th node to the first one. If they are both odd, they will have the same value, and we don't want that, as we showed. So 1 is odd and n has to be even

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          but the question asked to check in 1 to 2n. it doesn't matter if n is even or odd the last node and first will have a different sign. please explain why the n even is not possible??

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

            Yes, the borders work well since the circle is of even length. But there is another problem with even n.

            Consider doing one step around the circle I mentioned. Let's denote sum of all numbers on the circle S, and previous sum in our chosen interval A. The sum of elements we have not chosen will be B = S — A. If we get +1 as result, new sum is A + 1. What happens to B then? Since S stays constant, new B = B — 1. If we choose the second interval as initial one, we would have to write -1 on the next node.

            So if we have +1 on one side, then we need to have -1 on opposite side (and vice versa). If n is even, we get two sequences (+1 -1 +1 -1 ...) (+1 -1 +1 -1 ...) of length n each. Their first elements will have the same sign, which is contradictory

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Solution 59065438 How do you think ?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Iv got a simple proof for that.If input is n we have 2n numbers to arrange .the sum of these 2n nos is s=2n*(2n+1)/2 =n*(2n+1).since 2n+1 is always odd,s depends on n.now if n is even ,s can be divided in two equal parts(eg 18+18 for n=4) which we dont want as sum of no two consecutive n nos can not be equal.so n is odd.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is the answer to the bonus of Div1.A yes when k is odd

»
5 weeks ago, # |
  Vote: I like it -40 Vote: I do not like it

can someone please help me with my code. There is something strange.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it -20 Vote: I do not like it

    Why downvote? I post it because I am not able to understand why it is not printing all the $$$n$$$ strings. I had run the last for loop n times. But in the output it is printing only 3 rows. If someone can help then Please help!

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      probably your code print something other than 0/1 (-1 or something)

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can someone explain me what is the logic of Div-2 C problem?

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

    Look for a pattern. Let's start simple. If k = 3, n = 6, "1 4 5 2 3 6" would be the solution.`

    • Look at 1 4 5. This equals 10 for first 3 numbers.`
    • Look at 4 5 2. This equals 11 for next 3 numbers.`

    What did we do between both steps? We removed a smaller number to replace with a number that is 1+removed number.

    • Look at 5 2 3. This equals 10 again for next 3 numbers.

    We removed a larger number and added a number that is removed number-1.

    By doing this we get a pattern of 1%n, (1+3)%n, (1+3+1)%n, (1+3+1+3)%n... Please correct me if I explained wrong.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Somebody pls check and tell what's wrong with my code for Div 2 problem B !! code

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    input :
    3
    -1 0 1
    output: 1
    yours: 3

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Try your code with case -2 0 2 the answer is 3, 0's distance to 1 and -1 is same so it does not makes any diffarence to make 0 1 or -1. So if the count of negatives % 2 is equal to 1 you can make that 0 with a zero. I couldn't look well to your code but it may be the wrong thing, I hope it helps.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Currently, you are ALWAYS making 0 go to 1. However, 0 can also go to -1 for the same cost (1).

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain how to solve problem Div2 D?? I am not able to understand the editorial...

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I did it this way- The maximum number in the input is 10^18 which can be represented in 64 bits. The minimum possible cycle can be of length 3. If we have the xth bit set in any 3 numbers, then we are done! (all 3 will be mutually connected because of non zero "and") There are at max 64 bits. => If we have more than 128 non zero numbers (By PHP) in the array, then we will get a cycle of length 3.

    Now for <= 128 non zero numbers. We can check by actually making a graph. It will take O(m^2), which will be well within the bounds.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How do you come up with the "128 non-zero numbers" logic?

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

        10^18 fits well inside 64 bits. We need a minimum of 3 set bits at any common position. By Pigeon Hole Principle if we have more than 64*2 = 128 numbers (non zero because zero has none of the bits set) then at least one of the position will have 3 set bits. (The bound of 128 can be made stricter if you calculate the exact number of bits needed to represent 10^18)

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          how does having >128 numbers guarantee that there will be at least 3 numbers having set bit at the same position? (I'm not saying the answer is wrong, i wanted to know how php is used here)

»
5 weeks ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

For the problem, Shortest Cycle ,in the test case with n=10^5 and large numbers, making an adjacency list is causing Memory Limit Exceeded Error. How to prevent this?

Edit: Just note if too many edges (thus giving memory limit exceeded) then there is a triangle.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

div1 a. i noticed a beautiful pattern by connecting numbers on circle sequentially. my solution was 0 3 4 7 8..., i.e., +3 +1 under modulo 2*n,now join 0->1,1->2..2*n-1->1and so on it makes flower like pattern on paper.really amazed after seeing that.

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Thank you for your challenging problems and educative tutorials! But I was caught with some trouble at problem D... 59056716 I tested this submission with test 15 both on my local Windows machine and codeforces custom invocation. Both are resulted in 3. But every attempt to submit turned out to be Wrong answer on test 15...

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    OH I thought I have made some mistakes...

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Maybe I pasted some other test data by mistake... Finally I found out my fault, then I formed a bfs tree, to judge the size of rings by LCA![submission:59058541]

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For 1206 D, 1205 B Another way, If the no. of non-zero elements > 120 ( 2*log2(10^18) ) then we must surely have a 3-cycle. Otherwise, for all vertices v, do BFS traversal to find length of shortest cycle through v and take minimum. This will be in O(V*(V+E)) time and O(V+E)(max O(V*V)) memory. Not much efficient though.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My solution 59056716 is very close to that, but I strangely recieved a WA on test 15, while I surely got the correct answer in codeforces custom invocation...

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Custom Invocation gives 5!=3.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Awwww I see... I'm going to keep debugging...

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thank you! Finally I formed a bfs tree and judge the size of rings by LCA![submission:59058541]

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why am I getting WA on test 5 59056925 in problem D ? I think I misunderstood the problem. Can someone show me how the answer for test 5 is 4 ?

»
5 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

In Div-2D, can someone explain why using set as Adjacency list gives AC int the following code 59059506 whereas using Vector as Adjacency list gives WA in this code 59057776

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Given that you are getting WA on TC 14, it is probably because two values can share more than one bit, so the vector representation would have multiple edges going between the same two nodes, which would allow a cycle of length two.

»
5 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Finally I left div2.. Nice problems, but solving them from smartphone is incredible as usual :(

»
5 weeks ago, # |
  Vote: I like it +25 Vote: I do not like it

For div2,D If the number of non_zero numbers is more than or equal to 119 ,we can just output 3.(Pigeonhole Principle,think of each bit as a pigeonhole,and think of each non_zero number as a pigeon) If it is less than 119,we can just use Floyd algorithm,we can solve it in O(n^3).

This might be a little bit easier to understand.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In problem D of div 2, I am getting TLE, in a test case where each input is 0, so basically I am getting TLE while reading 10^5 numbers, which are zeros. Strange!! code: https://codeforces.com/contest/1206/submission/59088647

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I tried to implement Floyd in the contest but failed coz I discover a problem: say there's an edge u -> v, Floyd will find a cycle path of "u -> v -> u" coz this is an undirected graph. And I don't know how to counter this problem. Do you know if there's any tweak I can do to make Floyd work?

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      http://codeforces.com/problemset/submission/1206/59043624 This is my solution.I hope it can help you.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks for the reply, is it ok for you explain these two lines of code?

            for(int i = 0;i < k;i++)
            for(int j = 0;j < i;j++)
        
        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          It's not quite easy to explain. It's just a way to avoid the situation you said above.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Kindly explain the above lines if you have understood them!

          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            This loop is essentially enumerating all the pairs that satisfies 0 <= i,j < k. The shortest path between any pair can only include Vertex 1 ... Vertex k — 1 according to the property of Floyd algo. So here we can enumerate all the cycles that contains Vertex 1 ... Vertex k. When k iterate from Vertex 0 to Vertex n, we basically covers all the possible cycles in the graph.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please explain how to use Floyd's algorithm for finding the shortest path? (I read somewhere it couldn't be used for undirected graphs). It would be of great help. Thank You.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain me the proof of div2 C,i basically did some cases and realized that if the number is even there is no solution, but i cant prove it.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    "Now, if n is even, we get a contradiction, since ai+n−ai=−(a(i+n)+n−ai+n)ai+n−ai=−(a(i+n)+n−ai+n), but due to the alternating they must be equal."

»
5 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

Problem B.Div2 is interesting.59065083 :D

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi could someone tell me why this is failing for "Make Product Equal One" https://codeforces.com/contest/1206/submission/59025115 locally I'm getting correct answer for the same input, is it some IO issue with Golang?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Also, what you could do in DIV 2 problem B was to first find the cost to convert all the numbers (ie. arr[i]) to 1 (ie. costOne) and -1 (ie. costMOne) and let the difference between the cost to convert to 1 and to -1 be c[i] (costOne — costMOne) for the element arr[i].

This means that you have 2 sets of numbers, first : the set which is closer to 1 (ie. arr[i]>0 or c[i]<0) and the second : the set which is closer to -1(ie. arr[i)<=0 or c[i]>=0)

Assume all elements to be closer to 1 and convert all the elements to 1 (ie summation of abs(arr[i] — 1) ) which assigns the value 1 to the current total product 'totalProduct'. Now, just convert those numbers that were closer to -1 (ie. arr[i]<=0 or c[i]>=0). Meaning, you now have to greedily remove EVEN number of elements such that your product in the end still remains 1 (ie. sort c[i] in descending order and remove EVEN maximum number of elements you can from it. let the number of elements in c be n, so remove n elements if n is even or n-1 if it is odd). Removing these elements from c means decreasing the value of totalProduct by c[i] for each element removed.

This is in asymptotic O(n) time.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In Problem D, I first checked for the 3 length cycle case as given in editorial and then I'm finding the minimum length cycle for the other case by taking each vertex as root and seeing if it is in the cycle or not, cases with some non-zero inputs and n = 100000 are passing but the case with all zero inputs and n = 100000 is giving TLE. I'm unable to understand why in case of all zeros it is giving TLE.
Submission — 59060203

»
5 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

Can someone explain the first approach of div1C in more depth? Apart from the dp part. Thanks in advance.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Div1 D solution doesn't seem natural I think.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How can solve 1D in $$$O(n)$$$? I think "divide the subtrees of the childs into two groups" need $$$O(n\log n)$$$...

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

In problem D of div 2, I am getting TLE, in a test case where each input is 0, so basically I am getting TLE while reading 10^5 numbers, which are zeros. Strange!! code: https://codeforces.com/contest/1206/submission/59088647

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

can anyone please explain the bit part I have no idea of binary represntation or bit may be thats why I didnt understand the solution. Can anyone please explain it easily from scratch. Sorry for my poor english. Thanks a lot :)

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

    So assume a bit can hold either a 0 or a 1. Basically its a digit within a binary sequence. If you know base conversion from binary to decimal, then you understand that 2^60 is roughly greater than 10E18. This also means that you can have a total of 60 binary digits (aka bytes).

    Now, the AND operator returns true if any byte overlaps with a 1. Now, note this: You can only have 60 non zero numbers that do not have any byte overlaps.

    If you have greater than 60, then you are guaranteed at least one byte overlap. Now, if were to assume each byte has an overlap once with another number's byte, then we would have 120 non zero numbers. Any number added beyond 120 non zero numbers would mean, 2 overlaps for a certain digit. This would mean the shortest cycle is 3.

    If you have < 120 non zero numbers, then you can use BFS on each vertex to find the shortest cycle.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Many of you can't solve Div2 C. When you need to construct an array to solve a promblem,just construct it boldly. Don't be afraid.

For this problem, let v be some number of the array(a[i]),let v' be the number opposite v(a[i+n]). Then the circle was cut into halves.let s1 = a[i+1] + ... + a[i+n-1],s2 = a[i+n+1] + a[i+n+2] + ... + a[i-1]. if n is an even number,it means that 2 is a divisor of the sum of all numbers,let it be 2k. The sum of any n consecutive numbers must be k.So,v + s1 = k,v' + s1 =k.v = v'!It's impossible.

if n is an odd number,it means that the sum of all numbers can be written as 2k+1. Then |(v + s1) — (v' + s1)| must be 1.It means v — v' = 1 or -1. Just construct it boldly.I said to my self when I was trying solving this. What we want is for any i,s1 = k or k+1.Now we have n groups:(1,2)(3,4)...

Why not let s1 for v = 1 1 + 4 + 5 + 8 + 9 + 12 + 13 + ... ? (We choose the first one in the first group,second one in the second group,first one in the third group...)It can be proved right.

I won't write down the proof.(I didn't prove the algorithm at all when I was participating the contest,but luckily my thought was corret. :D )The proof was already given in the editorial.

(I'm a Chinese student,there might be some grammar mistakes.Please forgive me for this and upvote for me.Thanks.)

»
5 weeks ago, # |
Rev. 4   Vote: I like it +28 Vote: I do not like it

Div1 Problem E can be solved in the time complexity of O(n log n) with Möbius inversion formula : let define that

$$$ [ P ]= \begin{cases} 1, & \text {if P is true} \\ 0, & \text{if P is false} \end{cases} $$$

try to enumerate i1,j1 , whose gcd is d , and simplify the formula it with Möbius inversion now we have

$$$Answer=\sum_{i_1,j_1\in [1,n-1],d=gcd(i_1,j_1)}([i_1+j_1-n\lt d]*k^{d-n}+[i_1+j_1-n\geq d]*k^{i_1+j_1-2n})$$$
$$$Answer=\sum_{d=1}^{n-1}\sum_{i_1,j_1\in [1,n-1]}[d=gcd(i_1,j_1)]([i_1+j_1-n\lt d]*k^{d-n}+[i_1+j_1-n\geq d]*k^{i_1+j_1-2n})$$$

using the inversion:

$$$[n=1]=\sum_{p|n}\mu(p)\ \ ,\mu(x)is\ Möbius\ function $$$
$$$gcd(a,b)=d\ <=>\ gcd(\frac ad,\frac bd)=1$$$

we can derive that

$$$Answer=\sum_{d=1}^{n-1}\sum_{i_1,j_1\in [1,n-1]}([i_1+j_1-n\lt d]*k^{d-n}+[i_1+j_1-n\geq d]*k^{i_1+j_1-2n})\sum_{p|gcd(i_1/d,j_1/d)}\mu(p)$$$
$$$\because p|gcd(i_1/d,j_1/d)<=>pd|i_1\ and\ pd|j_1$$$
$$$\therefore Answer=\sum_{d=1}^{n-1}\sum_{pd<n}\mu(p)\sum_{pd|i_1,pd|j_1}([i_1+j_1-n\lt d]*k^{d-n}+[i_1+j_1-n\geq d]*k^{i_1+j_1-2n})$$$

let $\ i\ ,\ j$ take the place of $$$\frac{i_1}{pd}\ ,\ \frac{j_1}{pd}$$$ we have

$$$Answer=\sum_{d=1}^{n-1}\sum_{pd<n}\mu(p)\sum_{i,j\in[1,\frac{n-1}{pd}]}([i+j\leq \frac{n-1+d}{pd}]*k^{d-n}+[i+j\gt \frac{n-1+d}{pd}]*k^{(i+j)pd-2n})$$$

then we can enumerate$T=i+j$ the latter formula turns into some "calculate the sum of geometric progression" questions

the former two $$$\sum$$$ can be enumerated in $$$O(n \log n)$$$ the latter formula can be calculated in $$$O(1)$$$ with $$$O(n \log n)$$$ pretreatment

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone pls prove this in Div1E?

The case of i1+j1≤n is obvious: in this case, by subtracting and adding i1,j1 we can show that the string has period gcd(i1,j1), in this case comps=gcd(i1,j1). We now consider the case when i1+j1>n.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me figure out the complexity of D problem. There could be at max 60 edges and for each edge we perform a BFS to find the shortest distance between its end points. And there are n vertices, so total complexity of performing repeated bfs would be 60^2*(n+60). And in order to construct the graph the work would be n*(log10^18) so overall — n*(log10^18) + 60^2*(n+60). Could someone tell me if my analysis is correct. Thanks in advance.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No!! There are at most 60 edges in a graph and removing each edge and doing bfs would cost me at most 60 operations . so overall our complexity would be (60)^2. You could have also used bellman ford for this but there time complexity would have been (60)^3 in worst case.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    60 edges can connect at most 120 vertices. So rest of the vertices have zero degree, you don't have to do BFS on them. For example, you can do BFS on the connected component of source only. So my guess is, depending on the implementation the complexity may vary.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can anyone please explain the bit part I have no idea of binary represntation or bit may be thats why I didnt understand the solution. Can anyone please explain it easily from scratch. Sorry for my poor english. Thanks a lot :)

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone got the answer for the above chanllenge (1205A)? I dont see any comments about it

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please explain to me how to find the shortest cycle using the Floyd Warshall's algorithm??

  • »
    »
    5 weeks ago, # ^ |
    Rev. 9   Vote: I like it 0 Vote: I do not like it

    Define $$$dp[i][j][k]$$$ as the shortest path from $$$i$$$ to $$$j$$$ using upto prefix $$$k$$$ of vertices, then shortest cycle length is $$$dp[i][i][n]$$$.

    So basically you find the shortest path from vertex $$$i$$$ to $$$i$$$ itself. Make sure during initialization you set, $$$dp[i][i][k] = \infty, \forall k \in [0, n]$$$ and during transitions, avoid going from $$$i$$$ to $$$i$$$ through $$$i$$$(Well, actually this happens automatically if you set $$$dp[i][i][0] = \infty$$$).(Prerequisite: Basic version of Floyd Warshall)

    Setting $$$dp[i][i][0] = \infty$$$ is mathematical way of saying that there is no path from vertex $$$i$$$ to $$$i$$$ without going through any vertex.

    EDIT: This only works for Directed graphs, in undirected graphs, this won't work(Since each edge of Undirected Graph == 2-length cycle of Directed Graph), see explanation here, https://qr.ae/TWreWj

»
5 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

For Div 2 D, can I assume that finding the MST and adding one of the remaining edges will give the shortest cycle?

If not, why? Thank you.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

DIV 2 1206 C PROBLEM: I can't understand editorial's last line, can any one help me. Please:

If n is odd, then it's now easy to build an example: for i from 1 to n ai=2i−1, ai=2i, if i is even, and ai=2i , ai=2i−1 if i is odd.

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

How does the checker work fast enough to determine whether there exists a palindromic path if I query distant points in Div.1 problem C?

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    I come up with an idea look at this :

    if dp[i][j][k][l]=1 means there is a Palindromic Paths from (i,j) to (k,l),0 otherwise.

    update: dp[i][j][i][j]=1,dp[i][j][i+1][j]=(a[i][j]==a[i+1][j]),dp[i][j][i][j+1]=(a[i][j]==a[i][j+1])

    if(a[i][j]=a[k][l])

    dp[i][j][k][l]=dp[i+1][j][k-1][l]|dp[i+1][j][k][l-1]|dp[i][j+1][k-1][l]|dp[i][j+1][k][l-1];

    else

    dp[i][j][k][l]=0;

    Do you think it's right?

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      And complete is O(n^4),it's fast enough

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Could anyone please explain the second solution of Div.1 C more clearly?

"Thus, the algorithm is as follows: choose any path between $$$(1,1)$$$ and $$$(4,4)$$$, find on it four cells with a xor of numbers equal to $$$0$$$, and ask a question about it."

Why does there exist a path from $$$(1,1)$$$ to $$$(4,4)$$$ such that the xor is equal to $$$0$$$?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How did you guys come up with generating the sequence for odd numbers in Problem C-Almost Equal?

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

http://ideone.com/5bc3Ib code if you don't understand any solutions and explanations of Div2 C problem like me(just brute force which shows you valid sequences)

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

for B wouldnt the answer always be 2 since if a[i] & a[j] != 0, then in the graph there will be an edge of weight 1 from i to j. since a[j] & a[i] != 0 as well. we will get an edge from j to i, which is a back edge of weight 1. this would mean the shortest cycle is of weight 2 always?

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

    In the announcement they mentioned this :

    Note that the graph does not contain parallel edges. Therefore, one edge can not be a cycle. A cycle should contain at least three distinct vertices.

»
13 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

.

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain the Problem 1205B(Shortest Cycle) ; I am unable to understand the editorial , It would be helpfull if someone explains it in a simple way . Thanks in advance !

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Useful for 1206C/1205A