diverta 2019 Programming Contest 2 Announcement

5 years ago, # ^ |

Obviously, (p, q) should be the difference between two balls' coordinates, since otherwise we'll never be able to acquire a ball at zero cost (and our answer would be N). Iterate over every pair of balls and let (p, q) be the difference between their coordinates. Then, for each such (p, q), iterate over every ball and determine whether we can collect it at zero cost. (We can do so if and only if there exists a ball at (x-p, y-q): since there can be only one ball at each point, we know that we can collect (x, y) right after (x-p, y-q).) That lets us determine the minimum cost of collecting the balls given this pair (p, q), and our answer is the minimum of all of these values.

→ Reply

5 years ago, # ^ |

-8

For the third sample test case in problem B why is the answer 2. What are the values of p and q taken ?

→ Reply

5 years ago, # ^ |

Take p=1, q=0, then collect the four points in the order #1, #3, #2, #4. #3 and #4 will then be free, so the answer is two.

There are several more cases that work (p=0, q=1, and the order #1, #2, #3, #4, for example), but this gives a correct answer.

→ Reply

5 years ago, # ^ |

-16

but given that u r not allowed to take value 0 of any p & q !!

→ Reply

5 years ago, # ^ |

We must have p != 0 or q != 0, so one of the two can be zero as long as they aren’t both zero.

→ Reply

5 years ago, # ^ |

-16

"We will collect all of these balls, by choosing two integers p and q such that p ≠ 0 or q ≠ 0 and then repeating the following operation:"

→ Reply

bugdone

5 years ago, # ^ |

I used union-find to connect balls with the same (p, q). 1. I first sort the balls first by x, then by y. 2. For all pairs of balls (i, j) where i < j, I compute (p, q) and check the cost. This gets WA on more than half the tests. Why?

I know that it doesn't help the complexity to use only i < j pairs. But I thought that sorting would be enough to make it work.

→ Reply

5 years ago, # |

+10

What was the solution to F?

→ Reply

burt_macklin_

5 years ago, # |

Hint for C?

→ Reply

5 years ago, # ^ |

Here's a small hint that helped motivate my solution.

Suppose we have three terms x, y, and z. After subtracting z from y, we get y-z, and after subtracting that from x, we get x-y+z. As you can see, the z is being added now, since it was subtracted twice. In general, subtracting a number an even number of times is equivalent to adding that number. Can we take advantage of this somehow?

→ Reply

iLoveIOI

5 years ago, # |

When will editorial come out?

→ Reply

rng_58

5 years ago, # ^ |

Uploaded just now.

→ Reply

SameerGulati

5 years ago, # |

+10

Solution for E?

→ Reply

5 years ago, # ^ |

+11

Here's my solution, although the explanation may be a bit hard to follow.

Let dp[i] be the ways to get at least one block to height i and then to order however many blocks end up on height i at some point. (We need to order them because we have to figure out the order in which we'll add blocks to these squares.) Then, dp[0] = N! since there are N! ways to arrange the blocks at point 0.

Afterwards, dp[i] is the sum of the dp values from dp[i-1] to dp[i-D], since we can start anywhere from 1 to D blocks below, times the sum from 1! to N! (as we can bring any number from 1 to N of blocks up to height i and then we have x! ways to order their next steps).

Then, our answer is dp[H] except at this step, we don't multiply by the factorials (as we won't be doing any future steps, so we don't need to order the blocks arriving at H).

→ Reply

SameerGulati

5 years ago, # ^ |

Thank you :) your explanation is somehow better than the editorial for me.

→ Reply

SorahISA

5 years ago, # |

← Rev. 2 →

After thinking C for over an hour, I find D a simple brute force.
QwQ

How to solve C?

→ Reply

vyomkesh

5 years ago, # ^ |

Brute force? How? (I used DP 2 times)

→ Reply

SorahISA

5 years ago, # ^ |

https://atcoder.jp/contests/diverta2019-2/submissions/5937161
see if gA, sA, bA is greater than gB, sB, bB
solved in O( (N/min(gA,sA,bA))^2 )

→ Reply

Your text to link here...

5 years ago, # ^ |

Take the largest number in the set, and call it A. Take the smallest number in the set and call it B.

Subtract each of the remaining positive numbers in the set from B. Then, subtract each of the remaining negative numbers in the set, plus the new value of B, from A.

This is ideal because we're subtracting B and all remaining negative numbers from A once while subtracting all remaining positive numbers twice, which is equivalent to adding them. So, we're adding as many positive numbers and subtracting as many negative numbers as possible.

→ Reply

smallguoguo

5 years ago, # ^ |

→ Reply

metamorphosis00

5 years ago, # |

+35

Problem C(without answer reconstruction): https://codeforces.net/contest/1038/problem/D

→ Reply

onceincentury

5 years ago, # ^ |

I think problem in codeforces is little diffrent.I can't handle the situation of adjacent.Can somebody help me in this problem.

→ Reply

tomsyd

5 years ago, # |

I don't understand why my code passed the test cases for question B. More precisely, why does adding the following 4 lines make my code correct ?

pot.emplace(a,b);
pot.emplace(-a,b);
pot.emplace(a,-b);
pot.emplace(-a,-b);

My code

( Maybe it's because test cases are weak. )

Thanks

→ Reply

iLoveIOI

5 years ago, # |

I thought you could choose lines with different slopes for B, time to relearn reading.

→ Reply

Submission during contest, Accepted submission after contest

5 years ago, # |

Oh wow, F is pretty similar to a problem that appeared in a Finnish contest recently, and I even realized that, but multiplied by $$$2^{\left\lceil log2(M)\right\rceil}$$$ instead of M at every step. Too bad, with that this would have been my best-ever performance :/

→ Reply

metamorphosis00

5 years ago, # |

I dont understand statement problem D :( . But tasks were interesting thanks to the authors.

→ Reply

square1001

5 years ago, # |

+24

E869120 and square1001 wrote problem F. How was it?

My solution is in the editorial and the max length of Hamiltonian Path will be $$$96 \ 755 \ 758 \ 040$$$. If we start induction from $$$N=3$$$ with setting edge length $$$1, 2, 3$$$, we can get more 'accurate' answer which max length is $$$83 \ 907 \ 014 \ 282$$$.

However, when I saw the submissions, most people solved in different ways to writers' one. Also, I am curious how short the optimal answer is, because writers/admins could not find the solutions which score is less than $$$6\times 10^{10}$$$ :)

→ Reply

atlasworld

5 years ago, # ^ |

why u wrote so short editorial for F, while in japanese its too long. why partiality?

→ Reply

E869120

5 years ago, # ^ |

← Rev. 3 →

That's because square1001 wrote a detailed editorial of problem F, and evima, who usually translates the problem statement in AtCoder, wrote English editorial of F.

→ Reply

atlasworld

5 years ago, # ^ |

← Rev. 2 →

-43

since evima is not so active on cf, tell him to write proper editorials from the next time. Cutting his job short is not good.

→ Reply

square1001

5 years ago, # ^ |

+28

But some people even in Japan are saying that English editorial is more simple and it means better. So I think that this is just an opinion difference to evima and square1001.

I personally think that it is good to write every steps of approach which the writer and/or editorialist used to solve the problem. That's why I wrote 5 + extra 1 step of ideas to complete the Japanese editorial.

But some people think differently — they think that editorial is the best if they could tell "how to get AC" in the most simple way.

→ Reply

5 years ago, # ^ |

← Rev. 2 →

+29

Apparently my solution produces a better one, with maximum path cost $$$49721430711 \approx 5 \cdot 10^{10}$$$:

distances

0 1 7 10 13 21 26 41 43 45 
1 0 88 176 352 704 1320 2112 2552 2992 
7 88 0 5544 11088 22176 44352 77616 105336 133056 
10 176 5544 0 238392 476784 953568 1907136 3099096 4291056 
13 352 11088 238392 0 7390152 14780304 29560608 51731064 88681824 
21 704 22176 476784 7390152 0 140412888 280825776 561651552 982890216 
26 1320 44352 953568 14780304 140412888 0 1544541768 3089083536 6178167072 
41 2112 77616 1907136 29560608 280825776 1544541768 0 9267250608 18534501216 
43 2552 105336 3099096 51731064 561651552 3089083536 9267250608 0 27801751824 
45 2992 133056 4291056 88681824 982890216 6178167072 18534501216 27801751824 0

Edit: And the improved solution from my post below, with maximum path cost $$$45201300642 \approx 4.5 \cdot 10^{10}$$$

distances

0 1 2 4 8 15 24 29 34 46 
1 0 80 160 320 640 1200 1920 2320 2720 
2 80 0 5040 10080 20160 40320 70560 95760 120960 
4 160 5040 0 216720 433440 866880 1733760 2817360 3900960 
8 320 10080 216720 0 6718320 13436640 26873280 47028240 80619840 
15 640 20160 433440 6718320 0 127648080 255296160 510592320 893536560 
24 1200 40320 866880 13436640 127648080 0 1404128880 2808257760 5616515520 
29 1920 70560 1733760 26873280 255296160 1404128880 0 8424773280 16849546560 
34 2320 95760 2817360 47028240 510592320 2808257760 8424773280 0 25274319840 
46 2720 120960 3900960 80619840 893536560 5616515520 16849546560 25274319840 0

→ Reply

E869120

5 years ago, # ^ |

← Rev. 3 →

Great solution.
How did you find this answer?

→ Reply

5 years ago, # ^ |

It seems there are two differences to the solution in the editorial:

Firstly, I have the "optimal" (minimum maximum value) list of values for every size:

values

1
1,2
1,2,4
1,2,4,7
1,2,4,7,12
1,2,4,8,13,18
1,2,4,8,14,19,24
1,2,4,8,15,24,29,34
1,7,10,13,21,26,41,43,45

Finding them took a few seconds with a simple brute force:

brute code

#include <iostream>
#include <bitset>
#include <vector>
using namespace std;

const int N = 200;
bitset<N> sums;
bitset<N> cur;
bitset<N> res;

void solve(int i, int h) {
	if (i == h) {
		if (cur.count() > res.count()) res = cur;
	} else {
		if (! sums[i]) {
			sums[i] = 1;
			if ((sums & (cur << i)).count() == 0) {
				sums ^= (cur << i);
				cur[i] = 1;
				solve(i+1, h);
				cur[i] = 0;
				sums ^= (cur << i);
			}
			sums[i] = 0;
		}
		solve(i+1, h);
	}
}

int main() {
	int pc = 0;
	for (int h = 1; pc < 9; ++h) {
		solve(1, h);
		if (res.count() > pc) {
			pc = res.count();
			for (int j = 1; j <= h; ++j) {
				if (res[j] == 1) cout << j << ' ';
			}
			cout << '\n';
		}
	}
}

Secondly, instead of building inductively by adding edges to all previous nodes multiplied by M, I add edges from the first node to the other ones, then from the second to later ones, and so on, each time multiplied by the product of the sum of the two longest edges for every previous node. This works by the same argument, but we end up multiplying smaller values.

Here's the submission: code

→ Reply

Um_nik

5 years ago, # ^ |

+10

Why do you think that we multiplying smaller values? Your value covers all subsets of edges with no more than 2 edges from each group, while authors solution covers only interesting subsets.

I think that it is actually worse, because I was doing the same thing, but with bad values (like in editorial), and it wasn't enough ($$$1.36 \cdot 10^{11}$$$). I had to use different values for one group, so that only sums of two are different (and all numbers different). We can do this because after decoding all other groups we know the exact number of edges we need. And that helps only if the size of group is 5, 6 or 7 (not more).

Also I don't understand why you multiply by sum of two maximums, not sum of two maximums + 1 (and the same question for solution from editorial). You know, when we use 10-based system, we multiply by the largest digit + 1, not by the largest digit.

→ Reply

5 years ago, # ^ |

I actually didn't even realise I wasn't adding 1. It isn't a issue here though, since if the total length is exactly some multiple of b, we know the contribution from the earlier nodes is exactly b, since it is at least 1 and not more than b, and the contribution from later nodes is divisible by b.

Note that by doing it in this order you cannot find the maximum cost of hamiltonian path, since at each step you add edges to nodes that you have not handled yet. So I think the approximation is necessary.

It turns out the intuition about "multiplying smaller values" doesn't really work. But by constructing the graph like this, the maximum path is pretty easy to find: It always goes $$$1 \rightarrow 3 \rightarrow 5 \rightarrow 7 \rightarrow 9 \rightarrow 10 \rightarrow 8 \rightarrow 6 \rightarrow 4 \rightarrow 2$$$, since the lengths of the edges from every node are sorted by how large of an index the edge goes to, and it is optimal to take as many edges and as heavy edges from every node as possible, we get this greedy solution. So we end up taking one edge from every group of edges we add, and the multiplier will always be the second smallest value in the list of weights for that group. Additionally, b will be determined by the product of the sum of the two largest values in the suffix of lists.

I ran the brute force again, firstly minimising the sum of the two last numbers in every list, and secondarily minimising the second smallest number. This gave the following values:

values

1 
1 2 
1 2 4 
1 2 4 7 
1 2 4 7 12 
1 2 4 8 13 18 
1 2 4 8 14 19 24 
1 2 4 8 15 24 29 34 
1 2 4 8 15 24 29 34 46

And the graph with maximum path cost $$$45201300642 \approx 4.5 \cdot 10^{10}$$$:

distances

0 1 2 4 8 15 24 29 34 46 
1 0 80 160 320 640 1200 1920 2320 2720 
2 80 0 5040 10080 20160 40320 70560 95760 120960 
4 160 5040 0 216720 433440 866880 1733760 2817360 3900960 
8 320 10080 216720 0 6718320 13436640 26873280 47028240 80619840 
15 640 20160 433440 6718320 0 127648080 255296160 510592320 893536560 
24 1200 40320 866880 13436640 127648080 0 1404128880 2808257760 5616515520 
29 1920 70560 1733760 26873280 255296160 1404128880 0 8424773280 16849546560 
34 2320 95760 2817360 47028240 510592320 2808257760 8424773280 0 25274319840 
46 2720 120960 3900960 80619840 893536560 5616515520 16849546560 25274319840 0

Here's the submission

The original values but using the maximum as in the editorial gives $$$75915624051 \approx 7.5 \cdot 10^{10}$$$ for the longest hamiltonian path: submission. The modified values (even though they weren't optimized for this use) give $$$69050411635 \approx 6.9 \cdot 10^{10}$$$: submission

→ Reply

Xellos

5 years ago, # ^ |

I used a similar idea, but with a worse sequence: $$$1, 2, a_i = a_{i-1} + a_{i-2} + 1$$$. My thought process: Well shit, the last two edges are too big. If it's just 1 edge, I can find the lengths of all paths that don't contain it, all paths that contain it and just bruteforce the minimum length of that edge such that no two paths' lengths coincide (using 2 pointers to check if a fixed length is ok). But it's 2 edges, so I'll just guess one of them and do that for the other. Distances:

0 878 37673475840 5381925120 448493760 22424688 679536 12584 143 1
878 0 6 10763850240 896987520 44849376 1359072 25168 286 2
37673475840 6 0 21527700480 1793975040 89698752 2718144 50336 572 4
5381925120 10763850240 21527700480 0 3139456320 156972816 4756752 88088 1001 7
448493760 896987520 1793975040 3139456320 0 269096256 8154432 151008 1716 12
22424688 44849376 89698752 156972816 269096256 0 13590720 251680 2860 20
679536 1359072 2718144 4756752 8154432 13590720 0 415272 4719 33
12584 25168 50336 88088 151008 251680 415272 0 7722 54
143 286 572 1001 1716 2860 4719 7722 0 88
1 2 4 7 12 20 33 54 88 0

(6 is the guessed length here, there are other options). The max. length is pretty short, too.

→ Reply

Xellos

5 years ago, # ^ |

+10

Here you go! A solution with max. cost approximately $$$9 \cdot 10^9$$$.

0 214 95963 4008331713 448493760 22424688 679536 12584 143 1
214 0 3 2004429048 896987520 44849376 1359072 25168 286 2
95963 3 0 1002019965 1793975040 89698752 2718144 50336 572 4
4008331713 2004429048 1002019965 0 3139456320 156972816 4756752 88088 1001 7
448493760 896987520 1793975040 3139456320 0 269096256 8154432 151008 1716 12
22424688 44849376 89698752 156972816 269096256 0 13590720 251680 2860 20
679536 1359072 2718144 4756752 8154432 13590720 0 415272 4719 33
12584 25168 50336 88088 151008 251680 415272 0 7722 54
143 286 572 1001 1716 2860 4719 7722 0 88
1 2 4 7 12 20 33 54 88 0

→ Reply

indubitable

5 years ago, # |

← Rev. 2 →

-52

Can someone explain. The sol of C

→ Reply

satashun

5 years ago, # |

← Rev. 2 →

+46

Problem A,B,C and E were written by me. Thank you for your participation!

→ Reply

crazy__1234

5 years ago, # ^ |

can u tell me How this Solution of problem A Passes...https://atcoder.jp/contests/diverta2019-2/submissions/5917384... I Think This Is wrong....

→ Reply

satashun

5 years ago, # ^ |

I didn't come up with other solution but N — K, so I generated random cases other than K = 1 case, then only K > N / 2 cases were included and N % K = N — K for those cases by accident. Sorry for weak testcases..

→ Reply

bigbigbigbigcat111

5 years ago, # ^ |

After reading the editorial E, I still don't understand how you get rid of the "orders".

→ Reply

Sturdy

5 years ago, # |

For the third sample test case in problem B why is the answer 2. What are the values of p and q taken

→ Reply

indubitable

5 years ago, # ^ |

Ya I was too confused due to. It

→ Reply

soul_voyage

5 years ago, # ^ |

(0, 1)

→ Reply