moejy0viiiiiv's blog

By moejy0viiiiiv, history, 6 months ago, In English,

I accepted this problem during the training using a solution.

When I read the model solutions submitted by Mike, I found they are brute force too. And It will failed on a easy case n = 218 - 1, ai = i, bi = i + 1.

Only my solution and Los_Angelos_Laycurse's solution pass this case.

I think we implemented more clever brute force solutions.

But I don't know how to prove my solution is right or construct some hard cases to make my solution TLE.

I really want to know: Is there any provable solution to solve this problem?

Read more »

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

By moejy0viiiiiv, history, 8 months ago, In English,

Hello everyone,

hihoCoder is going to hold a contest at the first day of this year. (2017/01/01 19:00 UTC+8)

hihoCoder is a Chinese website which holds some contests for beginners and also a monthly challenge.

The contest lasts 2 hours and contains 4 problems. The problem set is prepared by me and jiry_2. There will be english translation of the problems. The hardest problem is as hard as div1 C/D in my mind.

Enjoy problems!

Read more »

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

By moejy0viiiiiv, history, 11 months ago, In English,

When I was submitting the problem D in round #371, I clicked the "Choose File" button and selected my code.

Before the submission, I read my code another time, found a bug in my code and fixed it. And then I clicked the "submit" button.

But it turned out that my solution got wrong answer on pretest 4. I stress-tested my solution, and found it passed the big random data. I was really shocked. umm... Maybe my solution failed on some small testcases. So I tried many ways to generate testcases. But my solution was right on all the testcases I generated.

After struggling for about 40mins, I gave up and submitted it again. It passed all the pretests.

I compared two codes, and just found I submitted the old version (before fixing the bug) at first time.

After asking my roommate, he said when you clicked the "Choose File" button, it would upload the file instead of recording the path.

In the rest time of the contest, I tried to solve problem B and E but failed.

I think I should quit from algorithm contest like WJMZBMR and study harder.

Read more »

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

By moejy0viiiiiv, 2 years ago, In English,

Team member: lyy Ruchiose TooSimple zhj

jcvb failed on a relatively easy problem on day 2. But he still has one year to compete.

Read more »

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

By moejy0viiiiiv, 3 years ago, In English,

I'll upload my example solutions and will post links to them as soon as it becomes possible.

All the problems in Div 1 don't have the unique solution. I list several solutions to each problems. There are also some interesting bonus problems. I can't solve some of them yet :( If you have interesting ideas, feel free to share and discuss your ideas in the comments. :)

My English is poor, so if there are some mistakes or something you can't understand, you can also discuss it in the comments.

469A - I Wanna Be the Guy

I Wanna Be the Guy is an interesting game. I strongly recommend it to you.

The problem itself is easy. Just check if all the levels could be passed by Little X or Little Y.

7894174

469B - Chat Online

This problem is not hard. Just iterator over all possible t, and check if the schedule of Little X and Little Z will overlap.

7894252

Bonus:

  1. p, q ≤ 50, l, r ≤ 109
  2. p, q, l, r ≤ 105

468A - 24 Game

Solution 1:

If n ≤ 3, it's easy to find that it's impossible to make 24, because the maximal number they can form is 9.

If n > 5, we can simply add n - (n - 1) = 1, 24 * 1 = 24 at the end of the solution to the number n - 2.

So we can find the solution of 4, 5 by hand. 1 * 2 * 3 * 4 = 24, (5 - 3) * 4 * (2 + 1) = 24

7894267

Solution 2:

We can find the pattern like that n + (n + 3) - (n + 1) - (n + 2) = 0, and find the solution of 4, 5, 6, 7 by hand or brute forces.

Solution 3:

A knapsack-like solution.

7894283

468B - Two Sets

Solution 1:

If we have number x and a - x, they should be in the same set. If , it's obvious that . The contraposition of it is , that means if , a - x should in the set B. Same as the number x, b - x.

So we can use Disjoint Set Union to merge the number that should be in the same set.

If a - x doesn't exist, x can not be in the set A. If b - x doesn't exist, b can not be in the set B.

Then check if there are any conflicts among numbers which should be in the same set.

There are many other solutions to solve this problem based on the fact that x, a - x, b - x should be in the same set, like greedy, BFS and 2-SAT.

7894313

Solution 2:

If a = b, it's easy to find the solution.

We regards every number as a node. Every number x links to number a - x and number b - x.

The degree of every node is at most 2. So this graph consists of a lot of chains and cycles, and some node may have self loop.

We only need to check if the lengths of all the chains are even or the chain ends with a self loop.

7894323

Bonus:

Prove there is no cycle in the graph described in the solution 2.

Divided all the numbers from [0, n - 1] into two sets that have parameters a, b. Can you solved it in O(1)?

468C - Hack it!

Define . , so we should find a pair of number a, b that

Solution 1:

First we choose x randomly. Then we can use binary search to find the minimal d that .

So is very small, between 0 and . If , after choosing x atmost 9 * len + 2 times, we can definitely find a pair that

7894341

Solution 2:

We can use binary search to find the minimal d that g(d) ≥ a, g(d) ≥ 2a, ...

This solution is similar to the first one.

7894452

Solution 3:

We can use binary search to find the minimal d that g(d) ≥ a. And we use two pointers to maintain an interval [l, r] that until we find .

I can't prove the correctness of this algorithm, but it performs well in practice.

7894356

Solution 4:

Thanks ZhouYuChen for his talented idea.

If x < 1018, we can get f(1018 + x) = f(x) + 1. That means if we shift the interval [x + 1, x + 1018] by 1, the result will be increase by 1 too. And it also not hard to find that g(10x) = 45 * x * 10x - 1. So if , [a - x, a - x + 1018 - 1] is the answer.

It's easy to see that upper bound of the answer is a, because of pigeonhole principle (among g(0), g(1), ..., g(a) at least two are equal). So big integer is not required in this problem.

If solution 3 is correct, the upper bound of the answer can be 2 * 1016.

7878473

Bonus:

Prove or disprove that solution 3 is correct.

468D - Tree

I am sorry that this problem coincides with that one.

d(u, v) = depu + depv - 2 * depLCA(u, v), so the answer is:

depi there means the distance between node i and root.

We choose centroid of tree as root (let's denote it u), so we can make every pair (i, pi) are in different subtrees, that means depLCA(i, pi) = 0.

So the answer is .

The next part of this problem is find the lexicographically smallest solution.

We regards it as finding the lexicographically smallest matching in a bipartite graph.

For a subtree, if the amount of nodes in this subtree in the left part > the amount of nodes not in this subtree in the right part, the perfect matching doesn't exist. So the amount of nodes in this subtree in the left part + the amount of nodes in this subtree in the right part should be no more than the amount of nodes unmatched, while the root is an exception.

We can use a segment tree to maintain it easily. We determined the minimum possible pi from 1 to n. If there is a subtree that the amount of nodes in this subtree in the left and right part is equal to the amount of nodes unmatched, we must select a node from it, so pi equal to the node in this subtree with the minimum id. Otherwise, we can choose a node with the minimum id that is not in the same subtree with i.

7894417

468E - Permanent

The permanent can be obtained as follows: for each (e1, e2, ..., et) such that x1, xe2..., xet are distinct and ye1, ye2, ..., yet are distinct, add to the answer.

It can be proved by the formula :

,

where s and t are subsets of the same size of {1, 2, ..., n} and , are their respective complements in that set.

Construct a undirected graph G with 2n vertices v1, v2, ..., v2n, where the edge weight between vertex vi, vn + j is Ai, j - 1. We only need to know the sum of weight of all matchings that we choose t edges. The weight of matching is the product of all edge weights in the matching.

We only need to know the sum of the weights that we choose x edges in the each connected components.

The number of nodes in a connected component is s and the number of edges in this connected component is t.

Algorithm 1:

Because it's a bipartite graph, so the number of vertices in one part is at most s / 2. So we can use state compressed dp to calculate the ways to choose x edges in this connected component. The complexity is O(2s / 2 * s2).

Algorithm 2:

We can choose a spanning tree. The number of edges in spanning tree of these vertices is s - 1, and the number of non-tree edges is t - s + 1. So we can enumerate all the non-tree edge, use tree dp to calculate the ways. The complexity is O(2t - s * s2).

Combined with these two algorithm, the complexity is O(min(2s / 2, 2k - s) * s2)) = O(2k / 3 * k2).

Read more »

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

By moejy0viiiiiv, 3 years ago, In English,

Hello everyone! Codeforces Round #268 is coming soon! We invite you to participate in this round. It will be held on September 20th at 17:00 MSK.

Problems have been prepared by me. Thanks xyz111 and dhh1995 for giving me the idea of some problems. Thanks vfleaking, foreseeable, xiaodao, ruchiose and xllend3 for testing.

I also want to thank Gerald for helping to prepare this round, Delinur for translating the statements, and also MikeMirzayanov for Codeforces and Polygon.

It is my first round on Codeforces. Hope you will enjoy this round.

You'll help a boy named Little X in this round. Good luck and have fun :)

UPD

Round has finished. Thanks for participating.

Congratulations to the winners.

Div. 1

  1. PavelKunyavskiy
  2. Kostroma
  3. HellKitsune
  4. Baz93
  5. DemiGuo

Div. 2

  1. manman
  2. topcodecheforces
  3. mhy12345
  4. sk_aswd
  5. z.last

Congratulations to ecnerwal, the only participant to solve the problem D!

Unfortunately, no one has solved the problem E in both divisions.

Editorial for the round will be added tomorrow.

UPD

Editorial is here.

Read more »

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