DmitryGrigorev's blog

By DmitryGrigorev, history, 7 months ago, In English

Actually, the solution to the Grakn Forces F problem seems pretty easy, but somehow I didn't come up with the intended one. I wrote some solution making $$$O(n \cdot log^2(n))$$$ queries in the worst case, which I actually didn't even seriously suppose to pass.

After the contest, I run the stress and it turned out that the solution fails in plenty of tests (around $$$1000$$$ numbers specifically).

It would definitely be caught if the number of tests was greater. It seems that there are not more than $$$10$$$ tests that pretend to be random (except very small numbers and very large numbers that I tested by myself). So my question is — what is the reason for this number to be so small?

I believe that tests must distinguish proper solutions and some shit like this that works very sometimes if it's possible. I understand the point that sometimes it's hard to generate tests, but here we just needed to have only a sufficient number of random tests to hack my solution, but definitely more than $$$10$$$. Here I had ~$$$50$$$ % chance to pass these $$$10$$$ tests, that's what actually happened.

300iq, what is your opinion?

Read more »

 
 
 
 
  • Vote: I like it
  • +146
  • Vote: I do not like it

By DmitryGrigorev, history, 23 months ago, translation, In English

(Idea of the problem Div2A — ScreaMood)

(Developer of the problem Div2A — DmitryGrigorev)

Tutorial is loading...

Code

(Idea of the problem Div2B — MAMSURENOK)

(Developer of the problem Div2B — DmitryGrigorev)

Tutorial is loading...

Code

(Idea of the problem Div1A — Mr.Hakimov)

(Developer of the problem Div1A — Mr.Hakimov)

Tutorial is loading...

Code

(Idea of the problem Div1B — DmitryGrigorev)

(Developer of the problem Div1B — PeregudovSergey)

Tutorial is loading...

Code

(Idea of the problem Div1C — ----------)

(Developer of the problem Div1C — ----------)

Tutorial is loading...

Code

(Idea of the problem Div1D — DmitryGrigorev)

(Developers of the problem Div1D — ---------- и DmitryGrigorev)

Tutorial is loading...

Code

Read this comment of saketh about another approach for this problem.

(Idea of the problem Div1E — DmitryGrigorev)

(Developer of the problem Div1E — TheWayISteppedOutTheCar)

Tutorial is loading...

Code

Read more »

 
 
 
 
  • Vote: I like it
  • +105
  • Vote: I do not like it

By DmitryGrigorev, history, 23 months ago, translation, In English

Hi, Codeforces!

We are glad to invite you to take part in Codeforces Round #569 (Div. 1) and Codeforces Round #569 (Div. 2), which will be held on Friday, June 21, 2019, at 19:35. The round will be rated for all participants from both divisions.

Problems for the round have been proposed by Ivan ScreaMood Fedorov, Kyrill MAMSURENOK Bessonov, Mukhammadjon Mr.Hakimov Hakimov, Fedor ---------- Ushakov, Fedor Kuyan Kuyanov, and me, Dmitry DmitryGrigorev Grigoryev.

The round have been prepared by us, Dmitry DmitryGrigorev Grigoryev, Fedor ---------- Ushakov, Dmitry TheWayISteppedOutTheCar Piskalov and Mukhammadjon Mr.Hakimov Hakimov.

We'd like to give thanks to Ildar 300iq Gainullin for excellent coordination of the round, to Sooke Sooke Gnar, Xiuhan sunset Wang, Ziqian TLE Zhong, Junzhao FizzyDavid Yang, Jiaxuan samjia2000 Gao for testing and to Mike MikeMirzayanov Mirzayanov as well for his unbelievable Codeforces and Polygon platforms!

Participants in each division will be offered 5 problems and 2 hours to solve them. During the round, you will be helping pupils of one usual Moscow school. Score distribution will be announced, traditionally, closer to the start of the contest

Good luck!

UPD Score distribution for Div.2 is standart — 500-1000-1500-2000-2500

Score distribution for Div.1 — 500-1000-1500-1750-2250

UPD2

Thank you for your participation in the contest!

List of the winners of the contest:

Div.2

  1. PSMaoTheKingOfAzerbaijan

  2. atacan

  3. Shayan.Kashefi_A

  4. LiPro

  5. BrutBurger

Div.1

  1. Radewoosh

  2. ACRush

  3. ecnerwala

  4. mango_lassi

  5. neal

My frank congratulations to all the winners!

The editorial

Read more »

 
 
 
 
  • Vote: I like it
  • +529
  • Vote: I do not like it

By DmitryGrigorev, history, 2 years ago, In English

(Idea of the problem A — ----------)

Tutorial is loading...

Code

(Idea of the problem B — IbragiMMamilov)

Tutorial is loading...

Code

(Idea of the problem C — usertab34)

Tutorial is loading...

Code

(Idea of the problem D — Denisson)

Tutorial is loading...

Code

(Idea of the problem E — Ralsei)

Tutorial is loading...

Code

Read more »

 
 
 
 
  • Vote: I like it
  • +61
  • Vote: I do not like it

By DmitryGrigorev, history, 2 years ago, translation, In English

Hi, Codeforces!

I`m glad to invite everybody to the #546 Codeforces round, which will be held on Monday, March 11, 2019 at 19:35. The round will be rated for all participants from the second division (with rating below than 2100). As usually, we will be glad to see participants from the first division out of competition!

Problems for the round have been proposed by Fedor ---------- Ushakov, Stepan IbragiMMamilov Stepkin, Alexey usertab34 Roze, Denis Denisson Shpakovskij and Alexander Ralsei Gladkov.

The round have been prepared by us, Dmitry DmitryGrigorev Grigoryev, Fedor ---------- Ushakov, Semyon cookiedoth Savkin and Dmitry TheWayISteppedOutTheCar Piskalov.

We'd like to give thanks to Ildar 300iq Gainullin for excellent coordination of the round, Grigoriy vintage_Vlad_Makeev Reznikov, Alexey Aleks5d Upirvitsky and Mohammed mohammedehab2002 Ehab for testing and to Mike MikeMirzayanov Mirzayanov as well for his unbelievable Codeforces and Polygon platforms.

You will receive 5 problems and 2 hours for solving it. During the round you will be helping for an extraordinary girl Nastya, who is studying in an usual school in Byteland.

Score distribution will be announced, traditionally, closer to the start of the contest.

Please, read all the tasks. Good luck!

UPD Score distribution is standart — 500-1000-1500-2000-2500

We're looking forward your participation.

UPD2 Thank you for your participation in the contest!

List of the winners of the contest:

Div.2

  1. woookje

  2. 1021869

  3. stanislav.bezkorovainyi

  4. Hamzqq9

  5. ilyausmanov

Div.1 + Div.2

  1. kmjp

  2. step_by_step

  3. TangentDay

  4. ..vince

  5. hitman623

My frank congratulations for all the winners!

The editorial will be posted very soon. We apologize for delay.

UPD3

The editorial

Read more »

 
 
 
 
  • Vote: I like it
  • +454
  • Vote: I do not like it

By DmitryGrigorev, history, 3 years ago, In English

All the problems have been prepared by us, — DmitryGrigorev and ----------.

(Idea of the problem — DmitryGrigorev)

Tutorial is loading...

Code — 39423470

(Idea of the problem — GreenGrape)

Tutorial is loading...

Code — 39423481

(Idea of the problem — ----------)

Tutorial is loading...

Code — 39423497

(Idea of the problem — DmitryGrigorev)

Tutorial is loading...

(Idea of the problem — DmitryGrigorev)

Code — 39423501

Tutorial is loading...

Code of the solution I — 39423519

Code of the solution II — 39418926. Try to optimize :)

Thank you tfg for the idea and the code of the solution III. Very good job!

Code of the solution III — 39392321

Read more »

 
 
 
 
  • Vote: I like it
  • +130
  • Vote: I do not like it

By DmitryGrigorev, 3 years ago, translation, In English

Hi, Codeforces! I'm glad to invite everybody to the #489 Codeforces Round, which will be held as soon as tomorrow, on Monday, June 18, 2018 at 19:35. The round will be rated for all participants from the second division (with rating below than 2100). As usually, we will be glad to see participants from the first division out of competition!

Problems for the round have been invented and prepared by us, pupils of Moscow school №2007, Dmitry DmitryGrigorev Grigorev and Fedor ---------- Ushakov. We want to give thanks to Andrew GreenGrape Raiskiy for his aid in preparing and testing of the problems, to Ildar 300iq Gainullin and to AmirReza Arpa PoorAkhavan who have tested our problems too and to the coordinator Nikolay KAN Kalinin, since our sometimes strange and undeveloped ideas have become eventually the Codeforces round. Also, we say thank you to Mike MikeMirzayanov Mirzayanov for his unbelievable Codeforces and Polygon platforms.

You will receive 5 problems and 2 hours for solving it. During the round you will be helping for an extraordinary girl Nastya, who has been living in Byteland and sometimes receives very strange gifts for her birthday :).

Score distribution will be announced, traditionally, closer to the start of the contest.

We're holding our the first and, I hope, not the last round in Codeforces, so I hope a lot you will like our problems. Please, read all the problems. Anyway, I wish luck and high rating for all the participants!

I'm looking forward your participation.

UPD Score distribution is standart — 500-1000-1500-2000-2500

UPD2 Thank you for your participation in the contest! It's very-very pleasant for me if you like the problems, and I'm sorry if you don't :) I hope the next my contest will be even better, than this. Thank you for all!

List of the winners of the contest:

Div.2

  1. sminem

  2. NguoiHocTinLoai2

  3. YaKon4ick

  4. HanaElhami

  5. pajenegod

Div.1 + Div.2

  1. dotorya

  2. Benq

  3. anta

  4. sminem

  5. kevinsogo

My frank congratulations for all the winners!

UPD3

Editorial is here

Read more »

 
 
 
 
  • Vote: I like it
  • +405
  • Vote: I do not like it

By DmitryGrigorev, history, 4 years ago, translation, In English

Can anybody help me with this task: We have a tree with N verteces(N<=5*10^5). Each edge has got a length Li(Li<=1000). In each iteration we delete one(given) of un-deleted edges and we must tell the longest simple way in each of two resulting components and we doing it while all edges aren't deleted. Please, any ideas how to solve it?

Read more »

 
 
 
 
  • Vote: I like it
  • +19
  • Vote: I do not like it