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:
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?
sorry x2
The best thing is to become gm
Educational round....ok(finger crossed)
the crossed finger trick do not worked for me (sad wale emoji)...
Nothing scares me more than edu round.
shit got real
Why has the frequency of edu rounds decreased?
Not complaining, just curious!
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)
edu rounds always bring me fear
For what?
somehow I feel it is harder than usual div 2 rounds.
for me too
Hoping for the final +14 for purple!
Ah well, C really threw me off. Guess next contest then.
GL everyone
Damn that Problem C is a good one. (T_T)
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
If someone needs clean Implementation for the problem
https://codeforces.net/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://codeforces.net/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 overflowE'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
Iterate 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.
Why should problems like C appear in CF?
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.
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://codeforces.net/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^2)$$$ if there are n/2 with length 4 and n/2 with length 2.
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://codeforces.net/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!!!!
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
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.
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 good if
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}$$$
Claim: The number of good arrays 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 1 arrays and type 2 arrays respectively.
The number of type 2 arrays 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 1 arrays is equal to the number of type 2 arrays by finding a bijection between the sets of these two arrays.
Consider the following process: take any type 1 array 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 1 array.
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 2 array 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 2 array. The resulting array must be a type 1 array, which can be shown by a proof by contradiction.
Suppose the resulting array is not a type 1 array. 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 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]$$$.
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 thereforeB(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 cases1. 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 basicallymin(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 thatO + 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).https://codeforces.net/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 :)
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 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.
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 - Torn Lucky Ticket 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?
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
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://codeforces.net/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 sinceb2 = 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)$$$.
why am i still unrated for this contest?
now it is showing that i haven't even given this contest . What is happening?
Same.
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://codeforces.net/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.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 Trie which 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.