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

Автор ch_egor, 6 лет назад, По-русски

Всем привет!

Сейчас проходит первый тур Открытой олимпиады школьников по программированию, а уже завтра состоится второй. Олимпиаду подготовила Московская методическая комиссия, известная вам также по Московской олимпиаде школьников по программированию, Московской командной олимпиаде и олимпиаде Мегаполисов (раунды 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516, 541, 545, 567, 583, 594, 622, 626, 657, 680, 704).

Открытая олимпиада составляется из самых интересных и сложных задач, которые были предложены многочисленным коллективом наших авторов, поэтому мы решили провести рейтинговый раунд Codeforces, который состоится 13.03.2021 12:05 (Московское время) и будет основан на задачах обоих туров олимпиады. В каждом дивизионе будет предложено 6 задач и 2 с половиной часа на их решение.

В связи с этим мы просим всех участников сообщества, участвующих в соревновании, проявить уважение к себе и другим участникам соревнования и не пытаться читерить никоим образом, в частности, выясняя задачи у участников соревнования в Москве. Если вы узнали какие-либо из задач Открытой олимпиады (участвуя в ней лично, от кого-то из участников или каким-либо иным образом), пожалуйста, не пишите раунд. Участников олимпиады мы просим воздержаться от публичного обсуждения задач. Любое нарушение правил выше будет являться поводом для дисквалификации.

Задачи соревнования были подготовлены Akulyat, KiKoS, wrg0ababd, budalnik, turist, alexX512 isaf27, ismagilov.code, DebNatkh, Siberian, Kaurker под руководством cdkrot, vintage_Vlad_Makeev, GlebsHP, Zlobober, meshanya, ch_egor, grphil, voidmax, Endagorion и Андреевой Елены Владимировны.

Спасибо adedalic и KAN за координацию раунда, перевод условий и подготовку задач для второго дивизиона, а так же MikeMirzayanov за системы codeforces и polygon, который использовался при подготовке задач этой олимпиады.

Также спасибо 4qqqq и Aleks5d за предоставление дополнительных задач, которые помогли составить (я надеюсь) сбалансированный проблемсет для раунда, и Um_nik за тестирование раунда!

Всем удачи!

Заранее сообщаем, что из-за проведения официального соревнования исходные коды других участников будут недоступны ещё час после окончания раунда.

UPD1:

Пожалуйста, не обсуждайте задачи публично до 15:30 по московскому времени.

Разбалловка для обоих дивизионов нестандартная:

  • div1: 750 — 750 — 1500 — 2000 — 2500 — 3000
  • div2: 500 — 1000 — 1750 — 1750 — 2500 — 3000

UPD2: Разбор

UPD3: Победители!

Div. 1:

  1. tourist
  2. jiangly
  3. maroonrk
  4. ecnerwala
  5. heuristica

Div. 2:

  1. 20I6wudi
  2. ShimaRin
  3. fengqiyuka
  4. gezlik
  5. b___
  • Проголосовать: нравится
  • -695
  • Проголосовать: не нравится

»
6 лет назад, скрыть # |
← Rev. 3  
Проголосовать: нравится +35 Проголосовать: не нравится

amazing fact:in the first few minutes after the announcement is published,the announcement‘s rating is negative(???

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +10 Проголосовать: не нравится

Есть табличка с текущими результатами?

  • »
    »
    6 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +10 Проголосовать: не нравится

    По понятным причинам, мы не можем публиковать результаты во время тура.

    Однако результаты первого тура сейчас опубликованы, вы можете их посмотреть на сайте олимпиады: olympiads.ru/zaoch

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +4 Проголосовать: не нравится

During the last contest, I performed really poorly, and I finally got a negative rating change. So I really hope I can do better this time.

I expect my rank<1000, to do this, maybe solving the first four problems are needed.

Hope everyone enjoy the fun of coding(and get a good result), stay Cheeki Breeki! >_<

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Wish I can get perfect ranking and rating change.

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +66 Проголосовать: не нравится

Really liked this point, We kindly ask all the community members that are going to participate in the competition to show sportsmanship by not trying to cheat in any manner . I think we should have this in each contest.

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +35 Проголосовать: не нравится

Notice the unusual start time!

»
6 лет назад, скрыть # |
 
Проголосовать: нравится -26 Проголосовать: не нравится

As a contestant, I want to become a tester :)

»
6 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится -91 Проголосовать: не нравится

As a contestant, I want to become a tester :) Why to many down votes

»
6 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится -23 Проголосовать: не нравится

We kindly ask all the community members that are going to participate in the competition to show sportsmanship by not trying to cheat in any manner, in particular, by trying to figure out problem statements from the onsite participants. If you end up knowing some of the problems of Moscow Open Olympiad (by participating in it, from some of the onsite contestants or in any other way), please do not participate in the round. We also ask onsite contestants to not discuss problems in public. Failure to comply with any of the rules above may result in a disqualification.

That's the point what I like. As for sure, fair competition is very important for a round or the competition will be meaningless.

btw, the time of this round is very great for Chinese users. I will partcipate in it and try my best solving problems. Good luck to all of the participants! :)

»
6 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +9 Проголосовать: не нравится

Amazing starting time. I can finally get rid of my regular 'drink coffee and have a stomachache during contest' cycle. Yay!

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

Change my opinion-Pacific time zone sucks for almost all types of schedule, either contests are 1AM in the night, or they are 6:30AM in the morning.

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +89 Проголосовать: не нравится

From the past few weeks the unusual timing became usual to us.

»
6 лет назад, скрыть # |
 
Проголосовать: нравится -40 Проголосовать: не нравится

Why are some contests held at different times than usual? I think the usual timing is right for everyone!

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +4 Проголосовать: не нравится

Olympiad rounds are challenging and fun!

»
6 лет назад, скрыть # |
 
Проголосовать: нравится -16 Проголосовать: не нравится

There are 22 writers in this contest. Can't believe it!!

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +14 Проголосовать: не нравится

I can bet this won't be an easy codeforces round. Expecting Div-2 to be Div-1.5 by the length of contest.

»
6 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +17 Проголосовать: не нравится

Your last 2 contests had weak pretests. Hoping for strong pretests this time.

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +19 Проголосовать: не нравится

Due to the official competition source codes of other participants will not be available for an hour after the end of the round.

This means that we cannot discuss the problems here or anywhere for one hour after the end of the round?

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

where are the "as a tester" comments!

»
6 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +18 Проголосовать: не нравится

Too many reds means too many problems to upsolve :v (to learn) !

»
6 лет назад, скрыть # |
 
Проголосовать: нравится -32 Проголосовать: не нравится

After see the author list and contest length. I am scaring about my rating :v

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +73 Проголосовать: не нравится

Um_nik's comment has been deleted!

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +37 Проголосовать: не нравится

В кои то веки на кодефорсесе срач в комментах, а корневой коммент потерли :(

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +2 Проголосовать: не нравится

Hope for strong pretests lol

»
6 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится -8 Проголосовать: не нравится

Hello, What about score table ch_egor? (before showing score table) thank you very much I get my Ans Now!(now)

»
6 лет назад, скрыть # |
 
Проголосовать: нравится -16 Проголосовать: не нравится

We kindly ask all the community members that are going to participate in the competition to show sportsmanship by not trying to cheat in any manner.

This is quite important I think, and I hope this will be added to all the announcements of the contests in the future.

I also hope that everyone will remember:

Due to the official competition source codes of other participants will not be available for an hour after the end of the round.

So please DO NOT discuss about the problems especially the solutions during the one hour after the contest is over. (It seemed that this happened last time.)

Hope for strong pretests, too!

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Due to the official competition source codes of other participants will not be available for an hour after the end of the round.

Does this mean we will not be allowed to discuss the problems for an hour after the end of the round? (If so, I think it should be written somewhere because right now it is not very clear.)

»
6 лет назад, скрыть # |
 
Проголосовать: нравится -8 Проголосовать: не нравится

Scoring distribution shows us that this contest will be HardForces

»
6 лет назад, скрыть # |
 
Проголосовать: нравится -28 Проголосовать: не нравится

2.5 hours for 6 problems!!!It tells about the difficulty level of the "Problemset".

»
6 лет назад, скрыть # |
 
Проголосовать: нравится -8 Проголосовать: не нравится

hope i will get positive delta this time

»
6 лет назад, скрыть # |
 
Проголосовать: нравится -41 Проголосовать: не нравится

hope this time i will get positive delta

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

How to register for this contest? Anyone please help

»
6 лет назад, скрыть # |
 
Проголосовать: нравится -26 Проголосовать: не нравится

Im outta here. Ratings go brrrrrrr

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +266 Проголосовать: не нравится

51jsms.

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +13 Проголосовать: не нравится

I liked the baiting in score distribution

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +55 Проголосовать: не нравится

Even those who couldn't solve A, solved C and most of them are green or newbie

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +15 Проголосовать: не нравится

Codeforces Round #707 (Div 1, Div 2)

Codeforces Round #707 (Div 0.5, Div 1.5)

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +61 Проголосовать: не нравится

Div 2A was just disgusting.

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +19 Проголосовать: не нравится

tourist be like: " Div1 D? Let me just solve E and F instead..."

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +35 Проголосовать: не нравится

don't know why but i feel lot of fst in problem C

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +223 Проголосовать: не нравится

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

100% have cheating in this contest.

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

this contest should be unrated

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +26 Проголосовать: не нравится

Using 30 minutes for reading A 10 times, and I still don't understand its statement now.

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +13 Проголосовать: не нравится

B was easier to solve and code compared to A in DIV 2

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +89 Проголосовать: не нравится

WTF, I think the correct contest duration is 2.5 days instead of 2.5 hours.

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

How to do C question?

»
6 лет назад, скрыть # |
 
Проголосовать: нравится -6 Проголосовать: не нравится

Very brainstorming and skillful contest.

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Shouldn't Div2.D run for lcm(n, m);?? then I used a map for freq-> index

»
6 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +61 Проголосовать: не нравится

Am I the only one who didn't notice that all $$$a_i$$$ and $$$b_i$$$ are distinct in Div1 B?

Even worse, the problem is solvable without that assumption, but my $$$O(n\ log\ ANS)$$$ implementation got TLE (thanks to the miserably tight constraints and time limits...). Spent the whole contest trying to optimise that code >_>

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +4 Проголосовать: не нравится

How to solve Question C?

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +16 Проголосовать: не нравится

Me after reading the D2A problem. Petr on Bad Problems

»
6 лет назад, скрыть # |
 
Проголосовать: нравится -8 Проголосовать: не нравится

Finally AC!!

submission

  • »
    »
    6 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +8 Проголосовать: не нравится

    It's so cool to keep trying to the end, But why did you spend 2 hours and 17 minutes on problem C? You could have solved problems A and B quickly

    • »
      »
      »
      6 лет назад, скрыть # ^ |
       
      Проголосовать: нравится +10 Проголосовать: не нравится

      Solving problems A and B will not help me anyway. I want to improve. Each time after the contest I regret that I can solve one more during the contest, but could not solve due to nervousness and lack of time. So, from now, I am planning to solve difficult problems first during the contest time. Starting 2 problems are just based on reading the problem, understanding it and then typing it (without much thinking). If you look at my rating graph, I reach around 1700 and then fall down, that too from more than 6-7 months maybe. I usually solve div 2 A B C and after the contest I realise that I could even solve D if I had time (or even if I had sufficient time then I don't know why negative thoughts come into my mind that i could not solve it). So, I just want to gain confidence that I can solve difficult problems in the contest time as well, and when I will gain confidence then I will start from the problem A.

»
6 лет назад, скрыть # |
← Rev. 3  
Проголосовать: нравится +36 Проголосовать: не нравится

Again this where bad problem statements for Div2.

A is nothing else than a complected problem statement, and the whole thing about the problem is understanding the text. This is, honestly, the worst kind of problems we can get. This is even worse than asking for some googleable formular or the like.

B needs at least a bit fantasy for implementation, but still the main part is understanding what the statement wants to tell us.

C is nice statement, but implementation needs (at least for me) a lot of edge-case searching. So, this problem was again like 5 minutes thinking, then 2 hours asking "What did I get wrong here?". That is good for educational contest.

Maybe the other problems where super creative, but 90% of the partitipants did not even read them.

Edit: And of course, E, F where to hard. No Div2 solved any of them.

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +88 Проголосовать: не нравится

Timelimits in B, C and D are a joke. Don't know about E, but looks hard too.

  • »
    »
    6 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +10 Проголосовать: не нравится

    Do you know what's the problem with GNU C++17 (64)? I noticed that you changed compiler to C++14 and got OK, and did the same, but there are some people who have OK with C++17.

  • »
    »
    6 лет назад, скрыть # ^ |
     
    Проголосовать: нравится -19 Проголосовать: не нравится

    You mean too low or too high? My solution for C ran in 1.2s and for B in 1.5s, I'd set both to 3s just to make sure but it's not that much different. D has plenty of reserve time, my solution runs in 1.7s.

    • »
      »
      »
      6 лет назад, скрыть # ^ |
       
      Проголосовать: нравится +2 Проголосовать: не нравится

      To low. In B and C I had hard time, both take more than a half of a time limit while being more or less optimal. In D I also had no problem (it's a miracle btw, I had $$$O(n^2 \cdot q \cdot \log(q))$$$), but I see many people in the standings having some TLEs, while I guess their solutions also have correct complexity.

      • »
        »
        »
        »
        6 лет назад, скрыть # ^ |
         
        Проголосовать: нравится -18 Проголосовать: не нравится

        Yeah, that log seems excessive. I can't see solutions but I expect a lot of overcomplicated shit in B, C and D since I almost fell into the trap of trying to bash out an ugly code for a nice idea several times during this contest.

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +72 Проголосовать: не нравится

Does anyone else think that after a certain point in the contest, the submissions for C grew exponentially? When I see the standings, I can see more pupil, newbies and specialist having AC when compared to blue, which is very weird. Not trying to be ratist but I've never seen this kind of acceptance rate for a problem like C.

»
6 лет назад, скрыть # |
 
Проголосовать: нравится -30 Проголосовать: не нравится

I hope I wasn't the only to solve Div2C/Div1A with NTT. Thanks to AtCoder Library I passed pretests in 1.6s out of 2 second. In general, AC library turned out very useful for me this contest as D2D/D1B required CRT, which is implemented there as well.

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

weak pretests on 1A/2C.

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

Is there a O(n) or O(nlogn) solution for C ?

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +28 Проголосовать: не нравится

cheatforces!

»
6 лет назад, скрыть # |
← Rev. 3  
Проголосовать: нравится 0 Проголосовать: не нравится

My reaction while reading prolem 2A was similar to https://www.youtube.com/watch?v=KNviwfDeRKg

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

когда разбор будет добавлен?

»
6 лет назад, скрыть # |
 
Проголосовать: нравится -14 Проголосовать: не нравится

Solved Div 1A using FFT, missed a silly observation.. how stupid I am.. :/

»
6 лет назад, скрыть # |
 
Проголосовать: нравится -6 Проголосовать: не нравится

Anyone noticed the weird constraint for the elements in Div2C?

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +26 Проголосовать: не нравится

And some interesting fact: you can pass Div2 C's pretest by just simple rand().

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +6 Проголосовать: не нравится

Thanks the organizers for this contest although I may suffer from a minus delta. At least it has given me the chance for a successful hack, which did not happen since June 2020 :-)

»
6 лет назад, скрыть # |
 
Проголосовать: нравится -9 Проголосовать: не нравится

How to slove TLE in problem 2 in div 2?

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +55 Проголосовать: не нравится

Will the system testing be done right now or an hour later?

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

Please do not discuss problems publicly until 12:30 UTC.

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +73 Проголосовать: не нравится

I think div1a should be easier or we should have open-then-rated system.I am pretty sure atleast a 200 people didn't submit anything because they couldn't solve anything in div1.

»
6 лет назад, скрыть # |
← Rev. 4  
Проголосовать: нравится +11 Проголосовать: не нравится

In today's contest something was weird ,In standing I saw many who has solve d2C but made wrong on d2A/d2B.....

And C was not that easy!? Or Do I missed any trick???

Yeah As I guessed Same question was available on gfg link

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +32 Проголосовать: не нравится

In D1B, I wrote int posa[500005],posb[500005] and used $$$posa[a_i],posb[b_i]$$$. However $$$a_i,b_i$$$ might be $$$10^6$$$! Despite this fact, this program with too small array bounds passed pretests. I really wonder how strong pretests are.

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I'm afraid of system testing

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Can somebody give me a hint on how to approach DIV-2 problem-C. I am totally clueless about how we can do it in less than O(n^2)

»
6 лет назад, скрыть # |
← Rev. 5  
Проголосовать: нравится -37 Проголосовать: не нравится

The initial problem scores seems too small for me.:(QAQ

I solved 2 problems but my score is smaller than some people with 1 problem.

Let's admire the great score setter.

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +9 Проголосовать: не нравится

I didn't like div2A, spent 15+ mins trying to understand the statement

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +16 Проголосовать: не нравится

Nice random scores on ACD.

D: easiest — in the same way as with 2D prefix sums, for each top left corner $$$(r,c)$$$ you just list "colour, smallest square for which we first see it" for the first $$$Q+1$$$ such colours; this list is created by merging the lists for squares with top left corners $$$(r+1,c)$$$, $$$(r,c+1)$$$, $$$(r+1,c+1)$$$ in linear time and that directly gives us the answers

B: alright, not trivial, not too hard, obvious binsearch and some number theory behind

A: Not The First Problem In The Contest Please! I solved it mainly by noting that if there are many different values (around $$$\sqrt{\max A_i}$$$), the answer always exists and we can ignore all except those few values to find it. Otherwise, there are some special cases — if there are 2 values that occur at least twice or one that occurs at least 4 times, the answer is obvious; if all values used in the sums are different, bruteforce works; and finally, there's the case $$$a+a=b+c$$$. It could be a 500-750pt A if it was just a yes/no problem and all values were guaranteed to be different, but this way, there are just way too many details to consider. Harder than B or D.

C: Nice problem, requires not getting bogged down in implementation even if you know the gist of what you want to check. The matrix A is almost irrelevant — we're splitting $$$B$$$ into chunks of rows. If there's an axis $$$a$$$ such that each chunk is increasing along that axis, and there's a chunk that contains at least 2 different values on that axis, we can "unsort" by $$$a$$$, splitting this chunk between rows that have different values on axis $$$a$$$. If we consider sorting instead of unsorting, in reverse order, we find that as long as the rows in each chunk are originally in the same order, we'll end up with $$$B$$$. Vice versa, any other unsorting means we'll never obtain $$$B$$$ since something would be sorted in a way we don't want. When there's no more splitting possible, we hash the rows and check if we can build $$$A$$$ by merging the chunks of rows we have at the end without changing the order in each chunk.

In implementation, it's essential to notice that the conditions "is increasing along axis" and "has at least 2 different values on axis" don't need to be checked for chunks, only for adjacent rows. We discard pairs of adjacent rows that are already in different chunks, and for each axis, we remember how many remaining pairs are strictly decreasing and which ones are strictly increasing. When splitting between two rows, we only update these conditions for this pair of adjacent rows and each axis, and this way, we only check each pair of vertically adjacent values once, leading to $$$O(NM \log)$$$ complexity.

There's also the question: can two identical rows end up in different chunks? If that happens, then there must be a split along some axis that had values $$$a, \ldots, b, c, \ldots, a$$$ in one chunk in $$$B$$$, where at least one of $$$b,c$$$ is different from $$$a$$$ and the split happens between rows with $$$b$$$ and $$$c$$$. However, the first time this happens, this chunk can't be increasing — the value among $$$b,c$$$ that's different from $$$a$$$ is either larger than the next $$$a$$$ or smaller than the previous $$$a$$$. That means the answer is no, all rows with the same value must be in the same chunk, and that greatly simplifies the final check with hashing — if we're adding a given row to the end of partially built matrix $$$A$$$, we know which chunk we must take it from.

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +75 Проголосовать: не нравится

My Div1C passed pretests even I typed n instead of m somewhere. It was so scary.

»
6 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +19 Проголосовать: не нравится

Dont we all agree that most of the C accepted submissions were from GeeksForGeeks!

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +18 Проголосовать: не нравится

Div1C can be solved with "bitset" in O(N^3/w)

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

Great problems, thanks!

»
6 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +115 Проголосовать: не нравится

Good contest with strong pretests, especially in problem B and problem C.

What's more, the tl of problem B and the ml of problem D are very friendly. No one can get TLE or MLE on them.

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Can somebody explain me in short how to solve DIV2 problem-C. I was very clueless about how to solve it in less than O(n^2)

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +22 Проголосовать: не нравится

TLE: https://codeforces.me/contest/1500/submission/109883422 AC: https://codeforces.me/contest/1500/submission/109892108

I resubmitted my TLE code during the contest and got an AC. Can anyone explain why? Can we rejudge? Sorry to disturb you.

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +52 Проголосовать: не нравится

My code with scanf can't pass div1 C, but it only takes 102ms after switching to fread. How could such thing happen on codeforces?

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

Hi, I had a query regarding my submission of the Div2(C) Going Home question. I had submitted two submissions for that question. My first submission got skipped and the second submission got accepted .The second was optimized solution as compared to first solution. But the first solution would have worked also because I had submitted the first submission again after the contest was over and got accepted. If my first solution was checked then I would have got much better rank. I would like to know more about why this happened?

  • »
    »
    6 лет назад, скрыть # ^ |
    ← Rev. 2  
    Проголосовать: нравится +9 Проголосовать: не нравится

    I am sorry to hear that. But it is because of the rule of Codeforces. Only your last submission to a problem will be considered as your valid submission. And if it gets AC, all your previous submissions will cost 50 points.

    If you want to know why it is designed in this way, let me explain in a deeper way.

    There are typically two types of competitive programming contests. One is judging real-time and the other is judging after contest ends. In a real-time judging contest, participants can try many times for a problem until they get AC.

    But in the other type of contests, participants must specify one submission as they final submission for each problem. Just like taking exams, you can not submit many answers to the teacher and say "Hey, please check all my answers. If one gets passed, then I get credit."

    Because Codeforces enables real-time testing, you may think Codeforces is the first type contests. However, in my opinion, Codeforces rounds are much more like the second type. Because it just does pretests during contests. Nobody knows the system test result until contest ends.

    So, in the next Codeforces round, please remember not to resubmit if you think you have given a correct answer.

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +12 Проголосовать: не нравится

It got TLE in contest DIV1 B https://codeforces.me/contest/1500/submission/109868976, but resubmitted got AC: https://codeforces.me/contest/1500/submission/109893896

Is this supposed to happens?

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Can somebody explain me why O(n^2) is accepted for n<=200000 in DIV-1A (DIV-2C)?

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +24 Проголосовать: не нравится

AC:https://codeforces.me/contest/1500/submission/109898116 TLE:https://codeforces.me/contest/1500/submission/109870735 It's the same Code. I submit it after the contest several times and all get accepted but got TLE during the contest...

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

My clean 30 Line code to DIv2 C. only based on pigeonhole principle. 109899822

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

int128 -> long long

TLE -> AC

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
  • Problem C — Uneven TCs? For some reasons, there are weak Test Cases. Testcases only contain N<1000 which is easily acceptable in N^2. Moreover, in a few test cases N=200000 but in those TCs the N^2 approach is getting completed in given time. This is somewhat unfair for those who don't submit the solution because of N^2 TLE reason. There may be other proofs that will prove that N^2 will never give TLE but thinking a general way, it won't.
»
6 лет назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

Your solution 109863008 for the problem 1501C significantly coincides with solutions shaw_off/109861748, rUnTiMe_TeRRORrr/109863008. 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. Here is the code that was published before this Competition as it was published before this competiton Contest -707 Div 2 Problem C **link to the contest -[](https://codeforces.me/contest/1501)** link — code avaialble on net link to my submission — [](https://codeforces.me/contest/1501/submission/109863008) please look MikeMirzayanov

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +10 Проголосовать: не нравится

109903632 109904857

I want to know why making the one which uses vector get Memory limit exceeded!

I think it is totally unnessary!

  • »
    »
    6 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    Not justifying the constraints of the problem or anything, but this is just one pitfall of std::vector. I agree that the problem didn't have a good memory limit anyway.

    Note that we say std::vector takes amortized $$$O(n)$$$ space. More precisely, when there are $$$n \gt 0$$$ elements, its internal capacity becomes $$$2^{\lceil \log_2 n \rceil}$$$, which in the worst case can be as large as $$$2n - 2$$$. This might have given the MLE verdict.

»
6 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

Problem 2C is pretty standard problem available on all coding tutorial websites including GFG.https://www.geeksforgeeks.org/find-four-elements-a-b-c-and-d-in-an-array-such-that-ab-cd/

@MikeMirzayanov

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

When will the rating changes finally be published?

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +29 Проголосовать: не нравится

Codeforces is now filled with idiots. Whenever they perform bad on contests, they blame the problem statements and writers

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +23 Проголосовать: не нравится

ASAS Isn't it?

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +130 Проголосовать: не нравится

I don't really think we should downvote this contest so heavily. It's true that many parts of the contest can be improved, but such downvoting is a disrespect to the authors and their contribution to the community.

  • »
    »
    6 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +12 Проголосовать: не нравится

    I do agree . They have done a lot of hardwork and downvoting so harshly is not fair .

  • »
    »
    6 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +28 Проголосовать: не нравится

    Even this contest wasn't bad.A,B were same as other rounds have.C have observation.And D was obvious binary search with some implementation.I don't know what people expect from cf.What people do is:if they performed bad,blame on authors.In todays contest atleast till Div2d didn't require any advance knowledge neither any advance math.

    • »
      »
      »
      6 лет назад, скрыть # ^ |
       
      Проголосовать: нравится +11 Проголосовать: не нравится

      Did you see the rest of div1 problems? I'm not sure that 2600 rating is normal for div1C. Or 2900 for div1D. Maybe I don't understand something, but these problems should be a bit easier.

      In fact, there were 2 more problems on the contest, that were as hard as div1F. IMO, the authors of the contest just overestimated the skill of the participants.

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Div2B can actually be directly simulated (of course compressing the sequences, e.g., 1 1 1 1 1 1 -> (6,1)). Since with compression on each iteration we insert only one element, no matter how many we have removed, and we remove only once, it is linear in N.

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +2 Проголосовать: не нравится

Был ли раунд рейтинговым? И если да, то когда рейтинг обновят?

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +4 Проголосовать: не нравится

Not submitted DIV 2.C O(n^2) solution with the fear of getting TLE. Could not find during the contest that sum cannot exceed 5*10^6.

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

hard contest

»
6 лет назад, скрыть # |
 
Проголосовать: нравится -19 Проголосовать: не нравится

Seriously

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

can anyone help me here why n^2 solution is passing?

  • »
    »
    6 лет назад, скрыть # ^ |
    ← Rev. 3  
    Проголосовать: нравится +3 Проголосовать: не нравится
    • The minimum pair sum is $$$1 + 1 = 2$$$
    • The maximum pair sum is $$$2.5 \times 10^6 + 2.5 \times 10^6 = 5 \times 10^6$$$
    • Total number of pairs when $$$n = 200000$$$ is $$$\frac{n \times (n - 1)}{2} = 19999900000$$$ which is roughly $$$10^{10}$$$
    • Now according to the pigeon hole principle after at most $$$5 \times 10^6$$$ unique sums it will hit again one of those unique sums and only then you can stop your nested loop and and print the result.
    • So half way through the $$$O(n^2)$$$ you definitely find the answer and you can terminate there so the $$$O(n^2)$$$ solution will need to run at most $$$5 \times 10^6 + 1$$$ iteration to find the answer.
    • »
      »
      »
      6 лет назад, скрыть # ^ |
       
      Проголосовать: нравится +1 Проголосовать: не нравится

      What about the differences:

      $$$x+y=z+w$$$
      $$$x-w=z-y$$$

      Note that for the differences we can switch the sign, so we can use the absolute value.

    • »
      »
      »
      6 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

      "So half way through the O(n2) you definitely find the answer and you can terminate there so the O(n2) solution will need to run at most 5×106+1 iteration to find the answer."

      But what if we don't find an answer, then the loop will run O(n^2) times (right?), would that not be TLE?

      • »
        »
        »
        »
        6 лет назад, скрыть # ^ |
         
        Проголосовать: нравится +1 Проголосовать: не нравится

        There is some possibility that we won't find answers for cases where n^2 < 2.5*10^6 but for cases of n^2 > 2.5*10^6 (we may need few more numbers because of some collisions in the chosen indices) we are bound to find an answer. I hope this clears your doubt :)

      • »
        »
        »
        »
        6 лет назад, скрыть # ^ |
         
        Проголосовать: нравится 0 Проголосовать: не нравится

        It is guaranteed to have an answer when is $$$n$$$ is roughly $$$\ge 4000$$$ (Pigeon Hole Principle)

        Let me demonstrate that:

        We only have $$$7$$$ days a week sat through Fri.

        If I ask you to name the names of 8 days, at some point it is guaranteed to name some day twice or more.

        With that, let us go back to the problem, we only have $$$2$$$ through $$$5 \times 10^6$$$ possible pair sums (Holes), Now when you run your nested loop you are going to generate sums more than the number of holes that you have, and so you are gonna have pairs with repeating sums.

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Is this round rated?

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

In Div2 C, I used an intuitive approach to solve that worked. Basically, I iterated over differences (ax — az) from 0 to k*C/N, where C = 2.5*10^6, N is the input size, and k is some constant (say 2) and then I checked whether four such indices exist or not. My question is how to prove that only checking first k*C/N differences works? Also, what is the tight lower bound for such k?

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +10 Проголосовать: не нравится

When will the rating be updated, if you don't mind me asking?

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +2 Проголосовать: не нравится

Is the round unrated now ?? I can't see any rating changes in my profile or any one else

Thank you in advance

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Was this contest rated

  • »
    »
    6 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +6 Проголосовать: не нравится

    If anyone noticed,contest final standings had been continuously changing yesterday in a span of every 2 hours albeit by a small margin of 2-3 yet ratings hadn't been updated and no info about contest being unrated had been published by the contest setters.

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Why hasn't the round's rating been calculated?

»
6 лет назад, скрыть # |
 
Проголосовать: нравится -68 Проголосовать: не нравится

As a contestant, I think that if you want to hold a contest on CF, you should provide the best problems and sincerity to contestants. A good round should have novel ideas, strong data, and amazing solutions, instead of old problems, cumbersome details, and bad pretests. As we all know, contestants would be sad if they solved a problem but got failed on system test instead of accepted because of small detail. Isn't it? :)

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

was this round unrated ??

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +34 Проголосовать: не нравится

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Why is this round unrated

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

when will they release ratings?

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

when will the ratings for this round be published?

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +12 Проголосовать: не нравится

Hope this round will not unrated.

»
6 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +6 Проголосовать: не нравится

,

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
  • »
    »
    6 лет назад, скрыть # ^ |
    ← Rev. 2  
    Проголосовать: нравится +2 Проголосовать: не нравится

    TL I made a small modification to your code, it passes #73, but it failed #74. Now replacing unordered map with array passes the limit, AC. Second code is runner up's C code. What is the reason for this?

    • »
      »
      »
      6 лет назад, скрыть # ^ |
       
      Проголосовать: нравится +1 Проголосовать: не нравится

      I was thinking that it was getting TLE because my map was getting updated each time and for that it needs more iteraton but after seeing your modification I have realised that my thought was wrong. But I have seen many contestants did it in similar way but got no TLE. Didn't find any dissisimilarity. If anybody knows the reason behind this TLE please tell me.

      • »
        »
        »
        »
        6 лет назад, скрыть # ^ |
         
        Проголосовать: нравится 0 Проголосовать: не нравится

        Do you mean, similar unordered-map type solutions passed?

      • »
        »
        »
        »
        6 лет назад, скрыть # ^ |
        ← Rev. 3  
        Проголосовать: нравится +1 Проголосовать: не нравится

        I think why your code gives TLE(not sure) is the code just stores one instance of a pair, but in the editorial, it mentioned we have to store all four instances of pairs and if we get to such a position we can break, by printing appropriate indices, but the code is not intended to do that, that is the reason for TLE(the test case 73 and 74 are specially made for this purpose like it has first 535 elements which have unique sum for each i belonging to N) so basically we get to near $$$1.07*10^8$$$ operations. But, it is evident that vector passes, I suspect that it is due to cache friendliness nature of vector(not sure). Like, I may quote one instance, in the last topcoder SRM 801, div 2 hard question, map solution was supposed to pass with the given complexity, but it didn't whereas it vector counterpart passed(although it is faster by a $$$logn$$$ factor), Click I am not able to come up with any other reason for this behaviour. Please correct me if I am wrong.

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

Why the div2 of the contest is unrated? Or the rating changes haven't been figured out yet?

»
6 лет назад, скрыть # |
 
Проголосовать: нравится -10 Проголосовать: не нравится

This round should be unrated...I found a guy who just copy pasted from geeksforgeeks and did a little bit modification and got AC ...he didn't even try to write his own code...you can see in his submission....function name and code ,even comment is exactly same as geeksforgeeks...

https://codeforces.me/problemset/submission/1501/109870879

https://www.geeksforgeeks.org/find-four-elements-a-b-c-and-d-in-an-array-such-that-ab-cd/

I found just one guy and don't know how many have done the same thing ...

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Hope it will be rated :)

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Why the ratings of Div2 doesn't change ?

»
6 лет назад, скрыть # |
← Rev. 3  
Проголосовать: нравится -9 Проголосовать: не нравится

hey MikeMirzayanov sir , can u pls tell when will rating updated for contest-707 div2 its upto 18 hour from contest ends

»
6 лет назад, скрыть # |
← Rev. 3  
Проголосовать: нравится +2 Проголосовать: не нравится

I think they did not update ratings because, now for div2-C O(n^2logn) solutions are not working and giving tle on 73th testcase which were accepted before.

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

when do we have rating score?

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +23 Проголосовать: не нравится

This is entirely my fault — it's even bolded! — but did anyone else miss the key condition "elements are distinct" for D2D/D1B? I only realised just now when reading a code that was identical to my own solution...

»
6 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +5 Проголосовать: не нравится

Ratings have been updated now.
Thank you !

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

congratulation to all cheater who copied code from the internet and get high rating change. congratulation congratulation !!!

»
6 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +3 Проголосовать: не нравится

Many codes of Div 2 C which passed during the system tests are now giving TLE on test case 73 and 74, and still, they have got points. So isn't this unfair with the people who didn't submit that knowing that it will give TLE?

Eg: Submission C

»
6 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится -9 Проголосовать: не нравится

.

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +15 Проголосовать: не нравится

I participated in Div.1 and I'm upsolving the Div.2 easy problems.

WTF is this shitty Div.2 A????

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Can someone please help me understand why O(n square) logic works for the Div2 C problem? The limits for n are (10 to power 5) so it should ideally give TLE for a N square logic according to me

problem link: https://codeforces.me/contest/1501/problem/C

Solution link: https://codeforces.me/contest/1501/submission/110046641

Thanks in advance

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Can somebody please tell me why my code:110064321 TLEs in Div.2D and any possible optimization I can do? Thanks.

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

The constraints are wrong on 1B. Says colors are greater than or equal to 1, but in the tests they can in fact be 0. Had fun debugging that -_-...

»
4 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

[submission:Prblem : Div1 A] I just don't know why this submission is passing div1 A , like n <= 2*(10^5) , so this algorithm is of O(n^2) but it still passes because there is no test case with greater n and having a no answer, I don't know if its just a fluke or some sort of blurry idea behind this which i can't see.