Could not find related blog. Let's discuss. What's the solution of B?

As an experiment the Educational Codeforces Round 33 will be rated for Div. 2.
×

# | User | Rating |
---|---|---|

1 | tourist | 3496 |

2 | moejy0viiiiiv | 3288 |

3 | W4yneb0t | 3218 |

4 | TakanashiRikka | 3178 |

5 | Petr | 3173 |

6 | dotorya | 3117 |

7 | izrak | 3109 |

7 | Um_nik | 3109 |

9 | anta | 3106 |

10 | ershov.stanislav | 3105 |

# | User | Contrib. |
---|---|---|

1 | rng_58 | 174 |

2 | csacademy | 170 |

3 | Swistakk | 160 |

4 | tourist | 157 |

4 | Petr | 157 |

6 | Errichto | 154 |

7 | Zlobober | 147 |

8 | matthew99 | 142 |

9 | Endagorion | 141 |

10 | BledDest | 137 |

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Nov/23/2017 19:23:30 (c4).

Desktop version, switch to mobile version.

User lists

Name |
---|

Auto comment: topic has been updated by dragoon (previous revision, new revision, compare).Apparently it's 1 if graph is bipartite, otherwise 0. But we have no clue why.

Let's choose a subset of edges, and then color each vertex black and white. If

uandvare connected by a chosen edge, they must be colored with the same color. Also, vertex 1 must be colored white. How many ways are there to do this?Suppose that we fix the set of edges. Then, the number of valid colorings is 2

^{components - 1}and this is odd only when the entire graph is connected. Thus this is what we want to compute.Now let's fix the coloring first. In this case, the number of valid subset of edges is odd only when the coloring is a valid bipartite coloring for the entire graph.

Could you explain the second item in detail?

Also the notion of the characteristic polynomial of a graph helps a lot. We can say that if we fix some edge, each good subset either doesn't contain this edge (their number is the answer for the same graph but without this edge) or contains it (their number is the answer for the same graph but the endpoints of this edge are considered the same). The characteristic polynomial is built just like that, but there we subtract instead of adding, which is the same modulo 2. Finally, we know that the number of ways to paint vertices of a tree in 2 colors is 2, so we can just look at the number of ways to paint vertices of the initial graph in 2 colors modulo 4: it's either equal to 2 (then the answer equals 1, and this happens iff the graph is bipartite), or equal to 0 (otherwise).

"what is the intuition behind this fact? How to come up with it without knowing it in advance? I would be grateful if the readers could shed some light here." — ok, so here's how we

derivedthe answer, not just proved the guess (more specifically Marcin_Smu did it). Strategy was very similar to the solution of problem C2 from that Petrozavodsk. If one knew solution to that problem this one was much easier.Consider bad subsets of edges. For bad subset of edges we can divide vertices into two groups (

A,B) so that there are no edges between them. We will count such triples (bad subset of edges, A, B), where (A, B) is partition of V and first vertex belongs to A (otherwise everything would be even trivially). But hey, if graph with our subset of edges has more than two connected components there is more than oen way to divide connected components into A and B! But if there arekof them then there are 2^{k - 1}- 1 ways to do so, which is always odd! So our answer is equal to number of such triples! But if we fix A and B first then there are 2^{e}bad subsets of edges corresponding to them, whereeis number of edges withinAand withinBin total. But this is almost always even. Only case when it is odd is when A and B are independent sets, or in other words if our graph is bipartite :). Since our graph is connected there is only one way to partition its vertices into two independent sets, so we are done.Maybe a bit more complicated than Makoto's proof, but that's how you can come up with it not knowing answer in advance.

Thanks — it makes more sense to me now. The 2**(k-1)-1 part, where the magic happens, does arise from a reasonable consideration!

C. https://apps.topcoder.com/wiki/display/tc/SRM+527 This editorial (P8XCoinChange) gives a big hint.

D. After some calculation on paper it turns out that we need to compute the following: , , . I believe this is solvable if we pre-compute these values when

iis divisible by 100000 and paste it into the code.C: Duh, that SRM's editorial is so long :P. What I did is very similar to what is described here: http://petr-mitrichev.blogspot.com/2015/10/a-week-with-sheafs.html (probably similar to what is written on TC, however much shorter), however my solution has complexity and at first it took my code 100s to complete maxtest, whereas TL was 2s. Using some weird optimizations I fortunately made it to pass :p. However I have heard that there is a solution in complexity , but I couldn't understand it at problem analysis.

D: I am not sure it can pass by using preprocessing. We had that idea, but there are some problems with this approach. Note that there are 100000 testcases. Moreover we need to compute those phis (that comes with log log n factor to complexity). We can do something a bit more clever and preprocess points of form

k^{3}instead ofk·100000, but it is still shaky. Maybe it will pass, maybe not, but this task still has a solution not using "preprocessing cheating". Computing those sums boils down to computing prefix sums of μ(i)·i^{k}for k=0,1,2 for some specifics points. I didn't figure it out to the end, but I think main ideas are contained here: https://www.mimuw.edu.pl/~pan/papers/farey-algorithmica.pdf or in editorial to Four Divisors problem: http://codeforces.com/blog/entry/44466It is very surprising that the number of primes up to

Ncan be computed faster thanO(N). My thinking was like: the sum ofphi(i) is closely related to the distribution of primes, most probably it can't be done faster thanO(N), so it must be some pre-computation.Compute sum{phi(i)} is different from number of primes up to N since they are Multiplicative function.

These sub-problems are well known in China and they can be solved by "sieve of xudyh". I couldn't find articles in English, but I know this one in Chinese is good: http://blog.csdn.net/skywalkert/article/details/50500009

The method the problem setter used in C is from here -- Summation by parts.

For two given sequences (

a_{n}), and (b_{n}),, with , one wants to study the sum of the following series:If we define then for every

n> 0,b_{n}=B_{n}-B_{n - 1}, andThe method can be applied in the following way:

For the

m-th power partition,For the

k-th convolution power of them-th power partition, thek-th order forward difference is: .Taking

k= 1 as example, leta_{n}=b_{m}(n),b_{i}= 1, we haveAs $a_{n} - a_{n-1} = 0$ if , otherwise , we can reduce

nto . And apply this method again and again, we can reducento a trival casen= 0.For large

k, we need to apply this methodktimes to reducento .D can be solved in

O(n^{2 / 3}) as described hereThanks for link to clear explanation. However, for the sake of completeness, complexity analysis is a bit off, because it doesn't take into account factor coming from Erathostenes' sieve. It is (if done carefully), as in both places I mentioned as well.

In fact,phi(1)..phi(n) can be calculated in O(n) using sieve(I don't know its English name),whose main idea is to calculate phi(i) using its minimum prime divisor.After this preprocessing we can make "xudyh sieve" O(n**2/3)

Any easy solution to F?

Divide rectangles on left and right and sort them by

`b`

. Then calculate`dp[i][j]`

as maximum weight when upper left rectangle is`left[i]`

and upper right —`right[j]`

.It can be computed in next way:

If

`left[i].a > right[j].a`

then`dp[i][j] = left[i].weight + max_over_k(dp[k][j])`

, where`left[k].b < left[i].a`

. Otherwise same logic but with`right[j]`

.Use two additional maximum_on_prefix_dp and it will be

O(N^{2}).How to prove greedyness in G?

How did you solve it?

One can prove two observations:

Observation 1. If one panda is already assigned — the problem can be solved greedily.

Observation 2. Given optimal assignment of pandas one can transform it to another optimal one such that there will be a panda which maximally gives its donuts either to left or right one.

Now we need to find such a panda (intuitively it will be the one with minimal allowed deviation).

The criteria we used was the following: minimal difference between optimal left and right packing (one panda) and minimal b[i] + b[i+1] — a[i]. Stress-test did not find any testcase it fails at.

Where I can read the problems?

How to solve div.2

M? Can't understand task.Anyone A, H, I?

I: Theorem: Let

T=A·Bwith , and letYbe a subtree ofroot(B) with maximum numbern_{Y}of vertices. Then the subtrees ofroot(B) are exactly the subtrees ofroot(T) with at mostn_{Y}vertices. Proof: Reduction to Absurdity.Using above theorem you can easily to prove that the factorization is unique.

Compute the hash value of all the subtree, and sort all the subtree according to their size. By enumerating the value of

n_{Y}, we can find the subtrees ofB. Using the hash value to check if this tree is a factor ofT. This leads to anO(n·d(n)) solution, whered(n) is the number of divisors ofn. By combining with some string matching technique, we can get anO(n) solution.For problem A.

Apparently, if

sis less than or equal to 1010, there is no solutions. Otherwise, we can always find a solution.If

shasd(d> 4) digits, then$\underline{999\ldots 999}898$((d- 4)'s 9 followed by 898, (d- 1) digits in total) is almost bobo. We can use this fact to solve the case where there is no almost bobo number having the same length withs. Now, we can assume there always exists an almost bobo number having the same length ofs.Apparently, the answer has a longest common prefix with

s, let's denote it asp. In order to findp, we need to enumerate all the prefix, and check if this prefix can be a solution.Assume the prefix is

s^{′}, we need to append another digitctos^{′}, in such a manner thatc<s(|s^{′}| + 1). Let's call the new string bet(assume the consecutive equal digits are merged). To append some other digits to maketalmost bobo, we need find a borderuoft(t=uxu, for some nonempty stringx), such that |t| - 2|u| ≤ |s| - |s^{′}| - 1 (there are some other small cases, just ignore it for now). So, we should find auwith maximum length, we can call it half border.As showed in this paper, Efficient data structures for the factor periodicity problem, all the border longer than half forms an arithmetic progression, we can determine the half-border with KMP in O(1).

After finding the longest prefix, we can just append more digits from 9 to 0 to find a largest answer (the rule used above can be used to check if the digit is a part of the answer).

I found dmd-compiler(it is compiler of d-lang), and I use It, but my program are too slow and got TL ... ;( (I can get accept by rewrite it in c++)

Does anyone know the compiler options of judge? I can't find it.

Can anyone publish the problemset?

Yes. http://opencup.ru/files/och/gp11/problems1-e.pdf