By that logic BIPFAMIL is harder than WORDGRID and my argument stands. Moreover, there are 3 people in a team. I think it is reasonable to expect that at least one reads all the problems :)

Why didn't you attempt WORDGRID over BIPFAMIL? From my perspective, once you know WORDGRID is bruteforce, one team mate can start writing code for it while another works out the math for BIPFAMIL. Did any teams try this strategy?

In the worst case the desired graph will have edges. So you might as well check distance between each pair of points and construct said graph in .

click

Doesn't work for me :/

Auto comment: topic has been updated by VastoLorde95 (previous revision, new revision, compare).

Auto comment: topic has been updated by VastoLorde95 (previous revision, new revision, compare).

Auto comment: topic has been updated by VastoLorde95 (previous revision, new revision, compare).

Did anybody manage to pass this using Monte Carlo sampling and DFS?

Are there any new features that are useful for compeititons as well?

See Growth Rate

Number of divisors of n is approximately

Saw your submission — 35045018, got the idea. Thanks :)

So then we can compute the maximum value of min(dp[i—1][k] + X, W + k * B) + cost[i] * k, where k takes c_i different values by splitting the interval into O(logc_i) intervals and taking max from each?

Isn't that slower than the solution using a queue?

What do you mean by nominals?

I think it is NP hard since it can be used to solve the Hamiltonian Path problem. I'll let someone who is more well versed with the theory correct me on this.

Is this because of the new diagnostic mode?

Are the numbers in the parenthesis your judgement of how difficult each problem is?

What was the hack for Div 1 C?

2 hrs

When you combine two strings, you create at most K-1 new substrings of length K

You only need the first K and last K characters from every string where K is the maximum possible answer.

Was anybody able to solve the last problem with divide and conquer dynamic connectivity? Despite lots of optimization, my solution didn't fit into time limit :/

The round is rated for both Div1 and Div2 participants and consists of 7 problems.

Thanks!

+1. For someone who knows the Sprague-Grundy theorem, proving the time complexity is the only hard part in the solution :/

Prove it by contradiction. If some shop is skipped, you can replace it with some other shop and decrease the total cost.

Greedy. The chosen m shops should be contiguous from the list of shops that contain items.

n graphs that contain a single node and no edges... should have been clarified.

Problem E

It can be proven that in the given constraints you can't solve this problem in less than 19 questions.

Really interested to know how to prove such a lower bound! :D

for 1,1 and 2,2 the answer is -1

Move the empty cell to top left corner. Now eliminate columns one at time taking care that there is always an empty cell available in the next column. For example you can do

3 1 1 1
1 1 2 1
1 2 1 1
1 1 3 1

Now eliminate the first column sparing one ball and repeat the process for column 2 and so on. The configuration after this step is complete easy to handle.

Any short approach for GAMEBALL? Also what is the minimum number of moves required to finish a game? Our solution never does more than 500 moves.

How to solve C?

Good luck :)

Is there any possibility to participate remotely?

Have you contacted the contest manager or Bill Poucher regarding this?

I submitted some wonky solution for C which works in . Couldn't prove a tighter bound myself but it runs pretty fast.

Did anybody else do the same? Could you prove a tighter runtime?

The idea is that the more unique drinks you have the lower your total volume required

What was the expected solution?

Guess they didn't want people hacking

I can only imagine your disappointment...

Thanks for the support!

And it makes perfect sense to downvote them because it's their fault that the rules were changed. SMH.

We know we didn't earn the spot but we will try to fill in and represent our country to the best of our abilities.

Sorry it turned out this way, we didn't ask for this to happen. I don't think it will justify whatever has happened but we were just 1 rank behind you in the Kolkata regional. We are going to go all out with our training and we hope we can fill in your shoes.

R.I.P. English

I am unable to login on the site. Using Google+ login gives me an error message saying "invalid credentials"

Is this common knowledge that the ring of polynomials is a UFD? Since the number of accepted solutions was reasonably high, I believe there might be a simpler way to prove the sufficient condition.

What is a unique factorization domain?

Edit: The explanation on wikipedia suggests that this is something similar to the fundamental theorem of arithmetic? Is so then how do you prove the uniqueness of factorizing polynomials modulo p?

Can someone enlighten me why checking if ba^- 1 is a root of P(x) modulo p is a necessary and sufficient condition in D?

Is there some way to create a bitset like this instead of creating a custom bitset object?

int x = something;
bitset<x> b;

Was Problem F checking if subset sum = k for min and greedy for max?

Hint : You can build the grid via an alternating sequence of 90 degree and 180 degree rotations and you need to perform this replication of the grid exactly n times.

Also observe that the final grid size is not that big

Clever :)

Can you elaborate on your tree dp idea? Couldnt come up with anything better than

Yes

I think the answer for C is an n dimensional regular simplex

You can break factorials mod m into chunks of size m - 1, skipping all multiples of m. Now observe how all chunks except the last one teudce to (m - 1)!

Oh sorry wromg problem I meant H and not E

How to solve C? And does pass in E or is there a better solution?

Hint : in the second round divide the array into quarters and swap the 2nd and 4th quarters. Similarly do for eighths in the next round and so on for \ceil{\log(n)} rounds

Greedy. Start from largest pile. Pick pile i if 2p(i) >= X else don't.

Cool :)

Does anybody know when the onsite results will be announced?

12 ipads and  ≥  1500 bucks for the top 200. What. The. Fuck.

Remove some 0s from that figure and I am pretty sure someone will end up paying XD

You only need to check primes upto since the power of all primes greater than in n! will be 1. And you can precalculate how many primes are in the range

Frantically hit F5. It always does the trick for me!

Segment Tree

It is available on the Codejam site itself

Jump for i-th level is to number i * i * (i - 1) * (i - 1)

hint: check if i^a + i^b mod k = 0 for all i ≤ k

http://codeforces.me/blog/entry/46812?#comment-312529

If you know that i^a mod k = r then j^b mod k must be k - r. Instead of iterating over i, iterate over the possible remainders of i^a and you will know what kind of remainder of j^b you are looking for.

i^a mod k = (i + k)^a mod k

Hints for large:

Problem B: We only need to compute i^a and i^b for i ≤ k.

Problem C: Greedy. Remove the segment such that maximum number of points are uncovered. Implement using line sweep to check for moments when exactly one segment is "active".

Problem D: DP. If the size of thr right most chunk is x then it must consist of the largest x elements of the permutation if we want maximum no of chunks. Also such a chunk cannot havr a suffix of size y < x consisting of the largest y elements else the right most chunk can be split into two. Use dp compute number of such right most chunks of size x and use another recurrence to compute the answer for n using information from permutations of size n - x.

I had a solution that didn't need flows and works in .

Get a path from s to t. If none exists, print 0.

This path will consist of at most n-1 edges. Now for each edge in this path, remove it from the graph and construct the bridge tree of the remaining graph. If s and t are in the same block int the bridge tree then removing this edge is of no use to us. Bridge Tree can be constructed in

If s and t are in different blocks find the minimum weight edge on the path from block of s to block of t in the bridgeTree. Now you have two edges, compare their weigths with the current minimum and update accordingly.

Add the removed edge back to the graph and repeat.

Took too much time debuggin but oh well :/ 19347868

363 Div 1 C. You can add it to the list.

Great tutorial! If only I knew about this before today's contest :P

Div 1 E: Heavy Light Decomposition?

Find the minimum on each path and then set that node to Infinity?

From the CF comments section after a failed attempt to solve a problem :P

Two numbers x and y have the same remainder modulo c[i]'s if and only if abs(x-y) = lcm(c[1], c[2], ... c[n])

Now if x mod k and y mod k are not the same, then there will always be ambiguity for Arya. x mod k and y mod k will be the same iff lcm(c[1], c[2], ... c[n]) % k is 0 since the differ by this amount (or a multiple of this amount)

I think you mean't the other way around.

How to solve ARITHM?

Here you go

7 5

6 3

7 3

3 1

1 5

2 4

Participant's output

2 4 1 3 5 6 7

Jury's answer

6 7 3 1 2 4 5

Checker comment

wrong answer Not topsort: 6,3 -> 6,4

DP + Square Root decomposition

In the optimal path, once you have collected the first k keys, you should move to a square to collect the k + 1th key. Thus we can divide the entire matrix into layers where ith layer consists of the co-ordinates of the matrix where such that a[x][y] = i.

Maintain a value for each of these points -> the minimum distance traveled to reach it.

Now we need to do transition from layer i to layer i+1. A brute force implementation for transition could take O((nm)²) time. Thus we take two cases -> If the size of the previous layer is greater than (nm)^0.5 and otherwise. If it is smaller than (nm)^0.5 we can do bruteforce, else we do a BFS with careful book keeping. Overall complexity O((nm)^1.5)

I am offensive and I find this brown.

Nope.

Nope.

See FatalEagle's solution. He did it in a much simpler

I didn't understand how we can perform the two operations in Div 1 B separately. How can you prove this?

639F: what is this compressed forest that is being talked about? Can someone elaborate on what the "left-right" traversal order is and what we achieve by taking LCA?

Edit: Damn, that is a very, very clever technique. Thanks for sharing your sample code!

Because in a valid polynomial Q, the problem states that .

Welcome to India Errichto! :)

Is the official list of finalists out?

Any update about the editorials? The problemset was very interesting, it would be a shame if people don't get to learn something new :)

Unless your friend's solution fails system test.

How to solve COPSUM?

1. A number N can have at most distinct prime factors
2. If the gcd of the array is greater than 1, then there exists at least one prime p, such that all numbers of that list are divisible by p.
3. Since we can't delete the entire array using operation one, then we can deduce that at least 1 of array[1] and array[n] are not delete using operation 1.
4. WLOG, assume that array[1] is not deleted using operation 1. Then some prime factor of array[1] or array[1]+1 or array[1]-1 divides all other elements of the final list.
5. Iterator over each prime factors of each of the following elements — array[1], array[1]+1, array[1]-1, array[n], array[n]+1, array[n]-1 and see what is the best answer we can get.
6. To maintain the answer we can use dp, which says what is the minimum cost to make the gcd of the first i elements > 1 if a) we have already removed some subarray from the list b) if we are in the process of removing some subarray from the list c)if we haven't removed any subarry from the list yet. This can be done in time.
7. According to point one we do step 6 at most times thus giving the said complexity (here M is at most 10⁹)

Thanks!

When and where can I find them?

Will there be editorials for these rounds?