well it would be mike thanking himself :)

for Asian students!

And Australian!

dont't be stupid

You have to be really bad to have a negative rating (like worse), so the wish is likely to come true.

In previous contest U got TLE.

There will be english statements

why don't you like geometry problems?

geometry is good, it makes people cry T_T

You mean the time that is shown below the submission during the contest.

Its the time when you've submitted the solution after the start of the contest. '00:04' Would mean that you've submitted the solution after 4 minutes

2 hrs

Still can't register in div.2 ((

How is it possible to do D problem in 2 minutes :O.Is it a joke? :|

Same case in hackerrank. People have multiple accounts, view problems from one account and once they got the solutions, they submit all at once.

Looks like someone else submitted his C first and later he resubmitted. Look at the programs. There is no template in the first submission of C.

I think destinydrifter can explain better

I only stuck for checking is it valid permutation. Simply I do not see why it means that all n² pairs will produce correct answer as valid permutation.

Yeah so querying these is enough.

I did not check that p[] are distinct, but I don't think that there could be 2 the same elements.

All elements of p are always distinct in all potential permutations.

Say p_i = p_j. But then xor(p_i, p_j) = 0. Hence p_i = p_j in all potential permutations and there is no answer.

Besides, you need to apply this procedure only for even n. For odd n, p0 is uniquely determined, hence only one possible permutation.

My solution:

I first find the value of a[0]^b[i] for all 0<=i<n (by query(0,i)) let v[i]=a[0]^b[i] for all 0<=i<n Next, I fix the value a[0]=j, 0<=j<n Now, its not hard to produce b and the corresponding a array using the above definitions. Then, just check the validity of this solution.(All this is being done for a fixed value of j) What's wrong with this approach? I am getting WA at test 7

3 2 1 8 1

Depends on the solution. I used the following hack a lot for the ones who used sorting:
3 2
1 2 1

Let's say that two points are connected if they lie on the same horizontal or vertical line. Find connected components. For each of them, let L denote the number of possible different lines you can draw, and let P denote the number of points.

For example, for a single point L = 2 and P = 1. For two points with the same y-coordinate it would be L = 3 and P = 2. For the sample test with four points it would be L = 4 and P = 4.

It turns out that you can draw a subset of L possible lines if and only if its size doesn't exceed P. So the answer for this connected component is .

Make a bipartite graph like this :

In one of the parts put a node for every x. And in the other part put a node for every y. Now a point in the problem at coordinate (x_i, y_i) is an edge in the graph that is between node x_i in th first part and the node y_i in the other part .

Now consider a connected component , consider that it has k nodes.

If this component has a cycle , then you can make all 2^k states for horizontal or vertical lines in this component .

Otherwise when the component is a tree you can make all of the states minus the state that all the nodes (vertical and horizontal lines) appeared , so it has 2^k - 1 states!

I see Div1 C smth likes ARC83 F: https://atcoder.jp/img/arc083/editorial.pdf.

    if (n % 4 == 0) return n / 4;
    else if (n % 4 == 1) return (n - 9) / 4 + 1;
    else if (n % 4 == 2) return (n - 6) / 4 + 1;
    else if (n % 4 == 3) return (n - 15) / 4 + 2;

"if(x&1 || x<4) ans=-1;"

This is wrong. What if x = 9?

My logic was:

if N is Even:

       If N < 4: -1;

       Else If N >= 4: N / 4;

else N is Odd:

       If N >= 9 and N != 11: 1 + (N — 9) / 4;

       Else : -1;

every number 11 > can be expressed as sum of composite numbers

so if n<=11: you can precalculate that that

else if (n & 1) n-9,ans++

if (n % 4 != 0) n-6,ans++

ans += n/4

public static int solve(int n) {
		int c=0;
		if(n%2==1) {
			n-=9;
			c++;
		}
		if(n%4==2) {
			n-=6;
			c++;
		}
		if(n<0) {
			return -1;
		}
		return c+n/4;
	}

31347433

maybe you used endl , it calls os.flush()

I don't know which ones where in pretests, so I'll write some special cases:

5
5
9
11
13
15

Why is distance being further than 3 impossible?

Could you explain how you count these pairs with a fenwick tree a little more? Maybe it's less complex than I'm making it out to be, but I got the conditions in-contest but couldn't figure out how to count them easily.

I don't think we need BIT here.

To find the number of pairs for which lp(i) * lp(j) <= n, just store the prefix frequencies of the lp array. Then for every i, add pref[n / lp[i]]. Remove the number of i, such that lp(i) * lp(i) <= n, and divide by 2.

Link

Thank you for this solution. I would like to add that it can be adapted to O(n) by using two pointers instead of Fenwick trees. Code : 31374591

I used greedy: keep subtracting 4 from the number.
If n % 4 == 1: Use 9 as your composite number.
If n % 4 == 2: Use 6 as your composite number.
If n % 4 == 3: Use 15 as your composite number.
This is the rough idea behind the problem.

Anyway, how did you check primality of numbers up to 1e9 using sieve, not miller-rabin?

cheaters xD

It's about n^2 brute-force. You can query (0..n-1, 0) and (0,0..n-1) and try every position of b0, say fix b0=i.Then reconstruct p from pi=b0^(saved query(i, 0) value). Finally, check whether it is a valid permutation and consistent with the queries.

На прошлом раунде взяли 100 человек, так что еще неизвестно )

Same thing happened to me, which wasted me 30 minutes and 7 incorrect submissions = almost 500 points.

I think the main problem is constructing compressed tree for that k vertices. I remember it is to solve this: https://open.kattis.com/problems/optimistan.

Pick a pair of special vertexes U,V that are as far from each other as possible. Construct a chain that connects them (these are the points with d(U,W)+d(W,V)=d(U,V) ordered by distance from U). Consider subtrees rooted at each vertex from this chain. We can easily split all vertexes into these subtrees. The distances to each vertex X from X's root Y equals to d(U,X)-d(U,Y). So we may treat roots as special vertexes. Most of subtrees will have only one special vertex — the root. They may be processed in O(N) in total. For the other subtrees we recursively call the same procedure.

This process seems to terminate quickly. On every step each subtree will lose 2 special vertex, but it may possibly generate some new. The more subtrees there are, the faster the special vertexes are lost. It seems all vertexes will be processed in O(K) iterations and problem is solved in O(KN).

1. Seeing, that you can achieve it, is pretty easy. You can take that one element as one segment, and the rest as the other.

2. Let's assume we achieve an answer x such that x > max(a₀, a_n - 1). If this element is in the first segment, then the first segment's value should be x, but since x > a₀ the score will be at most a₀. Same goes for the second segment, so x can be in neither segment, which is contradiction.

Splitting of array a of n elements into 2 subarray，it must be a prefix and a suffix. for the minimum to be larger, we make the 2 subsegments [0,n-2] and [n-1, n-1] or [0, 0] and [1,n-1]

I think you don't need to do this. I'm just lucky. :)

I will try to explain a possible approach.

First, if you want to represent n as a sum with lots of summands, those summands have to be small. Therefore you should ask yourself, what is the smallest suitable summand? It is 4. Can you use only 4? Only if n % 4 == 0. What about the other remainders modulo 4? You are obliged to use something else apart from 4.

The next composite number is 6. You can see that if n % 4 == 2, using one 6 and all 4 is optimal. But you cannot obtain any odd n using only 4 and 6.

Hence you need to use one more number. Maybe 8? No 8 is not useful as 4+4=8. Maybe 9? Yes! Using one 9 and all 4 you can obtain all n % 4 == 1.

The only remaining case is n % 4 == 3. Can you get it using only 4, 6, 9? The answer is yes as 6 + 9 % 4 == 3. The issue is that this is no more trivially optimal and you have to check the optimality. However, checking it is super-easy, as the smallest useful number (i.e. it is composite and it cannot be generated as a sum of 4, 6, 9) is bigger than 6+9 = 15 and therefore using 6+9 is optimal if n % 4 == 3.

p.s. I have ignored all small cases. As a byproduct of the explanations I have given ,those are all impossible (1, 2, 3, 5, 7, 11).