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

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

I spent some time today working on a system to identify similar problems along the lines of https://codeforces.me/blog/entry/113064. For testing, it would be nice to have a list of duplicate (or close to duplicate, "one simple transformation" away, etc.) problems on Codeforces. The only pair I am currently aware of is (1793F - Rebrending, 765F - Souvenirs), so any others would help. Thanks!

EDIT: Just to be clear, I'm not interested only in strict duplicates, but also problems that share some important subtask, observation, or pairs in which one problem is a generalization of the other. And not asking for anyone to put any work into this, just thought some people might have pairs that come immediately to mind :)

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

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

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

I am these days a very irregular Codeforces visitor, but yesterday saw the post About Problem Coincidences by MikeMirzayanov and was wondering about a solution along the lines of a problem database like what was suggested some time ago by Um_nik. Lots of the comments there mention the idea of constructing a notion of problem similarity using solutions, which seems reasonable, but others countered that they don't want to have to write a whole solution just to tell if a similar problem exists. Given the current state of AI, could something like the following work now or in the near future?

  1. For every problem statement in the CF, AtCoder, etc. universe, use AlphaCode or the editorial to get a solution.
  2. Embed each of these solutions into a vector space. AFAIK this is straightforward to do.

Then when someone wants to see the most similar problems to their proposed statement, they either write a solution, or just write a statement and behind the scenes the database can have AlphaCode (or similar) generate a solution, embed using same method as in 2. and query for nearest vectors in the space. AlphaCode can't solve all problems, but maybe it at least writes something that "approximates" a correct solution well enough that the resulting vector is close to the "correct" one?

Of course, AlphaCode itself is not available to the public, but probably it or something similar will be soon. Thoughts?

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

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

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

I want to share with everyone a happy story today. Two years ago I supported Codeforces on its 10-year anniversary. Codeforces and its community have been tremendous blessings in my life, so I wanted to give back. Also, I wanted a t-shirt.

Sadly, my gift package was lost to the sands of time (and space), and it seemed that I would never receive it. I messaged some Codeforces admins to ask if there was any way to get a replacement, but alas there were few replies :( understandable, since they are quite busy with similar (and more important) requests I am sure.

However, I really wanted my shirt, and so periodically when I logged onto Codeforces I would ping these people again. There was some conversation, but really nothing every came of it. That is, until two months ago, when I got a promising reply from geranazavr555. Long story short, after a couple of messages back-and-forth with Una_Shem, I found out that they had tried to re-send my gift a second time, but again it was lost. However, Una_Shem graciously offered to try once more, and I want to report today that the package has arrived.

Me with my certificate and t-shirt.

Here's to ten (er, eight) more years! Thank you to everyone who helped and who keeps Codeforces going. A special thanks as well to MikeMirzayanov for great Codeforces and Polygon platforms.

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

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

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

After competing today in Codeforces Round 620 (Div. 2), I received the following message from System:

Attention!

Your solution 71152328 for the problem 1304E significantly coincides with solutions ksun48/71134293, hoke_t/71152328, Venia/71156816, hanga97/71159069. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.me/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

Clearly, these are all due to using the data structure LCA from the well-known KACTL library maintained largely by simonlindholm, Chilli, and many others, and was published online well before the beginning of the round (check the Git commit history). You can see that aryanc403, a tester for Codeforces Round 620 (Div. 2), used the exact same LCA code as well (71170167). MikeMirzayanov, can you please look at this incident and correct it by putting all of us back on the leaderboard and giving rating change? I had over +100 delta in the contest, and it's frankly quite disappointing that the system doesn't have a way to notice that such commonly used templates are not cheating (especially if round tester uses it too). I hope my monetary contribution to Codeforces this year can help prevent such incidents in the future.

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

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