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

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

This round is in memory of Leopoldo Taravilse.

Leopoldo Taravilse (ltaravilse) was a distinguished member of the competitive programming community in Argentina and Latin America. As a contestant, he reached the ACM-ICPC World Finals in 2010 and 2012, and was active in CodeForces and TopCoder. After 2012 he became a problemsetter for the ACM-ICPC South American regionals and the Argentinian Programming Tournament, and later coach for a World Finalist team in 2016.

Leopoldo's passion was helping others realize their full potential in competitive programming. He taught at various competitive programming schools in Brazil, Cuba, Peru and Bolivia, and his role organizing the Argentinian Training Camp cannot be overstated. Under his wing, it grew from a small group of friends in 2010 to a major event featuring international sponsors and having hundreds of participants coming from all corners of Latin America. Through successive editions of the Training Camp, Leopoldo inspired students to learn and improve, to give back to the community, and to have fun doing it.

With his intelligence, warm heart, relentless work ethics and witty sense of humour Leopoldo touched countless lives. We will miss him as a friend, a mentor, a teammate, a drinking buddy, a role model, an overall great person.

Rest in peace my dear Leo.

You can see this blog: A round in the name of ltaravilse.

And you can donate for prizes of this round: In Memory of Leopoldo Taravilse.


Hello everyone!

I'm pleased to announce: Codeforces Round #502!

This round will take place on Aug/08/2018 17:05 (Moscow time). It is rated for all participants and everyone will have 8 problems and 2 hours 15 minutes to solve them.

The contest is created by Magolor. This is the first competition I proposed. I hope that you will enjoy it. The heroes are from a TV show that I like and do not have any relation to Leopoldo.

6 of the 8 problems are created by myself. Thanks to:

  • ODT for inspiring me and discussing the problems with me.
  • Anton arsijo Tsypko for examining my problems, helping me a lot on this contest and designing problems B and G.
  • Max MaxZubec Zub, Danya danya.smelskiy Smelskiy, Sofia Sonechko Melnyk, Stanislav stanislav.bezkorovainyi Bezkorovainiy, Vitaliy kuviman Kudasov, Aleksandr Kostroma Ostanin, for testing the round and improving the problems and solutions.
  • Mike MikeMirzayanov Mirzayanov for Codeforces, Polygon and the help he offered to me.
  • Nikolay KAN Kalinin for helping with the contest and designing problem G.
  • Ahmed ahmed_aly Aly for his initiative to host this round in memory of Leopoldo.

...Yet Another Chinese Round...?

Scoring distribution: 500-1000-1500-1500-2000-2500-3000-3250.

Prizes distribution: $153 for top 30, delivered using bitcoin or amazon gift card (each contestant chooses).

UPD1: Chinese Editorial is published. You can view it through This link. English Editorial well be published soon.

UPD2: Congratulation to winners!

  1. Benq

  2. 000000

  3. webmaster

  4. Swistakk

  5. orbitingflea

  6. ivan100sic

  7. ko_osaga

  8. dreamoon_love_AA

  9. TLE

10.step_by_step

UPD3: English Editorial is published.

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

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

Prize distribution, wow

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

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

"После 2012 года он стал проблемой для южноамериканских регионов ACM-ICPC и аргентинского турнира по программированию" Спасибо, гугл перевод

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

It is really sad that such great people pass away...

I have a suggestion. In several countries, there's a tradition called "moment of silence". Generally, it is a minute of silence during some important events as a gesture of respect. Can we all agree, as the community, that we won't submit anything during some particular minute during the contest?

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится -47 Проголосовать: не нравится

    'moment of silence' cannot be done by no submission for some time during the contest.

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

    With all my respect, I doubt this will be appropriate.

    A moment of silence is a period of silent contemplation, prayer, reflection, or meditation.

    If it's really meant for contemplation, reflection, etc, I would rather skip contest at all because you have to be in rather different emotional conditions during competition and during moment of silence. Switching between them forth and back in such a small time span seems both unrealistic and disrespectful.

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

      Just a suggestion, if it can be done like in football matches. A minute of silence before the contest begins? Maybe the problem statements are displayed a minute late and the round is of duration 2:14.

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

      I still think that would be appropriate, but looking at all comments below, I have changed my mind that would be a good idea. Nevermind.

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

    rated&bitcoin i don't think that could happen, naturally server will be down for more than 1 minute don't worry.., btw i got your point!

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

    Now everybody knows this was a bad idea. :(

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

    i think the hardware of codeforces servers agreed with your opinion and made a few minutes of silence by their selves, even though it was not the thing that everyone wanted...

    R.I.P leo...

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

Finally, Div.1+Div.2 combined round!

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

Auto comment: topic has been updated by Magolor (previous revision, new revision, compare).

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

null

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

Upvote if you are waiting new problems from Taravilse

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

WOW!

The contest is made by a middle-school student

Chinese ??

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

    You f***ing racist f*ck. I bet you're white. Stupid white trash

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

      Sincerely, i wasn't racist at all. I was showing my respect to Chinese students because they are clever and prodigious.

      So,please never judge a comment directly without dissecting its real meaning

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

    It's surprising but normal :D In China, even primary school students can set up a contest add you can find them on some OJs. Show my respect to those 'dalao' OIers. orz

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

    It is actually a junior-high school (still very impressive). See Wikipedia.

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

ooh. good. finally a combined round. so awesome people like me can really show my skills. I really should not be on Div 2. These losers man.....

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

Rest in Peace Leopoldo ltaravilse Taravilse!!

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

I'm glad to find the Chinese contest again. However,I'm sadder after noting the first part of this article and hearing that such a great person left.

Hope the contest can be hold successfully.

And hope Leopoldo rests in peace.

I can't speak English very well,please forgive me.

(So I hope that the description of the problems can be concise.)

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

Sometimes I feel like this life has just been cruel, to make people, whom others love, pass away at such early ages...

Too bad, never had a chance to know him or work with him before. Still, rest in peace, friend...

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

2 hours and 15 minutes for 8 problems? That's quite challenging! :D

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

Does "Chinese round" mean wrote by Chinese or wrote in Chinese? If it is the latter, it will save a lot of time to understand the problems for the Chinese. By the way, I'm also looking forward to the Chinese editorial .

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

I am sorry to hear that a great man passed away.

In this round, it is more important to remember such a great man than to compete with others.

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

IOI is comming, we lost a great man!

R.I.P. ltaravilse

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

Auto comment: topic has been updated by Magolor (previous revision, new revision, compare).

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

if (Div1 && Div2 && prize) {

combine (Div1 + Div2);

}

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

Mathforces?

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

Why did CF merges Div1 and Div2 ??

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

Really sorry for the loss :( May his soul rest in peace.... A great thing to honor him.....to which he dedicated his life most!!

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

I will be part of this round just for you Leo(Been inactive for two yrs ), for all the things you teach us at the very beginning.

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

Leopoldo was our coach. I met him first in 2005. We were Latinoamerican Champions in the ACM-ICPC World Finals in 2016. We had spoken 6 hours before he had the accident. So sad :(.

Thanks for making this round

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

Rest in peace brother.

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

Good that this Leopoldo Taravilse died. He is a piece of shit!

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

    Why do you have to be toxic in every posts?

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

    If he is then what kind of useless stuff are you?Everyone has no permission to look down at such a great man.

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

    How can you say something like this for someone who has passed away? You are such a pathetic and disgusting person!

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

Is It Semirated?

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

Div1 + Div2 combined? My rating would be as dead as leopoldo now.

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

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

Wish Leo a peaceful rest and Magolor a great debut.

(Too sad GoFundMe doesn't accept PayPal for personal campaigns)

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

А что с ним случилось (может быть это где-то написано в посте, но у меня с английским беда)? UPD: То, что он умер — это понятно. Из-за чего это произошло?

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

Auto comment: topic has been updated by Magolor (previous revision, new revision, compare).

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

such people.... they have always inspired us by there great patience and fresh minds , a round is a great respect for soul that loved and lived its career sincerely , thnx guys for that great work and hope the best for every real worker like ltaravilse

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

Auto comment: topic has been updated by Magolor (previous revision, new revision, compare).

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

C and D have the same scores? Does it mean the difficulty will be similar?

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

it will be great that contest starts 10 mins later so i could participare in it from the start

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

Please, no delay

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

Auto comment: topic has been updated by Magolor (previous revision, new revision, compare).

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

Round 502 and Error 502

Coincidence? I think not.

Contest should be unrated imo. It's a pity since the problem-set is nice :(

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

Is it just me or Codeforces is heavily lagging ?

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

looooooool what just happend !!!

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

Ребята, привет! Давайте не будем омрачать данный раунд, а получим от него удовольствие, ведь этот раунд в честь Леонарда...

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

It's been a long time since the unrated round. That day has come!

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

Looks like both Leopoldo Taravilse and Codeforces servers passed away, RIP :(

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

It’s a pity to be unrated.

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

Unrated! Goodbye.

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

Please, sorry to the issue. One of our subsystems failed completely unexpectedly. It was internal assertion failed in https://github.com/greg7mdp/sparsepp (Assertion num_deleted failed). We are investigating the issue. It was the first time ever this subsystems failed with such message.

The round is unrated and the prizes are postponed to be awarded in some of the next rounds.

Sorry again. I apologize to problem writer Magolor, the coordinators and everyone who helped prepare the round. You did a great and good job.

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

    Unfortunate that this happened. As always, thanks for your hard work on the platform.

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

    You should not make such announcements in the middle of the round (no matter how obvious it is that it will be unrated) because it just instantly kills everyone's motivation to continue with the contest.

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

      I think he did the right thing, it would have caused a lot of confusion had he not announced it. Those people who 'lost the motivation' would have felt worse after realising their time was wasted.

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

      However, tried your best but get nothing is also bad.

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

      Yeah, rated contest just bring out some kind of weird adrenaline and motivation. to solve problems.

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

      But what would Benq fill, if he found out that it is unrated after the contest? He took 1st rank, and he needs only 26 rating points to become a LGM!

      P.S. Benq, I believe you will do it next time :)

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

A sudden notice of unrated makes me full-body relaxed.XD

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

Magolor you struggled a lot to make this round happen and it's unrated now,i am really sad for this

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

So bad ToT

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

 Read the text carefully! Available

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

Anyway,these problems are really high-quality. Many thanks for these amazing problems.

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

The website became "502" during Codeforces Round 502 :P

The problems in this round is fantastic anyway :D

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

How to solve the D problem? I could think nothing but tries.

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

Such a nice contest in memory of the great person with interesting problems and prize distribution, ...and unrated =(

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

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

Sad :(

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

I liked problem D, but no comment for B and C

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

I think unrated is fair to all participants . but is not to the author and coordinators .

They spent lot of time on this contest but their work does not paid off.

I can understand that there does not exist a solution which is fair to everyone . And I know the sudden fail is not anybody's fault .

Hope there won't be next time . And I think the author needs to be compensated , if could .

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

9141 participants we don't see this every day

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

How to solve C :

  1. Participate in atcoder regular contest 91 (pretty recent contest).

  2. Participate in round #502.

  3. Copy-paste the solution from ARC91_E.

  4. Add 2-3 lines and submit the code before the server goes down.

  5. PROFIT !!! (actually not, it’s unrated xp)

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

How to solve D ??

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

    Hint: There are at most 4096 different strings, and k is between 0 and 100.

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

    make a mask for every string in the original multi-set and keep track of occurrence of every such mask, then brute force for every possible pair of masks where 0 <= mask <= 2^n what is the resulting cost for this pair, from this loop you can keep track for every mask m what is total number of strings s in the original multi-set such that cost of m with the mask representing s is at least k where 0 <= k <= 100 using cumulative sum. then every query can be answered in O(1).

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

    You'll need to preprocess queries to answer them in O(1).

    First, let's mantain a set S for each different string (stored as an integer bitmask) and a frequency array, we don't need to use a STL set, because a vector (or array) and the frequency array will help us to avoid double counting.

    Then, we will have a matrix ans[M][K] that will contain the number of strings in the set that has Wu value with string M (bitmask) at most K, so we will use preffix sums to process them after. What we'll do now is brute force the mask M and use our "set" to compute the Wu values and do something like this (pos is the number of different strings stored in array v):

    for mask=0 to 2^n - 1:
       for i=0 to pos-1:
          act = 0
          for k=0 to n-1:
             if (mask>>k)&1 == (v[i]>>k)&1: act += w[k]
          ans[mask][act] += frequency[v[i]]
       for wu = 1 to 100:
          ans[mask][wu] += ans[mask][wu-1]
    

    With that you can answer queries in O(1) with a preprocess of O(n2nmin(2n, m) + K2n)). Where K is the max value of k.

    Note: Try to use I/O that can make it on time, maybe scanf or getchar since the lengths are fixed. :D

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

2 minute silence for Top 30 people !! :)

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

D in custom invocation, no input, n=12,m=q=500000,all strings="111111111111", all queries="111111111111 100", all answers=500000: about 700 ms.

D with scanf: about 1700 ms.

D with cin+ios_base::sync_with_stdio(0): TLE.

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

Sad to know that the round is unrated. But, anyway, I really enjoyed these high-quality problems.

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

How to solve F?

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

The problems are nice, but those statements are just horribly confusing. Take an example (problem E):

Then, this procedure will be repeated again with all new and old power sources.

Repeated how many times? The most natural way to read this without considering the impact on problem difficulty is: repeated once.

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

    Incidentally, the Russian translation says "repeated once" more clearly ("ещё раз", "once more").

    Of course I agree that the statements as a whole, and this particular part, could have been better.

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

Don't know about others, but with all the tricks, problem D is just straight brutal in terms of thinking imo.

Not something too hard to implement after you got everything, but to reach that state is another story...

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

    What was you solution to D? I thought it was straight-forward k*n * 2^n precomp and O(1) answers to queries.

    Of course, I did not implement in contest because i left after the server crash ( ͡° ͜ʖ ͡°)

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

      Well, my idea is pretty much the same — pre-processing offline then O(1) to queries.

      But that processing part was straight deadly. Even O(22n * n) didn't fit in TL for me.

      At the near end I realized 0 ≤ k ≤ 100 (yeah, screw me), and changed the processing method to such with complexity of O(2n * 100).

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

        What was your 2^2n * n idea, I only thought of the one that relies on small K.

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

          Literally, I tried through all pair of distinct strings (masked to integers for simplicity), and calculated that for each pair, what would the Wu value for that pair is.

          After calculating everything, I sorted the values, then start handling prefix sums.

          The queries would be O(log(2n)) due to binary search though, but that part is insignificant compared to the pre-processing.

          My (failed) solution: 41366581. Still I advise against seeing it, my source code today has been a huge mess :<

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

            Thanks for sharing. And now I can see why you thought it was so difficult xD

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

        It didn't fit in TL for me too.

        Does the problem require some kind of Fast IO?

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

          I'm not even sure.

          Even my "Pretest passed" solution (which was O(2n  *  100) in pre-processing and O(1) for each query) took about 1.4s for the worst case

          (sync_with_stdio switched off by default for better IO).

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

            I use scanf and it didn't pass in O(2^(2n) * n) :< Didn't realize k <= 100 though :<

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

          Probably not. You can usually get away with some other constant optimizations.

          Can you share submission?

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

        2^(2n) and pretests passed in 1s for me

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

    I am too dumb lol. I was fixated on somehow manipulating the trie. But it was just precomp.

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

Thank you for the contest! Keep it up!

In my opinion, the problems were nice. And I quite like the format where there are even more problems than the usual five. Plenty to choose from.

However, there's room for improvement: the legends were not exactly a fit, and the Russian translation was not perfect either.

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

This is probably a very dumb question but how do you solve C?

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

    You should use sqrt-blocks.

    Here is sample for 17.

    [17] [13 14 15 16] [9 10 11 12] [5 6 7 8] [1 2 3 4]

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

      Well... I implemented that during the contest but it turns out there are a couple of bugs in my implementation (starting from the fact that I printed no spaces between numbers in the "left-over" block). Your 17 example just so happens to point out both of my bugs :P

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

    What I did was try and divide the array into "blocks". If a block is of length k we will print out n-k+1, n-k+2, ... , n, n-2*k+1, n-2k+2, ... n-k. We see that the sum in this case is k + ceil(n/k). The k is from the LIS (the increasing blocks), and the ceil(n/k) because there may be one extra block, and by choosing the biggest from each block we will get LIS = ceil(n/k). Now, try for each k, and once you find the minimum sum, print the array according to the statement above. Please forgive my grammar, as I was writing this in haste :)

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

    cut into some blocks(use sqrt)such as 9 , cut into 3 blocks,then 7 8 9 4 5 6 1 2 3,make many increase Sequence.

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

    You can always partition the permutation of length n to have 2 specific LIS and LDS values where LIS = i where 1<=i<=n and LDS = ceil(n/i). example: n = 9 you can choose i to be 3 and so ceil(n/i) will be 3 and the permutation can be:

    7 8 9 4 5 6 1 2 3

    So you can easily get the i that minimizes i + ceil(n/i) and then construct the permutation in this way:

    if you have a permutation 1, 2, 3, 4, 5 and the best i is 2. Then you can construct the permutation as follows: 5 3 4 1 2

    another example is how I have constructed the permutation of length 9 earlier.

    That is if you consider the sorted permutation 1, 2, 3, ...., n and the best i is x. 1, 2, .., x will become the last x values in the optimal permutation. and x+1, x+2, ..., 2x will be the x values before them and so on.

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

E is only about editing statement of appeared problem.

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

Auto comment: topic has been updated by Magolor (previous revision, new revision, compare).

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

That's good!But I think the difficulties between D and E was so big....maybe I'm too weak.orz

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

I think codeforces servers have lost their power. Maybe for increasing the number of contestants. In the past a few contests were found that were rated, but became unrated!

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

Was it really necessary to make it unrated? I mean, it was just a 20-minute delay, what seems to be an issue? Everyone was in an equal position.

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

    During the delay, no one was able to make a submission. It is unfair to someone who completed coding a problem just before the delay happened, but then have to wait 20 minutes to submit it.

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

      Well, delay time could have been spent on solving another problem. If you managed to do 4 problems in 30 mins, you should also look on E. There were a lot of ways to hold your time advantage.

      I'm truly disappointed, since this contest was combined, so a lot of Div. 2 programmers lost their chances to try competing with Div. 1 and lift their ratings quickly.

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

      It was unfair and inconsistent with previous decisions. There were much bigger issues yet rounds were rated as f**k.

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

Can E be solved by constructing the convex hulls of the 2 engines and checking that one of these 2 convex hulls can be obtained from the other by only rotations and shifts?

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

Statement of H was very bad. It took me more than 15 minutes to understand it.

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

    Many statements were very bad. "English by old people from post-communist countries" tier bad. The whole contest seems like it was made in a hurry just to have it before the authors leave for holidays or something.

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

      It wasn't bad English-wise. The story was very bad, complete mess. Idea of films and their endings and ways of combining them was very confusing. I could go on.

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

        I don't mean just bad grammar, but the kind of lack of understanding of a language that causes the stories to be bad because you can't express yourself well. And I don't mean just bad English, I'm pointing it out as an example; the statements were very hard to parse overall.

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

Both FizzyDavid's(41352396) and tqyaaaaaaaang's(41353078) solution passed system tests in problem E.

But their output for this input is different:

4 4

0 0

0 5

5 0

5 5

0 3

4 0

7 4

3 7

(I think it should be 'YES')

How did all these happen?...

(Problemsettings are satisfactory, though...

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

    Lol, yeah. FizzyDavid considers just rotations by multiples of 90 degrees which are obviously not sufficient (consider segments from (0,0) to (4, 3) and (3, 4))

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

    Sometimes system test is very weak, especially in unrated rounds.

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

    Yes. It was my fault.

    Tests are weaker at the beginning.

    Then I was asked to generate better test in order to hack:

    incorrect hull, use only area and length, use only dot product, ... strange solutions

    I thought it is strong enough...

    I forgot this one. Sorry.

    (Actually, I believe it may pass at first... My fault.)

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

      Will there more tests added? Will all the solutions be rejudged?

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

        We will add this test. But this won't influence the standings due to the contest rules.

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

    BTW: Why no one hacks?

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

      It's useless to hack when it's annonuced to be unrated..

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

      Too many approachable problems :) . I usually turn to hacking when I have no immediate idea of what to do with the next problem, and I believe many others do too. Or when hacked solutions just start to appear, which was not the case today either.

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

Can someone explain the solution of div2b please !!

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

    Consider the cases where moving a 1 or a 0 in A will change the OR of elements:

    • moving a 1 to a column where both string A and B had a zero A[i] == '0' && B[i] == '0'.
    • Moving a zero to a column where only A had a one A[i] == '1' && B[i] == '0'.

    Now, if you follow those 2 cases and look closely, You can see that you can move all the ones (let's denote them by countOnes) from A to the positions where both A[i] and B[i] are zero (let's call those positions validZeros), but, you can only move the zeros from A that have a 1 below them (let's call those moveZeros), and it's only worth to move them where case two happens. Let's call those ones that have a zero below them validOnes. Now, for all ones in A, you can move them to validZeros positions. For all moveZeros in A, you can move them to validOnes positions. Therefore, the expression ends up being: countOnes*validZeros + moveZeros*validOnes

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

Does anyone have a good proof (or can read the Chinese editorial) for why using sqrt blocks are optimal in C? To be clear, I understand that if you are using a block method, that sqrt blocks would be the best size, but it's not clear to me that using a block method would be optimal.

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

After seeing the F and being not able to think of anything other than brute force(I was hoping some good math in there since it is obviously F).I started watching FC Rottach-Egern — Bayern München which was more interesting than E and F questions.

The questions are not bad but estimation of level is very bad.F could be div2 C(at worst D) I guess.

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

    E was interesting. It uses interesting concept of convex hull + string matching.

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

      I could barely understand the question(mainly the legend in behind the question) and the examples were barking on my face to match the convex hulls.I liked implementing it without using doubles.But surely it is not worth E.The idea was good but the problem was not good overall at level of E.

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

        No need to use double. Assume we have polygon A1,  A2, ...,  An, then just match sequence (dist(A1,  A2)2,  dist(A1,  A3)2,  dist(A2,  A3)2,  dist(A2,  A4)2, ...).

        May wrong :)

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

          Yes I did something similar.I used side lengths and dot product of adjacent sides to represent angle.

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

          Wow! Can someone confirm this is correct?

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

            The sequence of pairs (side length, angle) is obviously correct, and if we replace angle with dist(Ai, Ai + 2) it's still correct, as we can restore angle by lengths of triangle sides.

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

              Aren't there 2 possible angles if we know the sides?

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

                Nope. Law of cosines. There are 2 possible cosines (α and  - α), but since the polygons are convex, it doesn't matter. You could always use all sides + area (sine and cosine) to make absolutely sure without having to prove anything, of course.

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

    F could be div2 C(at worst D) I guess.

    Div2C? If you want to make a horribly unbalanced round, yeah.

    Div2D/Div1B is a reasonable difficulty estimate, going by my impression and the number of successful solutions. Here's my idea: 3·108 is just 36 MB in a bitset, so let's optimise by ignoring numbers which aren't 1 or 5 mod 6 and do a classic, but constant-efficient sieve. This is a perfectly fine div1B; if pretests aren't too strong, people who don't test on maxtests can get burned and other people can get hacking chances. (I'm normally not a fan of weakening pretests, since I don't want to keep worrying if there are some weirder tests that make my code fail systests, but if I'm computing something that's known at compile time, I always check if it's good enough on maxtests or just hardcode maximum limits into it.)

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

    It hurts me so much that I can't even solve a Div2.C! XD

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

      I was under the impression that doing extended seive over blocks works reading the comments. If it works then it surely is not more than Div2D right.
      I take back my claim of Div2C in case it doesnt work. But extended seive with easy implementation is good enough for Div2C.

»
6 лет назад, # |
Rev. 4   Проголосовать: нравится -55 Проголосовать: не нравится

For f**k's sake!

There were much bigger shitstorms (queue blocked for more than half of the contest, terrible statements and mistakes in the problems) on cf and rounds were never unrated. I get used to the fact that no matter what, the round will be rated because majority would be happier. For some strange reason this time it was, even though it was only 20 minutes of server unresponsiveness yet problems were available to solve.

Wtf cf?

Edit. Is it because of money prizes or what? Why to disappoint everyone this time?

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

Auto comment: topic has been updated by Magolor (previous revision, new revision, compare).

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

Ahhhh

E and F, the two problems which roughly determine the 4-200 section of the standings in this contest are of poor quality.

E: disguised polygon congruence, a known problem and not a trivial one. If it were unknown, it could even be an F or a G by difficulty IMHO. Furthermore, as pointed out by others, the tests aren't very strong. They might be strong, but for this kind of problem they need to be stronger. For example, my first submission which makes an ordered triple (length, length, area) for consecutive vertices and then compares these cyclic sequences passes the system tests(as a challenge, try to think of a hack). Although the test which fails this approach is very specific, but I believe it could have been anticipated by the authors and testers.

F: the solution that uses to much memory is clear the moment you start thinking about the problem. Whether it passes the time limit is unclear, but it's easy to realize the problem is written in a way that it seems impossible to solve without finding all primes. After that, googling "Sieve of Eratosthenes low memory" and copy pasting gives you the full solution in minutes.

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

    For example, my first submission which makes an ordered triple (length, length, area) for consecutive vertices and then compares this cyclic sequences passes the system tests(as a challenge, try to think of a hack).

    Omgggggg, siiiiick! That hacks my solution and Benq's as well.

    Hack test

    It seems that this round should have been won by some fake blue guy :P

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

      But if you use signed area, that is not a problem right?

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

        I use signed area, but even though all areas I compute are positive because I operate on convex polygon. I would get different areas for angles α and  - α, but it sees no difference between α and 180o - α which is the problem here

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

    Edit: I saw the hack and get it, reflected ones are considered the same.

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

      Yes, because the cross product gives you the sin(α), so you cannot differentiate α and 180 - α. Putting the dot instead the cross product solves this issue since all angles are up to 180.

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

    F can also be solved by the usual sieve, using some casework for numbers divisible by 2 and 3.

    41372869

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

    Although the test which fails this approach is very specific, but I believe it could have been anticipated by the authors and testers.

    I did think about it and I like E as a problem because the right encoding of a polygon matters (or, well, should matter) — how to avoid doubles, how to ensure it's unique, then stuff like no reflections = direction on the convex hull matters... however, this round was prepared quite badly.

    I like F as a concept too, but if it's really easy to find, it shouldn't have been in the contest. Especially not one with prizes.

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

Why have my solution (http://mirror.codeforces.com/contest/1017/submission/41366026) got WA on test 20?

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

is there a difference between using long long as index and using unsigned int as index in bitset (in terms of performance)?

41372257

41372242

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

Auto comment: topic has been updated by Magolor (previous revision, new revision, compare).

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

[Double comment in case people don't check the editorial]

For 1017E - The Supersonic Rocket, many of the accepted submissions (around one-third?) actually fail on this test case:

4 4
0 0
1 0
1 1
2 1
0 1
1 1
1 0
2 0

I wrote up a detailed explanation of what's going on in this post: https://mirror.codeforces.com/blog/entry/61086

Can we add this case to the practice version of the problem?

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

Hope that we can see contests by Magolor again.

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

For problem D, I use O(q × 2n) "solution" and passed it.
my code:http://mirror.codeforces.com/contest/1017/submission/41379865

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

The second "guy" 000000 seem to be a group of contestants. Look at the submission times, you can tell that the problems were solved separately by more than one person.

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

    He had two submissions at the same time, right after the server came back after the downtime. There is nothing suspicious there.

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

    lol, u guys press downvote like the other guy was right and i was wrong. At least you should check what really happended first

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

      Maybe YOU "should check what really happended first", before making false accusations, without any real evidence.

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

        okay, sorry for not showing the evidences.

        you can see he finished A after 2 mins, then he solved C, which took him 4 min to submit at min 6. Then he solve B at min 7, which meant he had 1 minute to read the whole statement and solve B. You can see that he took 1 minute also to fix C's 3rd test, which was him just chaning '2' to '10'. Also you can see he use 4-spaces tab in A and B but 8-spaces tab in C.

        okay we had been interupted by server's error. assume he solved both D and F in crashing time, ignore his super fast submit speed because maybe we could do it also (2s between F and D), then look at D and F's code. D using C pattern (he declared iterator i at the beginning), define N = 10005, while F using C++ pattern and using const maxn = 4e8. I don't think those were done by only one person.

        his progess of solving E and G was also strange. sometime he submited E and then immidiately submited G. we can also see the spaces tab difference here.

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

        Lmao rekted

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

Thanks to the contest makes me know such a great people. But also sadly in this way. Wish Taravilse rest in peace.

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

Is this contest rated??

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

Why am i getting TLE in D ? 41423817

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

i like cs academy

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

Auto comment: topic has been updated by Magolor (previous revision, new revision, compare).