Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

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

1 | jiangly | 3678 |

2 | Benq | 3602 |

3 | ecnerwala | 3542 |

4 | maroonrk | 3541 |

5 | cnnfls_csy | 3540 |

6 | orzdevinwang | 3493 |

7 | inaFSTream | 3478 |

8 | Um_nik | 3430 |

9 | Geothermal | 3409 |

9 | Rebelz | 3409 |

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

1 | maomao90 | 174 |

2 | adamant | 164 |

3 | TheScrasse | 161 |

3 | SecondThread | 161 |

3 | awoo | 161 |

6 | nor | 159 |

7 | maroonrk | 158 |

8 | Um_nik | 156 |

9 | BledDest | 145 |

9 | Geothermal | 145 |

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial of VK Cup 2018 - Round 1

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/21/2024 15:20:04 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

On Div1C/Div2D:

The same approach can be also implemented using multiset, which is probably faster to write, but has an extra multiplicative factor, which may or may not fit into TL.My solution got AC with maximum execution time of 2917ms. Let's say that I was lucky, or I have to send a dearest thank-you to pragma and synced C++ I/O for making that happened...

Sorry. Deleted.

edit please :D Let's say that I was lucky, or I have to send a dearest thank-you to pragma // AND SYNCED C++ I/O FOR MAKING THAT HAPPENED... you didn't use I/O sync in your code))

Can you explain your solution?

for div1a/div2b

I used to think so, coded it in 36171159 and got TLE :( Perhaps I should learn a normal language

It can be much faster.

Let the largest prime factor of

Xbep(X), andq(X) =X/p(X). GivenX_{1},X_{0}=X_{1}-p(X_{1}) + 1 =X_{1}(1 - 1 /q(X_{1})) + 1. Notice that leaglX_{1}'s are always composite (not prime) andq(X_{1}) is at least 2. If we find aX_{1}such thatq(X_{1}) = 2, all largerX_{1}'s will not produce better answer, and we can stop searching.X_{0}' =X_{1}'(1 - 1 /q(X_{1}')) + 1 ≥X_{1}'(1 - 1 / 2) + 1 >X_{1}(1 - 1 / 2) + 1 =X_{0}, whereX_{1}' >X_{1}andX_{0}' corresponds toX_{1}'.q(X_{1}) = 2 is actually quite common. It just meansX_{1}is double of a prime, and prime is quite common. Since the distance to the next prime afterNis roughly , we only need to searchX_{1}'s. Therefore, the overall complexity is .My solution runs in 15ms: http://codeforces.com/contest/947/submission/36159299

"Clearly, we can obtain N from any number in interval [N - (P(N) + 1), N] by picking P(N) as the prime, and we cannot obtain N from any other number."

I agree with that, but why is P(N) always the best choice for the prime? Why is not possible to pick a smaller prime factor for X2 and then P(X1) for X1?

And you meant [

N-P(N) + 1,N], right?The largest prime factor gives the widest range of possible solutions. For example, if N = 14, the largest prime is 7 so the range is [8, 14] but if you choose the prime 2 the range is only [13, 14].

I also think it is a typo in authors' range formula.

You can prove it that if you will pick some prime divisor smaller than the largest prime divisors the range, which you will get, of numbers from which we can obtain N will lie in the range given by the largest prime divisor.

Ad first question: The interval of the previous value is always [

N-p+ 1,N], wherepis a prime divisor ofN. For any prime, this interval would be contained in the interval [N-P(N) + 1,N], hence it is optimal to consider only the largest prime divisor.Ad second question: Yes, I'll fix it.

The solution for B has an error in it, the range will be [N-(P(N)-1),N] and not +.

here

X(i)>=X(i-1)not just greater than so value should be strictly greater than its previous multiplex2 = k2p2 — (1) x2 >= x1 — (2) (k2-1)p2 < x1 -> k2p2 — p2 < x1 -> x2 — p2 < x1 by (1) — (3) By (2) & (3) Range of x1 is (x2 — p2, x2] -> [x2 — p2 + 1, x2] where p2 is largest prime factor of x2.

Auto comment: topic has been updated by majk (previous revision, new revision, compare).can someone please explain the idea behind this solution : http://codeforces.com/contest/948/submission/36161437

If you have X2 and want to know the range of X1 then you do the following.

Factorize X2 = p1^k1*p2^k2...pn^kn (p1,p2..,pn are primes), then the range of X1 is (X2-pn+1, X2). Because if you choose a bigger range then we can not obtain X2.

For example think about X2 = 14 = 2^1*7^1

The range for X1 will be (14-7+1, 14) = (8,14).

If we choose the range (7,14) then when we peek x1 = 7 and the prime less then x1 (2 or 5) we can not get the X2.

the same process is done for finding X0.

majk Excuse me, about problem E. How can I figure out the eigenvectors v (and Q, Q^-1) using eigenvalues only rather than proof it after knowing it. Is there any material about this? Thanks.

Answer to Bonus of Div1A/Div2B:

We can precompute

P(X) for allXin [1..N] with slightly modified Eratosthenes Sieve in : Each time we run a primepthrough the sieve, mark all multiples ofpwithp. In the end, all numbers are marked withP(X)!Now, for each query

X_{2}, we can find the range ofX_{1}inO(1) by looking at the precomputed table ofP(X). According to my another comment, we only need to searchX_{1}'s. And, for eachX_{1}, we can also findX_{0}inO(1) by lookup.Putting things together, this algorithms works in .

can anyone explain me the solution of problem c

The second solution:

If we make a new pile of snow and subtract all pile of snow, obviously, we will get TLE.

So, we don't do the subtraction.

We can use a variable called

sumwhich means the accumulated temperature until now.If

v[i] < =sum+t[i], then it will disappear and we can calculate the total volume of melted snow. For thosev>sum+t[i], we just addt[i] *numto the answer.And there is another problem, the new pile of snow may

v[i] < =sum+t[i], but actually it doesn't disappear. So, we can addsumto every pile of snow in the begin.Finally we can use multiset to remove element in

log(N).Here is my submission 36189438

UPD: num means the number of pile in the multiset, becausev>sum+t[i], so it won't disappear, the volume of melted snow ist[i] *numThanks for your explanation and submission, they were very clear!

In

Primal Sportproblem shouldn't the answer be 14 for input of 20.Assume

X0= 14If

P1= 4 thenX1= 16 (X1>X0)If

P2= 5 thenX2= 20 (X2>X1)Since we got answer 20 with X0 = 14 shouldn't that be the answer.

Here you are choosing p1 = 4 which is not a prime number

My Bad Sorry and Thanks gaurav569singh

Problem F can be solved by randomized algorithm:

If you just try random permutation and check if it meets the condition, (as you may know), it fails in test case around 96. However, if you modify this algorithm a bit, you’ll get accepted!

Details are as follows:

•Pick up vertex A which has biggest degree

And repeat this until you find the answer:

•Take one leaf B from the other tree (that is, the tree which doesn’t contain A) randomly and map A to B

•Take Vertex C which belongs to the tree with A and doesn’t connect to A randomly, and Vertex D which connect to B (B is a leaf, so D will be uniquely determined), and map C to D

•Just try random permutation for remaining parts and pray for judge :)

Code :36183744

Good job!

What you described is equivalent to the correct way of solving the case where the the highest degree vertex has N-2 neighbours. This was the case that the most "naive" random solutions struggled with — and the antitests were usually of the form G = "almost star", H = "almost path".

Part of the reason why there weren't too many strong pretests against random solutions is that this might help you tweak the meta parameters until you get accepted. In retrospect, I would put the test 96 in the pretest, so that contestants are at least given a chance to realize that we do not expect randomized to pass.

In other words, if the contest was full feedback, we would probably require solution by increasing

Nto 100000. We felt that the task was difficult enough and implementing the required operations on the graph on sublinear time just added implementation time, but was more or less standard.Thank you for replying.

Yes, I know it's very hard to implement this solution and pass system test within contest time.... (partly because we only know the result from pretest)

I'll check O(N log N) solution later, thank you for interesting problem!

Can Div2 C is done by segment tree? if Yes please explain it.

It can solve by segment tree, we only need to maintain the snow that melts every day for a volume equal to the temperature of the day.

Can anyone elaborate on how to add 1 to a segment by two additions using prefix sums in Div2C/Div1B Producing Snow?

You add 1 to the start of the segment, and add -1 to the end of the segment. When processing points, you add the value in the previously created array to a

currvariable, which will always indicate current element.By using a

difference array. You can perform the updates in constant time and access all the updated values at the end in linear time.In the formula I think there must be

`T[j]`

not`T[i]`

. Correct me if I am wrong.Problem 923B producing snow.

Can anybody explain how to do this?

Adding 1 to the range by 2 additions?

Check the previous comments. It has just been asked.

Can anyone explain the correctness of the trie/multiset solution of 923-C Perfect Security ? I just don't seem to understand why the algorithm mentioned in the editorial is correct.

The question wants the minimum sequence. This means we should find the j that minimizes a[0] ^ b[j], remove b[j] from our list and continue. The structure with operations "minimize a[i] ^ x" over all x in a set and add/remove x is the binary trie.

Could anyone find out what is wrong with my program for Div. 2 D? I used a trie like the editorial, but I seem to be off by one for some answers and I have no idea why. Could someone help me out? thanks 36214710

There might be a typo in the editorial for problem f.

The editorial says,

"Assume that one of the graphs is 1-star. Without loss of generality let it be G. Denote v the vertex that can be removed to turn G into star, u its only neighbor, and w be the vertex of degree N - 2. In graph H, find any leaf and denote it w'. Let its only neighbour be

u'. Furthermore, pickv'a vertex that is not adjacent tou'(such vertex always exists as H is not a star). "It seems that

v'andu'should be swapped.In 923D — Picking Strings, transforming BAAB to BBAABB is possible, as per ac solutions, can someone demonstrate how the transformation is done?

`B.A.A.B -> B.BB.A.B -> B.BB.A.AB ->B.BB.A.AAB = BBBB`

`B.B.B.B -> B.B.AB.B -> B.B.AAB.B = BBAABB`

I hope you understand my transitions :)

Yes I get it, and thanks a lot.

What is the tricky case in Test case 11 in Div1D — 923D Picking Strings?

AAA BBAAA 1 1 3 1 5

Answer is 0.

thx.

How to find Minimum number of Dogs in [948A — Protect Sheep]

Could someone please explain how to use dfs and similar in A part(948A) Please!!

Collect all of the cell coordinates/ vertices of the wolves, W.

Create an edge between every cell and it's left, right, down, up neighbors.

For each w in W, run DFS and see if it can reach a sheep. If a dog (or another wolf?) is encountered during the search, end that leg of the search.

I used this idea and ran a BFS from every cell containing a wolf and placed a dog if i ever encountered a ship but my program gives MLE. Can you help me where I'm going wrong?

CodeI found the error in my code and fixed it, but I can't fully understand why it was an error. Initially i was marking the cell to be visited while popping it from queue, but now i mark it as visited before pushing it in the queue. Can someone please explain why this was causing an error?

AC code