Petr's blog

Helvetic Coding Contest 2024 Editorial
By Petr, history, 8 months ago, In English
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)
  • Vote: I like it
  • +76
  • Vote: I do not like it

»
8 months ago, # |
  Vote: I like it +25 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thank You

    → Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      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

      → Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Codeforces Helvetic Contest 2024

Detailed Video Tutorial B1 + B2 + B3

https://youtu.be/1s9NN3D3TWY

(Language => Hindi)

→ Reply
»
8 months ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
8 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          thank you!! I was not familiar with multiplying matrices, so was a bit confused at first..

          → Reply
»
8 months ago, # |
← Rev. 2   Vote: I like it +103 Vote: I do not like it

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)

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

    → Reply
  • »
    »
    8 months ago, # ^ |
    ← Rev. 2   Vote: I like it -61 Vote: I do not like it

    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)

    → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +73 Vote: I do not like it

      bro why are you too mad chill wtf

      → Reply
      • »
        »
        »
        »
        8 months ago, # ^ |
        ← Rev. 2   Vote: I like it +21 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +139 Vote: I do not like it

    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.

    → Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +63 Vote: I do not like it

    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.

    → Reply
»
8 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

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

    → Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    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.

    → Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    4 months ago, # ^ |
    ← Rev. 7   Vote: I like it +8 Vote: I do not like it

    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!

    → Reply
»
8 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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<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);
    }
      → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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)

      → Reply
      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
»
8 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply