Helvetic Coding Contest 2024 Editorial

№	Пользователь	Рейтинг
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	155
8	TheScrasse	154
9	Dominater069	153
10	nor	152

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)

List<Integer>[] nids = new ArrayList[n+1]; for (int i = 0; i < t; i++) { int v = u[i]; if (nids[v] == null) { nids[v] = new ArrayList<>(); } nids[v].add(i); }

Комментарии (31)

Написать комментарий?

InfiniteStarlight

7 месяцев назад, # |

+25

The previous approach of just generating random words does not even come close to working for $$$n=1000$$$ (in fact, it is hard to push it beyond roughly $$$n=50$$$). Now we need to add our own insights to the process.

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.

→ Ответить

QuantumQuotient

7 месяцев назад, # ^ |

← Rev. 2 →

Thank You

Petr

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

+15

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

formidablechief27

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 a<b:
  return (a+5)*(b+1)-1
else:
  return (a+2)*(b+4)-1

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 :(

nassjes

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

SYUCT_blyat

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?

redsto

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..

Dominater069

+103

Let's play a game, spot the difference :

https://www.codechef.com/LTIME102A/problems/MINFUND https://codeforces.me/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)

Pirate_King

+30

-61

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)

jeremy_goku

+73

bro why are you too mad chill wtf

hashman

+21

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.

+139

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.

saarang

+63

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.

Galaxie_univers

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.

UP84

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

+17

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.

tu_rt_le

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

PsychoPinkQ

3 месяца назад, # ^ |

← Rev. 7 →

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 ith 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.

$$$M2 = \begin{bmatrix} \begin{align*} \sum_{1\leq i\leq m} (s_i + l_i)s_i & \sum_{1\leq i\leq m} (s_i + l_i)l_i \\ \sum_{1\leq i\leq m} s_i s_i & \sum_{1\leq i\leq m} s_i l_i \end{align*}\end{bmatrix}$$$

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 is

$$$ \begin{align*} (DP2[n][1] \sum_{1\leq i\leq m} (s_i + l_i)) + (DP2[n][2] \sum_{1\leq i\leq m} s_i) \end{align*}$$$

Sorry 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!

Code_Mystique

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 working

Is 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 like

dzhi

+10

My 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.

Monkey_d_Luffy-19834098

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.

theRealChainman

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.

Блог пользователя Petr