Dude, application fees :3 But first things first, how dare you say her name!

But now rules should get changed

Maybe even high-precision randoms!

Oh,No.The best time is before 8 p.m, so that they can go to bed earlier.

code with girlfriend wonderfully

Yeah1.

4(2)

How did you vote twice??

To get all the combination, Ehab and Mahmoud is the last one to start with :)

the next start is an empty string

or maybe concatenated version MahmoudEhab:)

Upto 2099, but if div1 and div2 rounds are held simultaneously people who are rated greater than equal to 1900 must participate in div1

You need to register before the contest starts. Registration's usually open till 5 minutes prior to the start of a contest. Some contests support extra reg which opens 10 minutes after the contest start and continues for 20 minutes.

There's no window, the contest starts at the same time for everyone.

cute !!

No

The description of the topic is short and concise。

if only query d at beginning and query s on LCA

then will get FST

   /\
  /\ \
 /\ \ \
/\ \ \ \

but I have no idea to solve it correctly now : /

Think in terms of prefix xors.

Instead of directly construct the array, just construct the prefix xor version of the array S1, S2,..., Sn. So the condition that no subseg has the xor equals to 0 or x is the same as the array S is distinct and there is no pair in S that xor of them is x.

So iterate from 1 -> 2^n-1, if x^i also belongs to the given range [1, 2^n) then just pick one, or else pick both.

To construct the answer array A from S, use : Ai = Si^S(i-1).

First observation, if there is no number x restricted. You can simply construct something like 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1... This pattern is optimal because at every i-th number where i is 2^x, you cannot add any new number using numbers in range [1..2^x), any new addition will cause XOR to be 0. Hence, you will need to add 2^x every time you are at the 2^x-th number (1, 2, 4, 8, 16, ...).

Now, what about the restricted number? Well you can simply take the biggest 2^x that forms x. e.g. if x is 5, restricted number will be 4. Now, you can simply skip the restricted number when you want to form the sequence. (Why biggest? To minimize the largest number in the sequence) e.g. x = 5 1 2 1 8 1 2 1 16 1 2 1 8 1 2 1, if at any time the number has exceed 2^n, just stop adding new sequences.

What can be pretest 7?

I will explain the complete solution of D.

To be honest, B is so simple. If we have both odd and even numbers, then the sorted array is the answer, or else just print the original array. Correct me if I'm wrong

if the input contains both odd and even numbers the result will always be a sorted array.

You need to notice that, if there are only odd or only even numbers you can not make any swap. Otherwise you can sort the whole array.

If we have at least one odd and another even number, we will be able to reorder the whole array (swap two odd numbers or two even numbers). For example, if you wanna swap two odd numbers o1 and o2, with an even number e, you can do:

swap o1 and e, swap e and o2, swap e and o1.

And the position of o1 and o2 was swapped as a result.

Firstly, ask the distance from 1. Now find the centroid of the current tree and check if it is an ancestor by checking if dist(root,centroid)+dist(x,centroid) == dist(root,x) , if that holds true, query the next node on the path and make it the root and now distance from root is dist(x,centroid)-1. otherwise, you can delete the subtree rooted at the centroid and everything else remains the same.

In my room there were submissions that checked if there is any odd numbers and sorted based on that (I found one more submission like that after the end of contest :@ ) .

One of the mistakes on problem A was dividing sum of the numbers by 2 for checking the answer, while the sum is odd.

Sorry for bad English. :)

wow 3 hacks, how did you get them? was there a corner test case or something?

it can be solved using Centroid

After solving (A,B,C)^zzzzzzzzzzzz
01:59:29 Successful hacking attempt

Every number has only one number that makes (A^B == X) true. The problem asks for sub segment so it's another way to tell you to think of prefix xor. The answer should be clear after that.

For E, $$$a_1=p_1^{e_1}p_2^{e_2}$$$. then max is $$$1+e_1+e_2$$$. that's exp step down. so $$$a_1$$$ must be $$$2^k$$$ or $$$2^{k-1}3$$$ (if $$$\leq n$$$). then remain is combination count. but no time to code.. the annoying $$$3$$$.

Am I right? or is there a better solution? wait for tomorrow morning:) sleep now

Actually, I didn't use DP. I used only multiplying. Seriously, I didn't use DP.
My solution of problem E is as follows:

---

Step 1: What is the maximal possible value of $$$f(p)$$$?
Actually, the maximal possible value of $$$f(p)$$$ is as follows:

• $$$1 \leq N \leq 1$$$ : $$$max=1$$$
• $$$2 \leq N \leq 3$$$ : $$$max=2$$$
• $$$4 \leq N \leq 7$$$ : $$$max=3$$$
• $$$8 \leq N \leq 15$$$ : $$$max=4$$$
• $$$16 \leq N \leq 31$$$ : $$$max=5$$$

• 1st value: $$$8$$$. Only $$$1$$$ way.
• 2nd value: $$$4$$$. Only $$$1$$$ way.
• 3rd value: $$$2, 6$$$. $$$2$$$ ways are possible.
• 4th value: $$$1, 3, 5, 7$$$. $$$4$$$ ways are possible.

• There are $$$1$$$ ways to insert $$$1$$$: Just after $$$5$$$.
• There are $$$2$$$ ways to insert $$$3$$$: Just after $$$5$$$, or just after $$$1$$$.
• There are $$$3$$$ ways to insert $$$7$$$: Just after $$$5$$$, just after $$$1$$$, or just after $$$3$$$.
• There are $$$5$$$ ways to insert $$$2$$$: Just after $$$6, 5, 1, 3$$$, or $$$7$$$.

• Ways to write: $$$1 \times 1 \times 3 \times 6 = 18$$$ ways
• Ways to insert the other values: $$$1 \times 2 \times 3 \times 4 \times 5 \times 7 \times 8 = 6720$$$ ways
• So, the answer will be $$$18 \times 6720 = 120960$$$.

what i felt and is true for most cases : if u don't know proof just input garbage and get gold.

Yeah exactly same over here too!

"You are allowed to not change the order", not "You must to not change the order"

Please read it carefully :

You are allowed to not change the order.

I guess u miss read it as:

You are not allowed to change the order.

You can use a method named "Heavy-Light Decomposition".

The test 63 is the hack I used during the round, so I want to clarify a couple of points:

First that seems the only test with anti Quick sort test, I can see that 150+ solutions failed this test and if it wasn't added all these solution may have been passed, I've also always see Quick sort solution pass sys test in previous rounds, so I think such test should be always added to any problem that require sorting.

Also I'm not very proud with that kind of hack, because all I did is check if a java solution that uses sort for primitive array, so I want to raise attention against this.

For those who still want to use primitives you can build your own sort function like the radixSort function that I use in my solutions, wich I copied from uwi code ( I hope he doesn't mind )

Problem is not time limit. Problem is the inbuilt sort in Java have worst case complexity of n^2. Hence the time limit. There is blog somewhere on the codeforces discussing this SORTING IN JAVA.

Arrays.sort() for primitive data types in java uses quick sort O(n^2) while Collections.sort() uses merge sort . Quick sort can have O(n^2) complexity in worst case

I also used BufferedReader, Arrays.sort(), and StringBuilder but still got a TLE :(

https://mirror.codeforces.com/contest/1174/hacks/560684/test

But I still don't get why?

May be it's because you have a query in your main but you didn't count that ?

I dont think randomized was intended. But sometimes its difficult to break randomised. Until and unless probability of failing it is high.
I did saw some randomised solns and one of my friend also used randomised in F.

what about the left of your monitor xD

Simply, as far as I know, the contribution points are the sum of the total votes you get in your blog posts and comments/replies divided by 5. Or maybe, it uses some logarithmic calculations.

If your total votes are 100, your contribution will be (100/5) = 20. And if it's -100, your contribution will be (-100/5) = -20.

Check those out:

• https://mirror.codeforces.com/blog/entry/52692
• https://mirror.codeforces.com/blog/entry/8963