There is something seriously wrong with the people on this website.

24 downvotes for what? Being excited about a new contest?

the crossed finger trick do not worked for me (sad wale emoji)...

shit got real

You said the exact same thing last time as well.

For what?

for me too

Ah well, C really threw me off. Guess next contest then.

I got TLE! Created 5 arrays according to string sizes.
Accordingly, there will be 4 pairs that produce even sums ((1, 3), (1, 5), (2, 4), (3, 5)).
Also, count among themselves meaning among array of length 1, 2, 3, 4, and 5.
Got TLE for this!

Any leads how to solve it?

you can observe that $$$a_{1} ⊕ a_{i} = b_{1} ⊕... b_{i-1} .$$$ Thereafter try to find $$$b_{1}$$$ bitwise

ig you are talking about the hard version because easy version can be solved using bitmask dp

Hint — You have to choose each bit of b0 independently.

Determine if each bit of b0 should be 1 or 0 by comparing with how many 1s should exist in the final array.

First initalize it with 0, and caluclate every $$$b_i$$$. Notice now that if you flip a bit in $$$b_0$$$ for ever $$$b_i$$$ that bit flips as well. We can precalculate the number of apperences for each bit in the solution of correct $$$b$$$. Now we can simply compare the occurences of bits in our current solution and the number of bits in the correct solution. If they are the same we do nothing, else we flip.

From b[i]^b[i+1] = a[i], we can deduce b[i] = b[1]^a[1]^a[2]^...a[i-1]. Since, the answer always exists all prefixes a[1], a[1]^a[2], ..., a[1]^a[2]^a[3]^...a[n-1], will be unique. So just fix b[1] and check for maximum and minimum XOR

Most likely people will tell you a solution which considers each bit separately (it is easier to code), but when this problem was proposed, I solved it in a different way

Can you tell what the approach was for C. I was doing a 0(n2) but it was giving a TLE. Without checking all the combinations how is it possible?

Used trie, looking for solution that doesn't use it

They should have given a smaller test case to fail the solution where (i,j) and (j,i) both does not satisfy. Wasted too much time thinking it was symmetric.

because it is O(n^2)

Your solution is $$$O(n^2)$$$ if there are n/2 with length 4 and n/2 with length 2.

How do you hack a randomized solution? I can get your code to fail against some tests on my local machine, but if I try to hack you then it'll fail since the seed is different on the grading server. Is there any way to determine what the seed would be on the grading server? If not, then I don't think your solution is hack-able.

What does randomized solution mean?

Done

N=2**16+1 input b[0] = 2 ** 16 b[i]= i xor b[0]

answer must be: a[i] = i

I'm going to return to Specialist!!! Ah I'll never take a part in any edu. round anymore!!!!

screaming

it's kinda easy when n is odd (you can simply calculate first element knowing xor of all of them), but could not find proper solution when n is even >_<

was sure that optimized n^2 goes through, but spend toooooo much time making up formulas

I don't exactly know why your solution is correct for odd $$$n$$$, the way I found $$$b[0]$$$ is first to find the prefix XOR of the array $$$a$$$. Then count the number of occurrences of each bit in the prefix XOR array. Compare it with the number of occurrences of each bit from $$$0$$$ to $$$n - 1$$$.

The bits whose number of occurrences is not equal should be in $$$b[0]$$$. (We can see that if the number of occurrences of some $$$i$$$-th bit is $$$k$$$, then choosing that bit in $$$b[0]$$$ will change its number of occurrences to $$$n - k$$$.)

The remaining numbers can be calculated easily.

Could you explain your solution?

230568418 230566680 More

Count number of arrays with minimum element $$$<x+k$$$ then subtract out number of arrays with max element $$$<x$$$. To do first part consider the number of difference arrays on $$$n$$$ elements, $$$(2k+1)^{n-1}$$$ then consider that you can shift the array up/down to decide where the minimum element will be with $$$x+k$$$ options. To find what we need to subtract out I did matrix expo.

Let an array $$$a$$$ be good if

• $$$a_i \ge 0$$$ and
• $$$|a_i - a_{i-1}| \le k$$$

Now the answer is equal to (the number of good arrays that contain an integer in range $$$[0, x+k)$$$) minus (the number of good arrays that only contain integers in range $$$[0, x)$$$).

The number of good arrays that contain an integer in range $$$[0, x+k)$$$ is equal to $$$(x + k) \cdot (2k + 1)^{n-1}$$$

The number of good arrays that only contain integers in range $$$[0, x)$$$ can be calculated with fast matrix exponentiation:

Let $$$A[n]$$$ be an $$$x \times 1$$$ matrix where $$$A[n]_i$$$ is equal to the number of good arrays of length $$$n$$$ that only contain integers in range $$$[0, x)$$$ with final element equal to $$$i$$$.

The number we want to calculate is $$$A[n]_0 + A[n]_1 + \dots + A[n]_{x-1}$$$.

Clearly, $$$A[1]_0 = A[1]_1 = \dots = A[1]_{x-1} = 1$$$.

Let $$$M$$$ an $$$x \times x$$$ matrix: $$$M_{ij} = 1$$$ exactly when $$$|i - j| \le k$$$.

We can notice that $$$A[i+1] = MA[i]$$$. This means that $$$A[n] = M^{n-1}A[1]$$$.

Such a counterexample is not possible. The fact that a solution exists guarantees that all arrays you can generate consistent with A have distinct elements. There is only 1 possible sequence of N distinct integers that has the same sum as 0+1+2+..+N-1, so your solution works.

You can prove this more formally by noticing that given A, the generated sequence B is determined entirely by the choice of the initial element B[0]. More formally, we can define B(n) as the candidate sequence B that starts with n:

B(n)[0] = n
B(n)[i] = B[i - 1] ^ A[i - 1] = n ^ A[0] ^ A[1] ^ .. ^ A[i -1]  (1 ≤ i < N)

Then it's clear that B(x)[i] = B(0)[i] ^ x, and therefore B(y)[i] = B(x)[i] ^ (x ^ y).

It follows that if there is any value of x such all elements of B(x) are distinct (which the problem guarantees), then for all x, all values of B(x) must be distinct, because you can't make two distinct value equal by XOR'ing them with the same constant.

There are no setTestCase calls in either of them. Idk why it became ugly on cf recently, but I also noticed that.

Only failing on test 1 is penalty-free, independently of the number of samples

From the statement:

After a card is beaten, it returns to the hand of the player who played it. It implies that each player always has the same set of cards to play as at the start of the game.

Does this not answer your question?

Each combined ticket consists of two snippets ("snippets" meaning strings in the input). There are three possible cases:

1. The two snippets are equal length, e.g. "123" + "222" = "123222" ($$$1+2+3 = 6 = 2+2+2$$$).
2. The left snippet is longer than the right, e.g. "1234" + "11" = "123411" ($$$1+2+3=6=4+1+1$$$).
3. The right snippet is longer than the left, e.g. "26" + "1234" = "261234" ($$$2+6+1 = 9 = 2 + 3 + 4$$$).

Define count(len, sum) as the number of snippets in the input that have length len and the sum of the digits is sum. It's easy to precalculate and store these in an array count[6][46] or something (since length is limited to 5, and therefore sum of digits is limited to 45).

Now for each snippet, consider how many of each of the three cases you can generate.

For case 1, a snippet s with length l and sum s can appear on the left side exactly count(l, s) times (i.e., it can be paired with each snippet [including itself!] that has the same length and digit sum). That's the easy case. (You might ask: what about when s appears on the right side? Ignore that case to avoid double counting.)

For case 2, a prefix of s of length k will be the first half, and the remaining digits will be part of the right half. So for example, if we have s="1234567" which has length 7, we can construct tickets "123456|7abcde" or "12345|67abc" or "1234|567a" (where '|' marks the middle). Consider the first one: "123456|7abcde". Here, the left side has sum 1+2+3+4+5+6 = 15, so the right side must have the same sum. The right side already has a 7, so the remaining 5 digits (*abcde*) must have sum 15-7=8. So the number of tickets of the form "123456|7abcde" is count(12-7, 1+2+3+4+5+6-7). Similarly, the number of tickets of the form "12345|67abc" = count(10-7, (1+2+3+4+5)-(6+7)) You can generalize this to something like: $$$count(|s| - k, \sum s_{1..k} - \sum s_{k..|s|})$$$ for all $$$|s|/2 < k < |s|$$$.

Case 3 is exactly the same as case 2 but using suffixes instead of prefixes.

You can use this to generate test cases yourself:

https://github.com/muzaffr/stress-tester

Only works on Linux, if you have Windows try using WSL

For each number, calculate the length,the length of the first half and the sum of digits in the first half of the prefix it needs as a suffix,and put them in a three-dimensional bucket. Then use all the numbers to match these as prefix. 231178050

The problem says that once a card is beaten, the player draws it back, so it is always optimal to play the best card $$$b_j$$$ against a card $$$a_i$$$ such that attack of $$$b_j$$$ > defense of $$$a_i$$$, and the defense of $$$b_j$$$ is maximum among such possible cards. This means we can make directed edges among the cards of Alice and Bob.

Those cards for which there are no possible opponent cards which beats them, are considered to end the game. Now, as we have a directed graph, we can easily use dfs to find out which the result for every card $$$a_i$$$. Note that, for every component in the directed graph, there would be at most one cycle in that component.

https://codeforces.net/blog/entry/121963?#comment-1082761 It might be helpful(at least for me)

it's impossible but he promised that it's always possible to construct at least one valid array b from the given sequence a.

now it is showing that i haven't even given this contest . What is happening?

Cu Ball

not many, but all

hope it will be fixed an not be unrated...:(

MikeMirzayanov

https://codeforces.net/blog/entry/121963?#comment-1082936

i think the standard solution of problem e may be wrong

That is common. All of these kind of contest(div3, div4 and edu) have an open hack. And the rating change will be much slower.

I think D is not repeated because the main focus of this question is to transform it into "find the max after xor given integer". It is easy to solve the latter lol.

The reduction to this basic 01trie trick requires some non-obvious steps, such as taking the prefix sum, then proving that the prefix sum must be unique, and finally reducing it to the condition of max XOR-sum $$$\leq n-1$$$. And also that problem on leetcode only involves the case where $$$n$$$ is odd, which is trivial and imo does not provide additional insight to the even case.

It was a hack with a java21 generator, but the judging system wasn't re-configured to support them. I already fixed it.

I think 5h for a rated contest is too much because of time zone difference and usual life stuff that might take over and not let many fully concentrate on the contest for so long