### Petr's blog

By Petr, history, 3 weeks ago,
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)
• +76

 » 3 weeks ago, # |   +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.
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 Thank You
•  » » 3 weeks ago, # ^ |   +8 Nice! I assume you also use a O(1) function to compute the spell power for such strings?
•  » » » 3 weeks ago, # ^ |   +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
 » 3 weeks ago, # |   0 Codeforces Helvetic Contest 2024Detailed Video Tutorial B1 + B2 + B3https://youtu.be/1s9NN3D3TWY(Language => Hindi)
 » 3 weeks ago, # | ← Rev. 2 →   +1 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
 » 3 weeks ago, # | ← Rev. 2 →   0 Problem E2. Does A in the formula vk+1 = A*vk mean (sum of all Aij)?
•  » » 3 weeks ago, # ^ |   0 It means the matrix A,which constisted by the combination of trials of each points
•  » » » 3 weeks ago, # ^ |   0 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?
•  » » » » 3 weeks ago, # ^ |   0 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.
•  » » » » » 3 weeks ago, # ^ |   0 thank you!! I was not familiar with multiplying matrices, so was a bit confused at first..
 » 3 weeks ago, # | ← Rev. 2 →   +103 Let's play a game, spot the difference : 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)
•  » » 3 weeks ago, # ^ |   +30
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   -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)
•  » » » 3 weeks ago, # ^ |   +73 bro why are you too mad chill wtf
•  » » » » 3 weeks ago, # ^ | ← Rev. 2 →   +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.
•  » » » » » 3 weeks ago, # ^ |   0 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.
•  » » 3 weeks ago, # ^ |   +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.
•  » » 3 weeks ago, # ^ |   +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.
 » 3 weeks ago, # | ← Rev. 2 →   0 Can you give me the code of each question, please?
•  » » 3 weeks ago, # ^ |   +15 You can see the code for the accepted solutions by double-clicking the "+" in the standings.
 » 3 weeks ago, # |   0 E3 says Tutorial is loading,when will it be available?
•  » » 3 weeks ago, # ^ |   +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.
 » 3 weeks ago, # |   0 Eyo, are there any other solution for E3. I see that problem quite fun lol.
 » 3 weeks ago, # |   +1 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.Both are of time complexity of O(n*t) with different approach. You can follow whichever you like
•  » » 3 weeks ago, # ^ |   +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.
•  » » » 3 weeks ago, # ^ |   0 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.  List[] 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); } 
•  » » » 3 weeks ago, # ^ |   0 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)
•  » » » » 3 weeks ago, # ^ |   0 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.
 » 3 weeks ago, # | ← Rev. 2 →   0 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.