Tlatoani's blog

By Tlatoani, 11 months ago, In English

We hope all of you enjoyed the round! This round has been a long time in the making -- the oldest problem in it is H, which was actually originally proposed for the rounds that eventually became Codeforces Round #655 (Div. 2) and Codeforces Global Round 10.

The tutorial for E and implementations for all problems are now available.

A - Windblume Ode
B - Omkar and Heavenly Tree
C - Omkar and Determination
D - Omkar and the Meaning of Life
E - Moment of Bloom
F - Defender of Childhood Dreams
G - Omkar and Time Travel
H - Omkar and Tours
 
 
 
 
  • Vote: I like it
  • +349
  • Vote: I do not like it

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

Thanks for the great contest and fast editorial!

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

Thanks for the fun contest!

»
11 months ago, # |
Rev. 2   Vote: I like it +208 Vote: I do not like it

The bonus of D !

Asking $$$A=[1,1,\dots,k]$$$​​​​ in which $$$k=2,3,\dots $$$​​​​, when the first time get answer $$$0$$$​​​, there is $$$p_n=n-k+1$$$​​​ if this is the $$$k$$$​​​-th query. What's more, if the answer to $$$u$$$​​​-th query is $$$b_u$$$​​​, then $$$p_{b_u}=p_n+u$$$​​. Now we get the position of $$$b_n,b_{n}+1,\dots n$$$ and only make $$$n-p_n$$$ queries.

Then asking $$$a_i=n$$$ if $$$p_i$$$ is determined, $$$a_i=k$$$ if else, from $$$k=1$$$ to $$$k=p_n-1$$$. If the answer to $$$u$$$-th query is $$$c_u$$$, then $$$p_{c_u}=p_n-u$$$.

Now we get the position of all numbers and only make $$$n$$$ queries.

And here is my solution

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

    great solution! I used similar way to find A[n], but I performed another n — 1 queries to determine other elements.

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

    The solution 1 of D can also be optimized to omit $$$n-1$$$ queries.

    You can record for each $$$j$$$, the index $$$prev_j$$$ such that $$$p_{prev_j}=p_j-1$$$.

    When you set $$$y\to next_x$$$, set $$$x\to prev_y$$$, and vice versa.

    You can ask like the solution 1, but since queries only find smaller index of the two equal $$$s_j$$$, you can visit $$$j$$$ from $$$n$$$ to $$$1$$$. If the $$$next_j$$$ is determined by previous queries, you can omit the query of the first type(i.e. a query with all $$$1$$$s except that $$$p_j=2$$$). If the $$$prev_j$$$ is determined by previous queries, you can omit the query of the second type(i.e. a query with all $$$2$$$s except that $$$p_j=1$$$).

    Since for each $$$x$$$ from $$$0$$$ to $$$n$$$, the relative position of $$$x$$$ and $$$x+1$$$only requires 1 query to determine(when $$$p_j=1$$$, we should also ask about $$$prev_j$$$(which shouldn't appear), we assume that there's an $$$0$$$ which is $$$prev_j$$$, and the same to the index j that $$$p_j=n$$$), you can solve the problem with $$$n+1$$$ queries.

    My solution

    (I only know a little English; sorry for that.)

  • »
    »
    11 months ago, # ^ |
      Vote: I like it -34 Vote: I do not like it
    if(tot>n+n){
    		cerr<<"fuck";
    	}
    

    Nice...

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

      lul.. this was actually funny.. don't know why ppl down-voted you though :(

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello Codeforces! I'm having a problem when adding problems to favorites and that is that no more than five are added!!! ಥ‿ಥ I would like to have a selection of problems, which for my taste are interesting to solve, so I can give them a look in the future. Any comments about this?

Thank you very much in advance! (~ ̄³ ̄)~

»
11 months ago, # |
  Vote: I like it +48 Vote: I do not like it
Spoiler

By the way, the girl is that "Hu Tao" in problem E.

»
11 months ago, # |
  Vote: I like it -18 Vote: I do not like it

Really a tough contest.. waiting for rating to go down....

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

Hi, Can someone point out mistake in my Submission. I feel I might have over complicated the problem lol. https://codeforces.com/contest/1586/submission/132264009

UPD: I passed the problem without segtree, turns out I was obviously Over complicating it :)

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

Nice problems! E and F should've been swapped imo. E was so tedious to formulate and code. Think F would have far more solves if it were in place of E. Took an hour on E and missed F by a whisker cause of one dumb typo ~>_<~

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

The editorial for problem D does not respect the requirement $$$1 \leq a_j \leq n$$$ on the queries. (But it is trivial to fix this.)

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

I am sorry but in problem E the editorial does proves only the fact that if every vertex appears even number of times, then answer is 0.

How to prove that ANY spanning tree works if we wanna find out the minimum number of queries to be added? This is the hard part.

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +26 Vote: I do not like it
    A more rigorous proof for E
    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think you just proved what the editorial proved. I was asking for the proof of the second part: when the answer is NO, and we have to find the minimum number of queries to be added. why does dp in any spanning tree work?

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

        The editorial is indeed incomplete in the part when the answer is NO, but in my opinion it is much easier than when the answer is YES.

        When the answer is NO, we just need to add queries so that all $$$f_v$$$ are even. The minimum such number is the number of values of $$$v$$$ such that $$$f_v$$$ is odd, divided by 2.

        We need at least that many extra queries since each query added can change at most two $$$f_v$$$ values. On the other hand, we can achieve this number of queries by pairing up the odd $$$f_v$$$'s (there are an even number of them since the sum of all $$$f_v$$$ is even).

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

          Wow, I didn't realise that there is no need for tree dp. Thanks a lot.

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

          Thank you. That's way better than the editorial

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

    Any (nonsimple) cycle in a tree visits every edge an even number of times.

    If every vertex is the endpoint of an even number of paths, the paths can be arranged into cycles: to form a cycle, take any path, say from $$$a_1$$$ to $$$a_2$$$. Then take any path from $$$a_2$$$, say to $$$a_3$$$. Repeat until $$$a_t = a_1$$$. This must happen, as the only vertices that an odd amount of paths start after the first $$$j - 1$$$ edges are $$$a_1$$$ and $$$a_j$$$.

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

      But this is the proof for YES case. I was talking about how to prove when the answer is NO, that is OK to take any spanning tree.

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

        The spanning tree is only used for the YES case. Read the solution more carefully.

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

          Actually in my solution, I used spanning tree for my NO case also. I did dp on that tree. So I was confused.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone help me with solution C 132264422

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

    u only checked for indices which are "." but u should also check for "X" too a simple example is this XX XX your code will give YES for it but ans should be no as following will also produce same EN grid XX X.

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

      sorry ,I am not getting. please,can you elaborate?

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

My approach to F was different, and allows for a trivial lower bound proof.

Fix the number of colours $$$c$$$ you will be using. For every node $$$i$$$, define the array $$$LEN[i]$$$ such that $$$LEN[i][t]$$$ is the length of the longest monocoloured path of colour $$$t$$$ from node $$$i$$$. In a valid solution, we have $$$0 \leq LEN[i][t] < k$$$.

Take any optimal solution and consider these arrays. Let $$$t$$$ be the colour of the edge from $$$i$$$ to $$$j$$$. Then $$$LEN[i][t] \geq LEN[j][t] + 1$$$. This immediately shows that we must have $$$LEN[i] \neq LEN[j]$$$ for all $$$i \neq j$$$. Since there are $$$k^c$$$ different arrays, any valid solution must thus have $$$n \leq k^c$$$.

Also, given that $$$n \leq k^c$$$, we can construct a solution by assigning the possible arrays in lexicographically decreasing order.

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

Although I failed this contest, I really liked the originality of problem B !

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

Great contest! For those who prefer video explanations, I explain solutions to all problems except I and G at the end of my screencast here.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My first time to solve an interactive problem! Stuck at E and tried G but withdrew...

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

my solution to D is working in my device properly but when i submitted it showed TLE on permutation {1,2} anyone kindly help 132260554

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

    The last (truncated) query would be "? 3 1". That violates constraint stated in the problem: $$$1 \le a_j \le n$$$.

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

Here are the video solutions to the first 4 problems. solutions

»
11 months ago, # |
Rev. 2   Vote: I like it +62 Vote: I do not like it

My feedback on A-G:

  • A: The idea is fine but I don't like that we have to print out the subset (I can understand the reason behind this though).
  • B: This feels like a hit or miss problem for me. I almost thought that we could ignore the tree condition and construct a line instead. Fortunately, I took my time and tried to use the special condition.
  • C: This seems a bit difficult for its position. I would rate this somewhere between A and B in a Div 1 round. Consider that we have 6 problems after this and only 135 min, I would prefer an easier one.
  • D: Nice problem that allows many approaches. Mine was also to find $$$p_n$$$ but in a different way from the one above.
  • E: This one feels oddly crafted for me. You have to think why it's okay to just keep a tree (I tried to prove it but I doubt everyone would do, because printing out the paths would be too difficult if it's not true). I would rather be given a tree and asked to print out the paths in the "NO" case.
  • F: I love how simple yet elegant the solution for this is. Props to the author for such a great problem.
  • G: Harder version of 1552F - Муравьепортация but the overall idea is quite similar. The strong sample tests definitely help, too. I wish I went for this instead of F in the contest. 27 ACs seem to be a problem position effect instead.

UPD: added G

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

Another way to construct a coloring for F is to think about the indices $$$0$$$ to $$$n-1$$$ in base $$$k$$$. Color the edge from $$$a$$$ to $$$b$$$ by the position of the most significant digit that changes. There is no path of length $$$k$$$ with only one color as the most significant digit that changes can only increase $$$k-1$$$ times.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This might be a stupid question but could someone please clarify B for me? If a , b, and c are distinct then (a,b,c) can never eliminate paths which consist of one edge for example 1, 2 or 1, 3 so why would this solution where you root the tree at 1 not work? For example, for the first test case with 7 nodes and 4 restrictions couldn't we make paths, (1,2) (1,3) (1,4) (1,5) (1,6) (1,7) since the restrictions don't apply to such paths?

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow, how beautiful the solution to F is!

»
11 months ago, # |
  Vote: I like it -13 Vote: I do not like it

Thanks for the interesting problems and +114 rating!

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

Can I asked for a solution in problem B if (m >= n)?

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

    can think of m<2*n

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

      Can you show your idea :D?

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

        actually when i wrote that comment i thought the wrong way but after thinking a lot i concluded that for m>=n there exists such an input for which solution is not possible ex: suppose n=m=6 consider the following 6 constraints {(1,2,6),(1,3,6),(1,4,6),(1,5,6),(1,6,2),(2,1,6)} here considering first 4 no node can be between 1 and 6 so u are forced to connect 1-6 if done this u cannot add 2 to either side as it will always violate the either of the last 2 constraints,,,,, may be there is a solution for some special cases for m>=n

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

    Here's a solution sketch for $$$m \leq n + 1$$$.

    m = n
    m=n+1

    It may be possible to push this idea a bit further, but it seems likely to get hairy fast.

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

      Thanks, I can understand your idea. When I first saw this problem, I was confused before reading its constraint.

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

I'm curious about the special judge for problem B.How to check an output is valid or not quickly(I can only thought about a data structure which is O(n log^2 n))?

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

    Notice that $$$b$$$ lie on the simple path between nodes $$$a$$$ and $$$c$$$ if and only if $$$dist(a,b)+dist(b,c)=dist(a,c)$$$.

    So all you need is a method to get LCA of two nodes.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you , Hutao , for this fantastic contest . The division degree is good.

»
11 months ago, # |
Rev. 2   Vote: I like it +16 Vote: I do not like it

In problem H,I have a different way on maintaining the information.

After off-line the queries,it requires us to find out the maximal toll on the road to the reachable cities with the maximum enjoyment value.And the maximum enjoyment could be saved on Link-Cut-tree with set maintaining the maximum value of each node subtree,while the maximal toll could be found at the same time.

Unfortunately,I would have thought that 3 seconds were enough for n log^2 n.It took me more an hour to get the program faster and faster.In the end,I control the size of each set no more than 3,because there is no edge cutting operation,with the time complexity O(n log n).

I have only solved A and H,and I have known I'm doing wrong.Now,I'm learning how to use binary search.

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

    3 seconds are indeed enough for O(n log^2 n).
    I just solved problem H (as practice), and I used DSU on tree to bruteforcely merge the cities with maximum enjoyment in two sets.
    The time complexity is O(n log^2 n) with a big constant from vector operations, and it runs surprisingly fast (<500ms).

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

      With set,maybe LCT has a larger constant and the complexity is more than O(97 n log n)(Top-Tree's complexity).I'll use these data structures more carefully next time.

      And thanks for solving my puzzle.

»
11 months ago, # |
Rev. 2   Vote: I like it +31 Vote: I do not like it

A stupid $$$O((n+q) \log^2 (n+q))$$$ solution for H:

First find out the answer to the first question using dsu. Then do centroid decomposition to find out the second answer. Let $$$mx_u$$$ and $$$mi_u$$$ respectively be the maximum toll and minimum capacity from $$$u$$$ to centroid, and $$$bel_u$$$ be the subtree within which $$$u$$$ lies. Then, we just have to find out the following:

  • $$$bel_v\ne bel_u$$$.
  • $$$\min(mi_u,mi_v)\ge V$$$. ($$$V$$$ is the number of vehicles in the query)
  • $$$a_v=ans1$$$. ($$$ans1$$$ is the answer to the first question)
  • among those $$$v$$$, the maximum value of $$$\max(mx_u,mx_v)$$$.

By maintaining a segtree independently for each $$$a_v$$$, the whole task can be solved in $$$O((n+q) \log^2 (n+q))$$$. (without any observation)

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for Editorial

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is this giving TLE on 2nd test case whereas it runs just fine on other IDE

my solution

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

    violating the condition that 1<=aj<=n i also did same mistake though

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

      arre thanks a lot bhai..i have been struggling in this for a long time

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

        however it should give wrong output format rather then TLE if so i would have done d too

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B? if m may not be less than n

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

    that,s mean the problem may not have solution if every node appeared at least one in B

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

      If it's given that Solution always exists for given testcases

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the Java implementation.

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

I really like the way D was made. It was easy but little trick at the same time. Thanks for this

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help as to why am I getting a wrong answer on test 3 though I did same thing as the editorial?? Any help will be greatly appreciated. 132350668

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem C, I can not understand the meaning of "This includes the cell itself, so all filled in cells are not exitable".

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

    I got WA cause' I misinterpreted this line, for a single column subgrid XXXX the output was supposed to be Yes but I was printing No.

    • »
      »
      »
      11 months ago, # ^ |
      Rev. 2   Vote: I like it -9 Vote: I do not like it

      I hope the authors would make the problem statement more easier to understand next time. For subgrid 2x2: [.X] [XX] I printed out YES, but the answer is NO

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

        How it is No? HuyHoang

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

          Because [.X][X.] also gives the same output. The bottom last cell is not exitable so they put an 'X' there. They say, "all filled in cells are not exitable" which does not imply "all non exitable cells are filled", so you could get a '.' there and still the resulting answer would be the same. There is clever wordplay here. If you still don't understand, watch this explanation by SecondThread for problem C (timestamped video) : here

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The thicken words for B is really useful! :)

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think the proof of F doesn't seem so right....How can the necessity be proved like that?

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Editorial Solution in c++ for 1586C? Anyone?

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

.

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

[solved]

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The editorial of G is very long and I had to be patient enough to read it carefully. However, I didn't understand the sequence "Specifically, we can represent a valid set v as the set u of intervals that aren't implied to be in v by any other element of v" after reading it again, again, again, again, again and again. Though I asked many other people, I still found it hard to realize what it exactly mean... So is there any people who is good at English explain about it? Thanks. Sorry for my poor English:(

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

    It was described earlier that if you have segments $$$[a_i, b_i]$$$ and $$$[a_j, b_j]$$$ such that $$$a_i < a_j$$$ and $$$b_i < b_j$$$ then the presence of $$$[a_j, b_j]$$$ in set $$$v$$$ "implies" the presence of $$$[a_i, b_i]$$$ in set $$$v$$$.

    That's why, if $$$v$$$ has both $$$[a_i, b_i]$$$ and $$$[a_j, b_j]$$$ then you say that $$$u$$$ will contain only $$$[a_j, b_j]$$$. In other words, $$$u$$$ will contain only $$$[a_i, b_i]$$$ from $$$v$$$ that don't have any other $$$[a_j, b_j]$$$ in $$$v$$$ with $$$a_i < a_j$$$ and $$$b_i < b_j$$$.

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

      Oh, what a great explanation! Thanks for your help!

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B if number of restrictions is not necessarily less than n?

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone say why test case 2 is not getting passed https://codeforces.com/contest/1586/submission/133734067

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

thank u so much

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem B is really really amazing.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it
We can also solve the problem D using the binary search. We can first try to find the value of pn i.e. the last element of the permutation. We can query the maximum diff such that p[n] + diff would exist twice in the array. For example lets say p[n] is 5 and n is 7 then diff would come out to be 3 because 5 + 3 will occur twice in the array (5 + 3 and 7 + 1) if we chose our array a to be [1, 1, 1, 1, 1, 1, diff] and 3 is greatest amongst all such diff values. Then pn can be easily computed as n - diff + 1 i.e. 5. It would require aroung log n queries to find the value of diff.

Then we can do the classic n - 1 queries to find the remaining n - 1 elements. 

Total queries: log n + n - 1.
»
10 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Never mind, figured it out!

Regarding this one: 1586C — Omkar and Determination, can someone explain how this is not determinable?

10 10
XX.XX...XX
XXXXX...XX
.X.XX..XXX
XXX.X...XX
..........
..........
XXX....XXX
.XXX..XXXX
XXXXX.X.XX
XXXXX.XXXX
1
9 10


XX  NN
XX  NN
XX  NN
XX  NN
..  EE
..  EE
XX  NN
XX  NN
XX  NN
XX  NN
  • »
    »
    3 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it
    NON DETERMINABLE AS
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

there is a solution for A using DP , it's something like knapsack and then print path that knapsack take it to get optimal solution https://codeforces.com/contest/1586/submission/137350208

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

Another way to think about the tree reduction for E. Thanks to SecondThread for the helpful explanation.

Suppose we have a cycle $$$C = c_1 c_2 \ldots c_m c_1$$$ and we remove an edge $$$e = (c_k,c_{k+1})$$$ from the graph. Now for each path that originally contained $$$e,$$$ say $$$P = v_1 v_2 \ldots v_i (c_k c_{k+1}) v_{i+3} \ldots v_j,$$$ we now remove $$$c_k c_{k+1}$$$ and reroute to the rest of the cycle, ie. the new path is $$$v_1 v_2 \ldots v_i (c_{k} c_{k-1} \ldots c_1 c_m \ldots c_{k+1}) v_{i+3}\ldots v_j.$$$ If we do this for every original path that contained $$$e,$$$ which is an even number of them* (see the note at the bottom), we see that the edge weight of $$$e$$$ goes to $$$0$$$ (even), and we add $$$e$$$'s original weight (an even number) to each of the other edges in $$$C \setminus e.$$$ Since all weights were originally even, the weights after rerouting all paths that originally contained $$$e$$$ are also all even. We can keep removing edges this way until we are left with a spanning tree.

However, the new path may no longer be simple (ie. it will repeat edges if $$$P$$$ contained any edges in $$$C \setminus e.$$$) But it turns out that having non-simple paths is fine at the end when we are left with a tree. Why is this true? Intuitively if we have a non-simple path in a tree, if we go down and visit a child and then come back up, we could just delete this because it cancels and the parity isn't changed, and we can turn it into a simple path.

Formally

Thus we have shown: If there is a valid solution with simple paths on $$$G,$$$ there is a valid solution using (possibly non-simple) paths on any spanning tree $$$T$$$ of $$$G,$$$ and further, any solution on a tree with non-simple paths is equivalent to a solution using the unique simple paths of $$$T,$$$ and the proof is complete.

$$$ $$$
Note
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

F is amazing! Spent a whole day convinced that the answer was $$$\lceil \frac{n}{k} \rceil$$$ and stumbled upon the correct solution after repeatedly failing to prove it.