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

Автор VLamarca, история, 7 месяцев назад, По-английски

Today was the first day I successfully used Chat GPT in codeforces. To be very clear, chat gpt did not come up with the solution, I came up with it. I only used it to write the code for a specific annoying part that is well known. I should probably just have something like that in the lib. Here is the submission. I probably just saved a few minutes. I also had to adjust a few things like reading the input, writing an extra if, etc. But chat gpt successfully did what I asked for it in an optimal way.

This was the prompt I used for Chat GPT 4: “An array A of length n can be seen as a graph where i has a directed edge to A[i]. Each vertex has 1 outgoing edge. There are some cycles in the graph. I think the name is a cactus. Write a code in cpp where given A you list all the sizes of the cycles”

On another example, I also remember trying to use chat gpt to search for some advanced level math theorems, but I failed to find with it. I was looking for something like this Given 2n integers, prove there is always a subset of size n whose sum is multiple of n for this problem, but I failed.

Do people have other use cases for chat gpt in Competitive Programming? I assume the main one is just coding a few simple things faster, and probably more accurately then most people, but the problem solving ability is still not good enough for problems above Div3A or B (fortunately or unfortunately wink wink).

Полный текст и комментарии »

  • Проголосовать: нравится
  • +10
  • Проголосовать: не нравится

Автор VLamarca, история, 4 года назад, По-английски

Most people know that if you don't submit anything in a codeforces round, the round is not rated for you. So if you are taking too long to come up with a solution for problem A, maybe you should not submit anything at all. Should you hate on someone that has this strategy? No! Hate the game, not the player.

In past rounds, I believe that the number of participants in greatly correlated with the difficulty of problem A. Is that the kind of behavior we want to foster? Is it intended that the rating should be a metric of your skill only among the rounds that you want to participate? Or should it be a metric of your skill among all rounds?

So I humbly suggest that if you enter the round, it should be rated for you, even if you don't make any submissions. The registration phase could remain the same, not being definitive, but if you click enter in the round between the let's say the 20 minutes window, starting 10 minutes before the round, the round should be rated for you. And late registrations should be unrated, otherwise this proposal makes no sense, because you would be able to check the problems in an alt account and only register late in the round if you think that you will perform well. Maybe you should also be able to register in the round without it being rated for you, but you need to decide that before.

Let me know your opinions!

Полный текст и комментарии »

  • Проголосовать: нравится
  • -35
  • Проголосовать: не нравится

Автор VLamarca, история, 4 года назад, По-английски

Hi!

In an attempt to verify by myself if rating inflation is real, I will be participating virtually in this contest from 2015 in roughly 15 minutes (21h05 UTC-3). I invite you to do the same!

I will do this for the next few weeks, and maybe gather some statistics in the end.

UPD: Among 3 participants that I consider very trustworthy, the rating change was very small. (Around +10 for each one). The rating variation was estimated by looking at people with similar original rating that got similar ranking in the contest as well. So this very small sample indicates that rating inflation is negligible.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +65
  • Проголосовать: не нравится

Автор VLamarca, история, 5 лет назад, По-английски

Hi!

I think it would be interesting to be able to upvote or downvote contests in Gym so we could choose which ones to do based on that also. (Maybe only allow upvote and do not allow downvote because people might get triggered due to their bad performance and downvote for no reason, but this is open for debate I guess).

As an example this contest is... hmm... lets say not the best one I've done.

Problem C: statement makes no sense.

Problem H: A key requirement of the output is missing (that the first point to be printed should be the smallest one lexicographically — I was the one who answered that on the clarifications of the contest with my coach mode — there are still many unanswered clarifications).

Problem A: Mentions turning to the right or to the left instead of ccw or cw.

Problem E: Variables constraints are not mentioned and it says "The next T integer are" but it should be "The next N integer are". (Notice that is says integer instead of integers also haha).

There are many grammar mistakes which are not that relevant but indicate that authors did not reread the statement when translating.

Additional feature: While I am at it, I would like to suggest the feature of tracking down which contests a certain team has participated on CF. We can currently see which teams a certain person was a member from, but we cannot see in which contests this team has participated.

MikeMirzayanov, arsijo please consider this request :)

Thanks for reading

Полный текст и комментарии »

  • Проголосовать: нравится
  • +213
  • Проголосовать: не нравится

Автор VLamarca, история, 5 лет назад, По-английски

Hi,

regarding problem B from this contest, my solution using double gets TLE and the same solution using long double gets AC, anyone has any idea why?

You can use this test case in custom invocation to confirm that the solution using long double is indeed twice faster.

EDIT: I could pinpoint the problem and it is the mod member function that gets the norm of a vector using hypot(x,y), which is the same as sqrt(x*x+y*y) but with better precision. The solution with double gets accepted if I use double everywhere, casting to long double only here: hypot((long double)x,y) (code). Using sqrt(x*x+y*y) instead works too. Nonetheless it is still very strange that hypot function is faster when dealing with long double.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +23
  • Проголосовать: не нравится

Автор VLamarca, история, 6 лет назад, По-английски

Hi!

In this blog I would like to humbly suggest a change in how hacking is calculated in CF rounds. I've talked to some of my friends and they agree that it feels a little unfair that someone who solved more problems scores less than someone who hacked more. A great example from where this happens is from the top positions (and other positions too) in today's round: Codeforces Round #482 (Div. 2) .

I have two main suggestions on how to calculate hacking points in a way that I consider fairer. The specific way may vary, but the key points are:

1) The more you successfully hack a certain problem, the less you should score with it. This means that the first hack on problem A should get you 100 points, but the second 50, the third 25 and so on (or something like this, maybe keep 50 for all the following hacks starting with the second one). I feel that a decreasing function for this is fairer because, in most cases, when you hack a certain problem, it is easier to hack it again. It only depends on luck to have lots of people in your room that made the mistake you spotted. Notice that, in this suggestion, if you hack problem A one time and then problem B one time, both of them should get you 100 points each.

2) The harder the problem, the more you should score by hacking it. This means that hacking problem A should get you 100 points, and hacking problem B 150 points, or something like this. I feel that in most cases it is harder to hack harder problems because generally their solutions are longer and therefore harder to read. Also fewer people solve harder problems, so it makes sense to increase the value of hacking them to make it more attractive for people that did passed pretest for this problem to try to hack others' solutions.

I am happy to discuss ideas in this regard.

Thanks for reading! (Also if you spot any mistakes in my english I would appreciate to hear about them in my private talks :) )

Полный текст и комментарии »

  • Проголосовать: нравится
  • +258
  • Проголосовать: не нравится

Автор VLamarca, история, 6 лет назад, По-английски

Hi!

The main objective of my post is to make most Div. 2 only rounds rated for purle users.

This is beneficial because it would distinguish their rating better. It would also mean a more frequent participation for those people, which is good for the growth of the plataform. It makes no sense to make a purple coder wait for a Div. 1 round, which is rare due to the difficulty to come up with a Div1 D/E problem, when in most cases those users don't even read these harder problems at all.

Another reason is because most Div. 2 rounds are hard enough for people with purple rating. I assume the difficulty of contests should be sufficient to not transform them in a "type race", which means that it is good that few people solve all the problems. I will try to convince you that we can make div2 contests rated for people with higher rating without breaking this principle.

EDIT: Originally the title of this blog was "Please increase div2 upper rating limit" but this was missleading as I only want to allow div. 2 participation from purple guys in Div. 2 only contests. By Div. 2 only I mean the contests that do not have a corresponding Div. 1 rated problem set.

The distribution of participants in div. 2 and div. 1 (when there is a corresponding Div. 1 contest) could and should remain the same.

Some data to back my suggestion:

In Codeforces Round #476 (Div. 2 only) [Thanks, Telegram!] only 1 person solved all the problems officially, and I would say that more than 95% of all the unofficial purple contestants solved at most 4 out of the 5 problems.

In Codeforces Round #477 (rated, Div. 1, based on VK Cup 2018 Round 3), let's assume that the contestants who solved 4 problems would have a chance of solving all problems in the corresponding div. 2 round. Less than 50 (including red and yellow rated people) out of more than 450 div1 contestants solved at least 4 problems.

In Educational Codeforces Round 42 (Rated for Div. 2) only one red rated person solved all the problems and the vast majority of purple rated unofficial contestants could not solve 2 of the contests' problems. Also 3 legendary grand masters contestants could not solve all the problems.

With that being said I suggest that most div. 2 only contests should allow rated participation of users with rating up to 2200, or less depending on the difficulty of the specific round. But please do allow participation of more users in Div. 2 rounds when the difficulty is sufficient, this is healthy for the plataform!

I am open to discussing ideias in this regard.

Thanks for reading :)

Полный текст и комментарии »

  • Проголосовать: нравится
  • +351
  • Проголосовать: не нравится

Автор VLamarca, история, 7 лет назад, По-английски

I was getting WA on this problem, but after I suspect that the problem's statement might be wrong, I got AC with this code.

In a phrase of the problem statement it is said: "The state of objects that do not have any nested objects will be '-'.". From this I understood that when k = 0, s would necessarly be '-', but I then submitted this code, identical to the AC one, with one exception: if s = '+' and k = 0, then it would give TLE, which indeed happend but shouldn't.

Did I misinterpeted the statement or is the problem indeed wrong? In the latter case I will try to contact the author.

Thanks a lot in advance!

Полный текст и комментарии »

  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится

Автор VLamarca, история, 7 лет назад, По-английски

Hello!

My solution to this problem E implements the same ideia as the editorial. But first I used a O(m*n*lgn) solution here (for m=1000 and n=5000, which is ~6*10^7) that got TLE. I used map in this one which made it slower. Then I tried using map only in the beggining instead of using all the way in the code (as shown here). This means that first I mapped the string to the index that gives the element that the map would represent. Accessing the element this way is O(1), therefore the solution was O(m*n) which got accepted.

But shouldnt the 3 second limit be enough for less the 10^8 operations in the first solution? I though that 1 second meant 10^9 operations.

Sorry for the begginer's doubt. Possibly it's because I used many operations per iteration, but how should I know? what do you consider as the boundary, 10^7 per second?

PS: actually in the first solution the map is deleted and remade in every iteration, which means that its size is not always the maximun n, which is actually faster than what I considered in this post.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +13
  • Проголосовать: не нравится