Привет, Codeforces!
В 03.11.2023 17:35 (Московское время) состоится Educational Codeforces Round 157 (Rated for Div. 2).
Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.
Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.
Вам будет предложено 6 или 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.
Задачи вместе со мной придумывали и готовили Адилбек adedalic Далабаев, Иван BledDest Андросов, Максим Neon Мещеряков, Артем Ferume Иликаев, Руслан AcidWrongGod Капралов, Алексей ashmelev Шмелев, Александр fcspartakm Фролов, Дмитрий DmitryKlenov Кленов, Дмитрий dmitryme Мещеряков и Елена elena Рогачева. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.
Обратите внимание, что данный раунд частично пересекается по задачам с Чемпионатом Юга и Поволжья России. Если вы участвовали в данном соревновании, то, пожалуйста, воздержитесь от участия в раунде.
Удачи в раунде! Успешных решений!
Также от наших друзей и партнёров из Harbour.Space есть сообщение для вас:
Harbour.Space University в партнерстве с BIMBA Y LOLA предлагают стипендию для получения степени магистра в сфере Computer Science, а так же опыт работы в качестве Junior Java Developer в команде разработки BIMBA y LOLA.
В BIMBA Y LOLA понимают важность работы с самыми креативными профессионалами, с предприимчивым духом и страстью к своей работе. Их соблазняет талант, сопереживание, инициативность, аналитический характер, приверженность качеству, проницательность и любовь к деталям. И, конечно же, явное призвание к моде.
Если вы разделяете эти ценности, то мы предлагаем вам молодую, динамичную и стимулирующую среду, в которой вы сможете развиваться профессионально; компанию, реализующую амбициозный международный план расширения и уже присутствующую более чем в 18 странах.
Все успешные кандидаты будут иметь право на получение стипендии со стопроцентной оплатой обучения (29 900 евро в год), предоставляемой BIMBA Y LOLA.
Требования:
- Свободное владение испанским и английским языками обязательно
- Степень бакалавра в области математики, статистики, науки о данных, информатики или аналогичной.
Кандидат должен быть знаком с:
- Agile Methodologies (scrum)
- GIT
- Java 8/11+
- Spring
- Maven
- JUnit
- Mockito
- UML
- HTML
- CSS
- Javascript
- ReactJS
- SQL Server/MySQL
Желательные навыки:
- Azure
- Azure DevOps — Pipelines
- Docker
- Kubernetes
- Helm
- Jira
- Confluence
Итого:
- 100% стипендия для получения степени магистра в области Computer Science в течение одного года.
- 4 часа/день стажировки в кампусе.
- Конкурентное вознаграждение.
- Возможность присоединиться к компании полную ставку после окончания обучения.
- Пожалуйста, обратите внимание, что заранее отобранные кандидаты должны будут заплатить невозмещаемый вступительный взнос в размере 125€ за оценку.
Обязательства кандидата:
- Обучение: 4 часа/день
- Вы завершите 15 модулей (длительность каждого 3 недели).
- Ежедневная учебная нагрузка составляет 3 часа, плюс домашнее задание, которое нужно выполнить в свободное время.
- Работа: 4+ часа/день
Погрузитесь в профессиональный мир во время обучения. Вы будете учиться у лучших и с первого дня сможете применять свои новые знания на практике.
UPD: Разбор опубликован
My comment is on top.... Can't believe this.. By the way thanks to authors for their hard work <3..
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)...
Wow, So exciting to see this round, I hope it will be interesting <3.
Wow, So exciting to see this round, I hope it will be interesting <3.
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.
is it rated?
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)
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.
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.me/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.me/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 \lt = i \lt = 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 \gt 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?
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://codeforces.me/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.me/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 $$$ \lt x+k$$$ then subtract out number of arrays with max element $$$ \lt 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
setTestCasein 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
setTestCasecalls in either of them. Idk why it became ugly on cf recently, but I also noticed that.Ideas
AThere can be two cases1. When x >= yIn this case we can just move along the path and pick the key until we reach the chest.2. When x < yIn 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))BTo 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.CA 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 + 2To 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.me/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 \lt k \lt |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 - 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
thank you!it is good for me,i have understanded.
How to solve F?
https://codeforces.me/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
b1as 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.me/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
java21generator, 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 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.