Hello Codeforces!

On Nov/03/2023 17:35 (Moscow time) Educational Codeforces Round 157 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be **rated for the participants with rating lower than 2100**. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest, you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given **6 or 7 problems** and **2 hours** to solve them.

The problems were invented and prepared by Adilbek adedalic Dalabaev, Ivan BledDest Androsov, Maksim Neon Mescheryakov, Artem Ferume Ilikaev, Ruslan AcidWrongGod Kapralov, Alexey ashmelev Shmelev, Alex fcspartakm Frolov, Dmitry DmitryKlenov Klenov, Dmitry dmitryme Mescheryakov, Elena elena Rogacheva and me. Also, huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

**Please note that the problems of this round partially intersect with the problems of the Southern and Volga Russian Regional Contest. If you took part in that contest, please refrain from participating in the round.**

Good luck to all the participants!

Our friends at Harbour.Space also have a message for you:

**WORK & STUDY OPPORTUNITY IN BARCELONA — BIMBA Y LOLA x HARBOUR.SPACE UNIVERSITY**

*BIMBA Y LOLA has partnered with Harbour.Space University to offer a Master's Degree scholarship in Computer Science, as well as work experience as a Junior Java Developer at the Development Team in BIMBA y LOLA.*

*At BIMBA Y LOLA, they understand the importance of counting on the most creative professionals, those with an enterprising spirit and passion for their work. They are seduced by talent, sensibility, initiative, an analytical nature, commitment to quality, a keen eye and a love for detail. And, of course, a clear vocation for fashion.*

*If you share these values, we are offering a young, dynamic and stimulating environment; one in which to progress and develop professionally; a company present in over 18 countries and embarked on an ambitious international expansion plan.*

*All successful applicants will be eligible for a 100% Tuition Fee Scholarship (29,900€/year) provided by BIMBA Y LOLA.*

**Requirements:**

**Spanish**and English language proficiency is a**MUST***Bachelor's degree in the field of Mathematics, Statistics, Data Science, Computer Science or similar*

*The candidate should be familiar with:*

*Agile Methodologies (scrum)**GIT**Java 8/11+**Spring**Maven**JUnit**Mockito**UML**HTML**CSS**Javascript**ReactJS**SQL Server/MySQL*

*Desirable skills:*

*Azure**Azure DevOps — Pipelines**Docker**Kubernetes**Helm**Jira**Confluence*

**Apprenticeship Summary:**

*100% Tuition Fee Scholarship to study a Master’s Degree in Computer Science for one year.**4 hours/day internship on campus.**Competitive compensation.**Opportunity to join the company full-time after graduation.***Please note**that preselected candidates will be requested to pay a non-refundable Application Fee of 125€ for assessment.

**Candidate’s commitment:**

*Study Commitment: 4 hours/day**You will complete 15 modules (each three weeks long) in one year.**Daily class workload is 3 hours, plus homework to complete in your own time.**Work Commitment: 4+ hours/day*

*Immerse yourself in the professional world during your apprenticeship. You’ll learn from the best and get to apply your newly acquired knowledge in the field from day one.*

**UPD:** Editorial is out

My comment is on top (yeee) ... By the way thanks to authors for their hard work <3... Hope we'll enjoy the round.

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

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

Thanks a lot...take love <3... .

sorry

sorry x2

The best thing is to become gm

The best thing to do is speak up and get rid of the anti social rejects

I have been Specialist for the first time.... Thanks to authors again..

Educational round....ok(finger crossed)

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

Wow, So exciting to see this round, I hope it will be interesting <3.

It is what it isNothing scares me more than edu round.

shit got real

Why has the frequency of edu rounds decreased?

Not complaining, just curious!

Consistent Authors, Hats off

I think the writer list on the Contest page doesn't reflect this correctly, it's currently just the usual BledDest-Neon-Roms-adedalic-awoo.

Educational Rounds are mathforces af. Would skip this one.

You said the exact same thing last time as well.

and I don't even understand what he means, if Edu rounds were mathforces I would've farmed the hell out of it

Right?!

i think he failed in maths in his high school :}

Who are you lil bro and how would you farm Edu rounds if they were mathforces?

If it were mathforces, I would gain rating over number theory tasks every contest, and take advantage of less implementation and more math/observation. That doesn't seem to happen to me anyways if you look at my contest record.

isnt almost every div2 just observation and constructive stuff tho lol (maybe im just having recency bias)

COME ON everyone!!!

I hope, inshallah! I will learn something new from this contest.

edu rounds always bring me fear

For what?

somehow I feel it is harder than usual div 2 rounds.

Big mind, big thought! It's feel little bit easier then usual div 2 for newbie people like us.

for me too

Hoping for the final +14 for purple!

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

If i do B question first and then A question, will I be in the same rank as the person who solved A problem earlier than me but our final time of two question is same?

Yes .. the rank will be same for this contest.

it follows the ICPC rules, which count the number of problems solved and the the sum of the time you solved each problem in minutes (of course + penality if you have).

GL everyone

Damn that Problem C is a good one. (T_T)

I agree with you.

Another great problem C in educational round.

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?

1) We can observe that two strings i,j will be lucky only if their parity is same since we want even length ticket.

2) So we can solve separately for odd (1,3,5) and even (2,4) since max length is 5 only. Now we just need to see among even and odd, let me consider even case. The combinations possible are 2+2, 2+4, 4+2, 4+4.

3) Since we want both halves to have same value, for 2+2 and 4+4 case, we will simply use map to store strings with same value and add it to answer. For example if there 3 strings of length 2 with value as 5 (maybe 23,14,32 etc...), then for each we will add 3 since we can concatenate to itself. This case will be same for 1+1,3+3,5+5.

4) Now for special cases like 2+4, 4+2 we just need to check what is the relation for example in 2+4 case, let ticket be ab+cdef. We want a+b+c = d+e+f, which is same as a+b = d+e+f-c. So we for every 2 length string we will add number of 4 length strings whose d+e+f-c = value of current 2 length string.

5) You can consider different cases like this for example in 3+5 case we want number of 5 length strings such that their last 4 — first digit = value of 3 length string.

Hope this helps

Yeah, thank you for the answer!

Upvoted!

If someone needs clean Implementation for the problem

CodEhttps://mirror.codeforces.com/contest/1895/submission/231214818

I tried submitting this, I cannot seem to think what am I missing in this. I tried to think if I recounted anything but cannot seem converge.

Help me debug, please

https://mirror.codeforces.com/contest/1895/submission/231216145

You are using a single frequency array to store all the counts try segregating them based on the size? Also

`for (int i = 1; i <= 45; ++i) { ans += total[i] * total[i]; }`

might overflowThanks! Your comment made me read the question once more. I completely misinterpreted. I was going for any suffix sum that matches the prefix + the sum of other entire sting or vice versa.

Clean solution! Thank you for sharing!

Upvoted!

E's statement is worse. Furthermore, it would be helpful to have an example or explanation provided for the problem

implementationforces

D is goated

How to solve D?

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

How to solve C?

Today's D problem is easy if you remember this problem exists

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

How to choose $$$b_0$$$ in D? Any observations, brute force approaches?

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.

Very smart approach! I used a very stupid 01 trie solution...

me too but i think it's not stupid and easy to think and implement(

Could you please explain how does a trie help here?

Let:

$$$c_{1} = a_{1}$$$

$$$c_{2} = a_{1} \oplus a_{2}$$$

....

$$$c_{n - 1} = a_{1} \oplus a_{2} ... \oplus a_{n - 1}$$$

The trivial solution would be we iterate $$$b_{1}$$$ from $$$0$$$ to $$$n - 1$$$ and find out the maximum value of $$$b_{1} \oplus c_{i} (1 <= i <= n - 1)$$$ by brute force. If this value is less or equal than $$$n - 1$$$, then we successfully find out a valid $$$b$$$.

However, the algorithm above is $$$O(N^2)$$$ To optimize it, we can use the 0-1 trie. Insert all the $$$c_{i}$$$ to a trie from the highest bit to the lowest bit. Then, we can obtain maximum value of $$$b_{1} \oplus c_{i}$$$ by traversing this trie rather than brute force. The time complexity becomes $$$O(NlogN)$$$

Understood, thanks!

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

SpoilerIterate on the first element in the resulting array (let it be $$$x$$$). To check that it is good, we need to make sure that all numbers of the form $$$x \oplus a_1 \oplus a_2 \dots \oplus a_i$$$ are not greater than $$$n-1$$$. To do it in a fast way, generate all values $$$c_i = a_1 \oplus a_2 \oplus \dots \oplus a_i$$$, store them in a binary trie, and find the maximum value of $$$x \oplus c_i$$$ with descent on the trie. If it is not greater than $$$n-1$$$, $$$x$$$ can be the starting element.

I mean, you can just bruteforce for all values of $$$b_1$$$ in $$$[0,n)$$$ and output the one where $$$max=n-1$$$ and $$$min=0$$$, right? That should be trivial using a binary trie storing all prefix XORs.

Also i don't think it is required to check the min , checking max is suff ig

Isn't that the exact same thing as what the parent comment from BledDest says?

BledDest's method focuses on which index to change to $$$0$$$, my method focuses on the literal value of $$$b_1$$$. Kinda similar I guess.

Are we reading the same thing? Quoting him...

The first element of the resulting array IS b1. So he's saying the EXACT same thing. (I hope I am not wrong here, it would indicate my final brain calls have finally passed away)

For what can come as the first element he is using whatever is in the array, I am using literally the interval $$$[0,n)$$$. Little details do matter

That is not specified anywhere in his comment?

I (reasonably) assume he means iterating over x in [0, n) only.

"find the maximum value of $$$x⊕c_i$$$ with descent on the trie"

That's the part implying he is using the prefix XOR values as $$$b_1$$$. Yeah I apologise, the difference in detail is too minor (just a small implementation advantage)

Oh no need to apologise, I simply wanted to confirm my understanding, I often second guess myself otherwise.

How does solving each bit independently gives correct answer? We also need to ensure that those bits need to appear in correct combination with each other. For example,(in bits), 000, 001, 010,011,100. And 000, 001, 010, 000, 111. Both have same frequency of each bit but they occur at different positions.

If some bit $$$x$$$ has the same frequency of $$$0$$$'s and $$$1$$$'s in the resulting sequence no matter how you choose it in the starting element, then it means that $$$n$$$ is divisible by $$$2^{x+1}$$$; and if we flip it, every number in the sequence just transforms from $$$b_i$$$ to $$$b_i \oplus 2^{x}$$$, which is a bijection when $$$n$$$ is divisible by $$$2^{x+1}$$$.

So, any such bits in the answer can be flipped without breaking anything.

My question is different. You are answering when frequency of a bit x is same in a set of numbers. My question is: There can exist 2 sets of numbers where frequency of each bit in the two sets are same but the sets are not same. S1 = {00,01,11}, S2 = {10, 01, 01}.

Since b[0] ^ b[i] = a[0] ^ a[1] ^ ... ^ a[i — 1], if you fix ith bit for b[0], then ith bit of b[i] is uniquely determined.

Yes, it is uniquely determined but how will you ensure that it is 0,1,2,3,4,...,n-1 only and not something else?

Suppose at ith bit there are a $$$ 0's$$$ and b $$$1's$$$ in $$$0,1,...n-1$$$ and p be the number of $$$1's$$$ at ith bit in prefix array. Then you can check if $$$ith$$$ bit of $$$b_{1}$$$ can be 0 if $$$p=b$$$ and $$$a>0$$$ otherwise it will be 1.

If we know the total quantity of $$$1$$$'s in each bit, we know the sum of all numbers. And for every set that is different from $$${0, 1, 2, \dots, n-1}$$$, its sum is strictly greater than required.

That's how I reason about it:

For $$$i$$$-th bit of $$$b_1$$$, the necessary condition is that $$$b_1, b_1 \oplus b_2, b_1 \oplus b_3, ..., b_1 \oplus b_n$$$ has the same number of set bits as sequence $$$0, 1, ..., n - 1$$$.

The only way for this condition to not be sufficient is if setting any bit for $$$b_1$$$ works.

That can only happen when there are initially more 1 bits in sequence than 0 bits (specifically there is one more 1 bit), which can't happen due to the nature of $$$0, 1, ..., n - 1$$$ sequence (at any n, number of 1 bits is not greater than number of 0 bits)

EDIT: i wrote some bullshit. Setting any $$$i$$$-th bit in $$$b_1$$$ works, if n is divisible by the $$$2^{i + 1}$$$, and it doesn't affect the answer, because there's always pair $$$(x, y)$$$ in $$$0, 1, ..., n - 1$$$, such that $$$x \oplus y = 2^{i}$$$

Considering each bit separately is also much easier to reason about, because the condition "every prefix xor of $$$a$$$ should have same number of set bits as sequence $$$0, 1, ..., n - 1$$$" is sufficient and quite natural to get across

how we ensure that the elements of the array will be unique?

for a solution $$$x_0$$$, if the resulting array has any $$$i,j$$$ such that $$$(x_0 \oplus c_i)=(x_0 \oplus c_j)$$$, then $$$c_i = c_j$$$, which means for any value of $$$x$$$, $$$(x \oplus c_i)=(x \oplus c_j)$$$, therefore there won't be any solution at all, which contradicts the constraint in the problem.

I was very close to what you was thinking but instead of thinking to store in binary tree I think that this may be done by greedily

Why should problems like C appear in CF?

is it ad-hoc ? just asking ?

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?

any target number would be at max 10, iterate over each number

Ex, 93746

9 3746 => (3+7+4+6) — (9), here we will check if we have any three-digit sum with this sum

Similarly, we will check for: 93 746 937 46 9374 6

Also, we can add a number from the backside as well, so check for suffix as well.

Used same approach but got wrong ans

Yes but how will you check in less than O(n^2) that"s my doubt

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

iterate over lengths of parts and then over largest of them => you can deduce sum of digits of smallest one (precalc them all)

since the maximum number of place is 5 you can just hash all option and then check for the correct ones.

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.

good contest

https://mirror.codeforces.com/contest/1895/submission/231204890 , Can anyone tell me why I am getting TLE , Sorry I am just dumb !

because it is O(n^2)

Your solution is O(n*n) and it will give TLE on the given constraints.

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

Thanks I get it now

I like problem C, even though I have not solved it because I had overcomplicated implementation.

Can anyone hack this? I did a randomized solution to D:

https://mirror.codeforces.com/contest/1895/submission/231206864

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.

If everyone creates an unique test case, then he will be hacked for sure.

What does randomized solution mean?

Done

Thanks. Is there a way I can see the test case?

Just any test with $$$n = 199\,998$$$.

Thanks!

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

answer must be: a[i] = i

Cannot find a good solution for D and bashed trie.

I'm not sure if this problem https://leetcode.com/problems/decode-xored-permutation/ is like today's problem D. These two questions are too similar. I think some people may have just modified the code a bit and moved it over, but I believe everyone wouldn't do that.

But this really affects my mood. In fact, I was looking for the problem for almost half an hour and I finally found it when the contest has finished for 30 seconds. Hope I will see every problem next round new, not existing.

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

screamingit'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

Is there any way to actually calculate b[0] in problem D ? I tried to compute XORs from 0 throught n-1, and it is equal to XORs of all prefixes ^(n times) b[0] . But sadly it doesn't help when n is even.

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.

The frustration of not being able to solve more than 2 tasks in div2 rounds is immense!

for G, splay tree: TLE Red black tree: AC(500ms)

don't know why :(

Could you explain your solution?

Two solutions that look similar 231191280 231185745

230568418 230566680 More

How can I solve F?

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

goodifNow the answer is equal to (the number of

goodarrays that contain an integer in range $$$[0, x+k)$$$) minus (the number ofgoodarrays thatonlycontain integers in range $$$[0, x)$$$).The number of

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

goodarrays of length $$$n$$$ that contain an integer in range $$$[0, x+k)$$$ is equal to the number of arrays of length $$$n$$$ where:Let's call these two types of arrays

type 1arrays andtype 2arrays respectively.The number of

type 2arrays is clearly $$$(x + k) \cdot (2k + 1)^{n-1}$$$: There are $$$x + k$$$ options for the first value and $$$2k + 1$$$ values for each subsequent value based on the previous value.We can show that the number of

type 1arrays is equal to the number oftype 2arrays by finding a bijection between the sets of these two arrays.Consider the following process: take any

type 1array and keep subtracting $$$k + x$$$ from every element of the array until the first element is in range $$$[0, x+k)$$$.With this process we can reach exactly one array starting from any

type 1array.We can represent the first element of the original array as $$$a_0 = q \cdot (x + k) + r$$$ uniquely with integers $$$q$$$ and $$$r \in [0, x+k)$$$. To satisfy the condition $$$a_0 \in [0, x+k)$$$, we need to subtract $$$x + k$$$ exactly $$$q$$$ times from each element. Doing this never breaks the condition $$$|a_i - a_{i-1}| \le k$$$ and thus, the resulting array is of

type 2.Reverse direction:

Consider the following process: take any

type 2array and keep adding $$$k + x$$$ to every element of the array until every element is non-negative.There is obviously only one way to do the above for each

type 2array. The resulting array must be atype 1array, which can be shown by a proof by contradiction.Suppose the resulting array is not a

type 1array. This means that one of the following conditions must be violated:The first condition can't be violated by definition. The second condition can't be violated since the operations don't change the differences of consecutive elements. Thus, the third condition must be violated.

If all elements satisfy $$$a_i \ge 0$$$ and $$$a_i \not \in [0, x+k)$$$, then all elements must satisfy $$$a_i \ge x+k$$$. But in this case we could've done one less operation. All elements would been $$$x+k$$$ smaller but still non-negative, so we would've stopped earlier and never reached this position.

What if there was no 'last operation' (i.e. we didn't do any operations)? Then the first element would satisfy $$$a_i \in [0, x+k)$$$ so that condition would've been satisfied and we reach a contradiction. $$$\square$$$

The number of

goodarrays 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

goodarrays 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]$$$.

Thnak u so much for your detailed explanation!

But how can you come up with that? I just cannot think of this bijection myself.

Is there some basic logics under it or any problems similar to this problem?

Cu ball

I have another way to argue why the number of good arrays contain a element in $$$[0, x + k)$$$ is $$$(x + k)(2k + 1)^{n - 1}$$$.

consider fixing the difference array of $$$a$$$, clearly there are $$$(2k + 1)^{n - 1}$$$ ways to do this, then for each difference array, we can add the whole array with any integer(that is, translate the array horizontally), and let focus on the minimum of this array, clearly it must be no less than $$$0$$$ and less than $$$x + k$$$ to be a good array, so for a difference array, there are $$$(x + k)$$$ ways to do that, thus the number of good array is $$$(x + k)(2k + 1)^{n - 1}$$$.

Thank u! I've got it.

[ Deleted ]

Is there a case for D where the elements in the answer array can satisfy all the XOR properties, and whose sum is equal to the sum of [0, n-1], but is not correct? As in some elements might have duplicates and the max element can exceed n-1. My solution goes over the 2^19 ways to either set the ith bit in the first element on and off for each of the 19 bits. Then I just check the total sum in o(1) time for all of these ways to see if it matches the intended sum.

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:

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.

Why did the problemsetters use

`setTestCase`

in the validators for single-test problems C and D (and also in some other problem recently)? Samples look ugly, and the use of this function here is pointless.There are no

`setTestCase`

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

`A`

There can be two cases`1. When x >= y`

In this case we can just move along the path and pick the key until we reach the chest.`2. When x < y`

In this case we can greedily pick the chest when we see it until k + x <= y Then we can traverse the leftover distance twice to reach the chest again. So basically`min(k + x, y) + 2 * (y - min(k + x, y))`

`B`

To get the min path just sort the array choose first N points as X coordinates of each pair Choose the next N points as Y coordinates.`C`

A thing to notice is that`O + O = E`

&`E + E = E`

. Keeping this in mind the only way we can get even lengths are :=`1 + 1, 1 + 3, 3 + 1, 1 + 5, 5 + 1, 2 + 2, 2 + 4, 4 + 2`

To find these pairs fast you can notice for the S(s(1) + s(3)) the sum S[0,1] is nothing but s(1) + s(3)(0) and for S(s(3) + s(1)) the second sum is s(3)(2) + s(1). Similarly form these formulas for all other pairs and store each unique sum is 5 seperate maps (Since size of string is atmost 5).implementationhttps://mirror.codeforces.com/contest/1895/submission/231214818

awoo For Question D of today's contest, my submission had wrong answer on test 2, Test 2 was part of the samples, but still I got penalty for submitting a code that gave a wrong answer on samples, please look into it

Thank you

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

Took too much time to solve C :(

In Problem E, is the card returned to the hand of the player who beat the opponent's card?

From the statement:

Does this not answer your question?

Ha Ha lol :)

Please could you explain the G statement? How should I count inversions in the string, from which blues were removed? How many inversions do I have in this string: '0010000'. When should I choose 'blue' cost of a symbol instead of 'red'? Too hard for me to get it from statement

I would solve D i believe if I would not spend 50 minutes on G and somehow managed to miss the statement. Good job!

I've been reading many C solutions but didnt get them :c i had other approach but dindt get ac in contest T~T

Here is my code for C, i think it's more intuitive than others. or maybe not I match every 5-3, 5-1, 3-1, 4-2 lengths. Also count math with itself

Code for C T~Tbump

Can anyone please explain C?

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

Define

count(len, sum)as the number of snippets in the input that have lengthlenand the sum of the digits issum. 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

swith lengthland sumscan appear on the left side exactlycount(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 whensappears on the right side? Ignore that case to avoid double counting.)For case 2, a prefix of

sof lengthkwill 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" iscount(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.

My code is here plz . this is my submission.

Your code is not in a proper format. Better you add submission link instead of whole code.

I have provided the link . My code is here plz this ( it is the link)

a if condn was missing , now its solved . i aim to become expert by the end of this year , and do everything possible to acheive it

this contest proved how bad i am at implementation.

Can someone provide test cases for problem C? I'm struggling to come up with good ones to test my code. Thank you.1895C - Порванный счастливый билет 231207578

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

Video Explanation for Problem D

Was anyone able to pass a randomized solution for problem D?

ok, this is my first time hacking submissions in contests

how to solve C?i have no idea? need help

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

thank you!it is good for me,i have understanded.

How to solve E?__

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.

How to solve F?

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

In the question D of this contest, when can ai be equals to 2*n.

Is it even possible, If yes then the case??

As max value of A^B is A+B but not for A==B. Please help

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

I figured out that we only need to find

`b1`

as all other values can be derived from b1 since`b2 = a1 ^ b1, b3 = a1 ^ a2 ^ b1 ... bN = a1 ^ a2 ^ ... ^ aN-1 ^ b1`

. But I can't find fast way to determine if a b1 if valid how did you do that or if you have any other idea?You can just enumerate it, and try to check the answer in $$$O(\log n)$$$.

It says rated for people under 2100 but no changes so far in rating

why am i still unrated for this contest?

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

Same.

so is it a problem for everyone then ?

What happened on problem E? Why are there many judgement failed?

Cu Ball

not many, but all

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

MikeMirzayanov

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

What's wrong with problem E?

Everyone got Judgement failed in system test.

i think the standard solution of problem e may be wrong

now it is showing the contest but no change in rating.

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.

oh thanks . But will it show unrated until the rating is changed or does it show unrated if the rating won't change at all.

It show unrated until the rating is changed.

problem can easily be solved by https://www.geeksforgeeks.org/find-maximum-xor-given-integer-stream-integers/ and i read some comments saying that it was like another problems i think thats not ok that problems repeated

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.

Why are they not judging E? Did someone TLE/RE Hacked the main solution or smth?

It was a hack with a

`java21`

generator, but the judging system wasn't re-configured to support them. I already fixed it.Is the educational round unrated? The rating is still not updated..... It's my first educational round.... Someone please tell me

It has already updated

Isn't it a bit late for not putting Editorial?

Why not release full 5-hour version of a regional contest? What's the point in spoiling half of the problems?

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

Upd: the button has been pressed, and now we have a gym: 2023-2024 ICPC, NERC, Southern and Volga Russian Regional Contest (problems intersect with Educational Codeforces Round 157)

For F,why can (k — x + 1) be more than n.The situation doesn't follow condition 1.

MikeMirzayanov and awoo, User ALL_LOWERCASED, Sir-Ahmed-Imran and I got the solution of the problem D skipped because of similarities. But the code of the

Triewhich was common was taken from this website, the code which we used is at the bottom of the page.The code was available before the contest.