**A1 - Balanced Shuffle (Easy)**

**A2 - Balanced Unshuffle (Medium)**

**A3 - Balanced Unshuffle (Hard)**

**B1 - Exact Neighbours (Easy)**

**B2 - Exact Neighbours (Medium)**

**B3 - Exact Neighbours (Hard)**

**C1 - Game on Tree (Easy)**

**C2 - Game on Tree (Medium)**

**C3 - Game on Tree (Hard)**

**D1 - Arithmancy (Easy)**

**D2 - Arithmancy (Medium)**

**D3 - Arithmancy (Hard)**

**E1 - Trails (Easy)**

**E2 - Trails (Medium)**

**E3 - Trails (Hard)**

**F - Playing Quidditch (Easy, Medium, Hard)**

**G1 - Min-Fund Prison (Easy)**

**G2 - Min-Fund Prison (Medium)**

**G3 - Min-Fund Prison (Hard)**

It is indeed hard to push it beyond roughly $$$n=50$$$, but yes, it's achievable. Randomly generate strings with at most $$$2$$$ letter $$$\texttt{X}$$$s and add them to answer if it does not violate any previous results. With some careful implementation and experiments, you can get a random solution that passes $$$n=1000$$$ in ~8 seconds. There's actually more room to improve i suppose, if anyone's interested in it, please try.

Thank You

Nice! I assume you also use a O(1) function to compute the spell power for such strings?

With the $$$n=1000$$$ limit one would almost definitely have to use a $$$O(1)$$$ function for the spell powers, and therefore the types or patterns of the randomly generated strings are actually limited tightly, making it easier to get to the correct random solution.

Enjoyable problem <3

Codeforces Helvetic Contest 2024

Detailed Video Tutorial B1 + B2 + B3

https://youtu.be/1s9NN3D3TWY

(Language => Hindi)

By the way, does anybody know a solution for D3 "on paper", without greedily finding a set without collisions?

For the first family of strings in the editorial, f(a,b) is very simple:

If not for the if, we could do something like "use b=p-1 where p is prime" and then the largest prime factor of f(i,j)+1 would uniquely determine the spell. But I do not see how to make this work with the if :(

Problem E2. Does A in the formula vk+1 = A*vk mean (sum of all Aij)?

It means the matrix A,which constisted by the combination of trials of each points

So we are multiplying a matrix by a vector and get a vector as the result? What should I search up to understand step by step how we get the result of that operation?

If you're familiar with matrix-matrix multiplication, you can just interpret the vector as a

`mx1`

matrix. You're multiplying a`mxm`

matrix by a`mx1`

matrix, so you end up with a`mx1`

matrix, that you can in turn interpret as a vector.thank you!! I was not familiar with multiplying matrices, so was a bit confused at first..

Let's play a game, spot the difference :

https://www.codechef.com/LTIME102A/problems/MINFUND https://mirror.codeforces.com/contest/1970/problem/G1

Even the story, problem name and subtasks are copied, they could have changed the cost function to at least hide it but no. Petr Kindly ban the person responsible for this from problemsetting (and also tell us who he is so we know)

I have been informed that authors were already aware of the fact that it was copied. Shame on all of you. Somehow they think that it is somehow better this way?? I would have been much more accepting to the fact that it was one bad guy instead of 10.

You can't reuse problems especially on big competitions like this. I thought that is obvious. Please mention such points in the blog announcement next time so i can skip fucking useless contests which have to resort to such measures (not that i gave it anyways, but that was because i was busy)

bro why are you too mad chill wtf

This contest allows you internet, and you think it's fair to have a problem that's easily searchable? Also, this is a semi-serious contest, not an educational contest for beginners or something. Also, in my opinion, the problem should be from a (reasonably) private contest, and the contest announcement should have a warning like so (similar to one of the previous rounds, where a problem was taken taken from Yandex Cup Finals, and tourist was the author):

"We have used a problem from [...] contest authored by [...] (replace with whatever), so if you have participated in that contest, please refrain from participating in this mirror."

For onsite contests (the contest that this was a mirror of was onsite), it is fine I guess for all practical purposes (it's actually not really fine, because this was supposed to be the hardest problem of the set according to solve count, and if some participants can just do it from memory, then there's no point), but for online contests where everyone can use the internet, it's not at all fine in my opinion.

I mean, his words were a bit harsh, but the point he's trying to make is legitimate, which is that you should mention when using problems from some contest, and the contest you are using problems from should be reasonably private.

Thanks.

Also its not fine even in the original contest. As soon as i read G, i got the distinct feeling of having seen the problem before (and instantly knew how to solve it). Since it did appear in a lunchtime, there is a high probability some of the 200+ psrticipants might have seen it too.

Thanks for bringing this to my attention, and I'm really sorry for this. I was not aware this problem appeared on Lunchtime. I am trying to figure out how this all happened.

Hi, I'm the original author of the problem. I shared the problem with one of the problemsetters and gave permission for it to be used in the contest. I sent the problem along with a bunch of problems used in a variety of school/private/public contests, so I guess the fact it appeared in a public contest was missed.

Can you give me the code of each question, please?

You can see the code for the accepted solutions by double-clicking the "+" in the standings.

E3 says Tutorial is loading,when will it be available?

If you refresh the page it will appear at some point, at least it does for me.

But for more reliable results, you can download the tutorial PDF from the "Contest materials" here.

Eyo, are there any other solution for E3. I see that problem quite fun lol.

I ACed with a different approach(as well as my orz friend the_coding_pooh) which is easier to come up with.

Instead of maintaining DP1[n][m] and do the recursive trick on a

`m×m`

matrix M1. Let's maintain DP2[n][2] and apply the same trick on a`2×2`

matrix M2.DP2[i][1] represents the ways of staying at the middle point for the

`i`

th time while the last trail is a short one. DP2[i][2] represents the ways that the last trail is a long one. M2[1][1] stores the ways of getting to the middle from a short trail and going to some random islands then back to the middle with a short trail, the same logics suit for [1][2], [2][1], [2][2] too.Set DP2[1] to {s[1], l[1]}, then multiple it with M2 for

`n-1`

times using the trick then you get DP2[n]. The ans isSorry for my poor English and creepy indexes, you can check my submission for better understanding though it's quite messy.

becaido, upvote me plz and get an IOI perfect score!

Can anyone tell why the

brute force approach is working for C-3?I mean

even the time complexity of O(n*t) is also workingIs it due to bad test cases or is it always possible that the algorithm will not give TLE? I am very much confused, please help me.

259726359 or 259723352

Both are of time complexity of O(n*t) with different approach. You can follow whichever you likeMy Java solution was barely Accepted with the exact time limit of 1000 msec. The algorithm complexity is fine as far as I can tell. I tried to optimize the code without success and suspect it might be implementation language related. In this case, the time limit of 1 sec appears rather tight to me.

After replacing the allocation of 200000 List (to group queries by node id) with int[][], the runtime drops from TLE to 921 msec. This is a nice learn of the overhead of Java List.

That's what he is asking...

Can you prove or give some rough idea of why O(n*t) is not giving TLE ?? Is it due to bad test cases or the algorithm always terminates in O(n) or O(nlogn)

My guess is that trees used in the tests are randomly generated with depth O(logn) instead of O(n). Whoever curious on the exact reason can test their code with a deep tree.

Using associativity for matrix multiplication to reduce the dimensionality of exponentiated matrix for E3 trails, really gave me a good review of linear algebra. Haven't had to think about those things in years. Great problem.