Helvetic Coding Contest 2024 Editorial

»

2 недели назад, # |

+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

2 недели назад, # ^ |

← Rev. 2 →

0

Thank You

→ Ответить

»

Petr

2 недели назад, # ^ |

+8

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

→ Ответить

»

InfiniteStarlight

2 недели назад, # ^ |

+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

2 недели назад, # |

0

Codeforces Helvetic Contest 2024

Detailed Video Tutorial B1 + B2 + B3

https://youtu.be/1s9NN3D3TWY

(Language => Hindi)

→ Ответить

»

Petr

2 недели назад, # |

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

2 недели назад, # |

← Rev. 2 →

0

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

→ Ответить

»

SYUCT_blyat

13 дней назад, # ^ |

0

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

→ Ответить

»

nassjes

13 дней назад, # ^ |

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?

→ Ответить

»

redsto

13 дней назад, # ^ |

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.

→ Ответить

»

nassjes

13 дней назад, # ^ |

0

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

→ Ответить

»

Dominater069

2 недели назад, # |

← Rev. 2 →

+103

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)

→ Ответить

»

Pirate_King

2 недели назад, # ^ |

+30

→ Ответить

»

Dominater069

2 недели назад, # ^ |

← 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)

→ Ответить

»

jeremy_goku

13 дней назад, # ^ |

+73

bro why are you too mad chill wtf

→ Ответить

»

hashman

13 дней назад, # ^ |

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

→ Ответить

»

Dominater069

13 дней назад, # ^ |

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.

→ Ответить

»

Petr

13 дней назад, # ^ |

+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

13 дней назад, # ^ |

+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

13 дней назад, # |

← Rev. 2 →

0

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

→ Ответить

»

Petr

13 дней назад, # ^ |

+15

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

→ Ответить

»

UP84

13 дней назад, # |

0

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

→ Ответить

»

Petr

13 дней назад, # ^ |

+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

12 дней назад, # |

0

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

→ Ответить

»

Code_Mystique

12 дней назад, # |

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

12 дней назад, # ^ |

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

→ Ответить

»

dzhi

12 дней назад, # ^ |

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<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);
    }

→ Ответить

»

Monkey_d_Luffy-19834098

11 дней назад, # ^ |

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)

→ Ответить

»

dzhi

11 дней назад, # ^ |

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.

→ Ответить

»

theRealChainman

11 дней назад, # |

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

→ Ответить

№	Пользователь	Рейтинг
1	tourist	3690
2	jiangly	3647
3	Benq	3581
4	orzdevinwang	3570
5	Geothermal	3569
5	cnnfls_csy	3569
7	Radewoosh	3509
8	ecnerwala	3486
9	jqdai0815	3474
10	gyh20	3447

№	Пользователь	Вклад
1	maomao90	174
2	awoo	164
3	adamant	163
4	TheScrasse	159
5	nor	157
6	maroonrk	155
7	-is-this-fft-	152
8	Petr	146
8	orz	146
10	BledDest	145

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