Magolor's blog

Codeforces Round #502 (in memory of Leopoldo Taravilse, Div. 1 + Div. 2)
By Magolor, history, 6 years ago, In English

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.

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

Comments Comments (260)
| Write comment?
»
6 years ago, # |
  Vote: I like it +59 Vote: I do not like it

Prize distribution, wow

→ Reply
»
6 years ago, # |
  Vote: I like it +220 Vote: I do not like it

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?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it -47 Vote: I do not like it

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

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +255 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it -15 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +138 Vote: I do not like it

        Your idea came true. There was no one to submit in 25 minutes, only 502.

        → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +24 Vote: I do not like it

    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!

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +67 Vote: I do not like it

    Now everybody knows this was a bad idea. :(

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +83 Vote: I do not like it

    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...

    → Reply
»
6 years ago, # |
  Vote: I like it +22 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it -109 Vote: I do not like it

null

→ Reply
»
6 years ago, # |
  Vote: I like it -581 Vote: I do not like it

Upvote if you are waiting new problems from Taravilse

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +296 Vote: I do not like it

    You’re undebatably one of the most disgusting and miserable people I’ve seen here on CF.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +59 Vote: I do not like it

    you're a fucking piece of shit you know, have some respect for people who were friends with him. If I were in front of you I would hit you in your fucking face scumbag

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -30 Vote: I do not like it

    Seriously,I didn't expected that comment from u!!

    → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it -29 Vote: I do not like it

    Do you think this will help,vote-cheater?We admire Taravilse not because of your votes.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +27 Vote: I do not like it

    Even though this comment was obviously not written in good faith, does anybody know if ltaravilse had written any unpublished problems? They could be added to another round.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    Upvote if you are waiting new problems from rotavirus

    → Reply
»
6 years ago, # |
  Vote: I like it +12 Vote: I do not like it

WOW!

The contest is made by a middle-school student

Chinese ??

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -128 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      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

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
6 years ago, # |
  Vote: I like it -123 Vote: I do not like it

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.....

→ Reply
»
6 years ago, # |
  Vote: I like it +30 Vote: I do not like it

Rest in Peace Leopoldo ltaravilse Taravilse!!

→ Reply
»
6 years ago, # |
← Rev. 11   Vote: I like it +68 Vote: I do not like it

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.)

→ Reply
»
6 years ago, # |
  Vote: I like it +26 Vote: I do not like it

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...

→ Reply
»
6 years ago, # |
  Vote: I like it +23 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 .

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Maybe "Chinese round" means Chinese do not have to do the contest at midnight.:D

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      But 22:05+2h15min=00:20... Maybe earlier than those start at 22:35 or even later. But I think if it means this, Codeforces Round 500 (Div. 2) [based on EJOI] and Codeforces Round #503 are the "Chinese rounds" instead of this one.

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 4   Vote: I like it +16 Vote: I do not like it

      But I think we have to do this contest at midnight.We'll take parts in this contest from 22:05 to 0:20,isn't it?

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I am a Chinese and now I'm travelling in USA now.It could be a good time for me to take part,but I didn't bring my computer:(

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I think it's the former. Well, never saw the latter works before, but if the setters were generous enough, they might provide a link to the Chinese statements when the contest begun, maybe?

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -18 Vote: I do not like it

    Actually not. In fact 'Chinese round' means that the time fits Chinese people. Being a foreigner, hope that CF will prepare translation of the problems, of course it will save competitors lots of time understanding the problems.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    Hey! I'm curious about how you find that? This blog was just created two weeks ago!

    → Reply
»
6 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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.

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +36 Vote: I do not like it

IOI is comming, we lost a great man!

R.I.P. ltaravilse

→ Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -14 Vote: I do not like it

if (Div1 && Div2 && prize) {

combine (Div1 + Div2);

}

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Mathforces?

→ Reply
»
6 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Why did CF merges Div1 and Div2 ？？

→ Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +37 Vote: I do not like it

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.

→ Reply
»
6 years ago, # |
  Vote: I like it +203 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Rest in peace brother.

→ Reply
»
6 years ago, # |
  Vote: I like it -93 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it +14 Vote: I do not like it

    Why do you have to be toxic in every posts?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it -23 Vote: I do not like it

      Coz i like to spread negative vibes :)

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It's sad that there is someone so pathetic, having to look for attention in the most disgusting of ways.

        → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
6 years ago, # |
  Vote: I like it -29 Vote: I do not like it

Is It Semirated?

→ Reply
»
6 years ago, # |
  Vote: I like it -97 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You are a disgrace to the Codeforces community.

    → Reply
»
6 years ago, # |
  Vote: I like it +19 Vote: I do not like it

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What's bad about common round?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it +1 Vote: I do not like it

      No offence,just crack a joke about the difficulty of Chinese Round(hell) .

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +47 Vote: I do not like it

        Not all Chinese rounds are duliu >^<

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +4 Vote: I do not like it

          However,your last round is very duliu

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it +2 Vote: I do not like it

            yep! ( >﹏<。)

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              6 years ago, # ^ |
                Vote: I like it -8 Vote: I do not like it

              Please trust me, Chinese rounds will make you "happy". I think that you understand my meaning.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                6 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                yeah...it makes me "happy".In another sense，maybe just lucky of survival.

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Sorry, my meaning is that Chinese rounds will be very hard sometimes. Really, I agree it with you that survival is very lucky.

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Rest in peace great Leo.

                  → Reply
»
6 years ago, # |
  Vote: I like it +29 Vote: I do not like it

Wish Leo a peaceful rest and Magolor a great debut.

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

→ Reply
»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it

RIP ltaravilse

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +23 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it -23 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it -42 Vote: I do not like it

Please, no delay

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +223 Vote: I do not like it

Round 502 and Error 502

Coincidence? I think not.

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

→ Reply
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Is it just me or Codeforces is heavily lagging ?

→ Reply
»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

looooooool what just happend !!!

→ Reply
»
6 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it -48 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +18 Vote: I do not like it

It’s a pity to be unrated.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Unrated! Goodbye.

→ Reply
»
6 years ago, # |
  Vote: I like it +139 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

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

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +76 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +26 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Nah. Participating in a contest has never been "get nothing", especially with such high-quality ones like today's.

        It's not just rating bruh.

        → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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 :)

      → Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +68 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

So bad ToT

→ Reply
»
6 years ago, # |
  Vote: I like it +62 Vote: I do not like it

Read the text carefully! Available

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    Successful Hacking Attempt +100

    → Reply
»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +89 Vote: I do not like it

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

The problems in this round is fantastic anyway :D

→ Reply
»
6 years ago, # |
  Vote: I like it -67 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Sad :(

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +98 Vote: I do not like it

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 .

→ Reply
»
6 years ago, # |
  Vote: I like it +9 Vote: I do not like it

9141 participants we don't see this every day

→ Reply
»
6 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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)

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have actually written a brute force code using small n values and deduced the relation from there

    → Reply
»
6 years ago, # |
  Vote: I like it +7 Vote: I do not like it

How to solve D ??

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

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

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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).

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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

    → Reply
»
6 years ago, # |
  Vote: I like it +9 Vote: I do not like it

2 minute silence for Top 30 people !! :)

→ Reply
»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you tell me why this is happening? I always use fast IO using cin and cout and thought that the difference could not be that big (to give TLE I mean).

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think the problem is the difference between speed of reading STL strings and C strings (aka char*).

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Nope. 41361499 reads chars and still gets TLE.

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Sorry, I should saw your code before writing something. Now, we talk about different things. I compared reading STL strings and reading C strings and you use char one by one reading (it's not the same as two methods, mentioned above).

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Can you link some documents about this?

            I always think read char must be faster than cin and cout. Yet I managed to get AC using cin + ios_base::sync_with_stdio(0) but gpt TLE using read char.

            Thanks.

            → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    close... http://codeforces.net/contest/1017/submission/41359754

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Don't you know that Chinese Round are always DuLiu

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +22 Vote: I do not like it

How to solve F?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Seem turn out to do how bruteforce :)

    → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    I have just written an Eratosphenes sieve with sqrt memory. I think it should pass

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How did you do the sieve with sqrt memory?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It has been described here

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          The time complexity of this method is still , right? I don't think that this complexity could fit the time limit.

          → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +98 Vote: I do not like it

      If intended solution is to enumerate all primes then do bruteforce, then the problem is trash!

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It works 2 seconds in a max test, so I think yes:) It astonished me enough too when i had realised it

        → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 2   Vote: I like it +47 Vote: I do not like it

        Exactly. This is one of the “outstandingly dumb” problems for me in the past 6mo ~ 1yr. It doesn’t even deserve its place in a joke contest. Something is broken in codeforce’s QA process.

        (FYI : the author doesn’t even do sieve with sqrt memory, you can check out that in editorial)

        → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    It seems you can just use eratosphenes with n/3 memory with bitset.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It worked out with almost stupid eratosphenes and vector bool 41370869. So even no need in sqrt memory optimization.

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      With bitset even faster 41371002

      → Reply
»
6 years ago, # |
  Vote: I like it +29 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    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.

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

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...

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    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 ( ͡° ͜ʖ ͡°)

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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).

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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 :<

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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

            → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        It didn't fit in TL for me too.

        Does the problem require some kind of Fast IO?

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          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).

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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

            → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

          Can you share submission?

          → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

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

    → Reply
»
6 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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.

→ Reply
»
6 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +11 Vote: I do not like it

    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]

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 :)

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    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.

    → Reply
»
6 years ago, # |
  Vote: I like it +75 Vote: I do not like it

E is only about editing statement of appeared problem.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it -10 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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!

→ Reply
»
6 years ago, # |
  Vote: I like it -45 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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?

→ Reply
»
6 years ago, # |
  Vote: I like it +31 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +16 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +44 Vote: I do not like it

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...

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +41 Vote: I do not like it

    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))

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +27 Vote: I do not like it

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

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    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.)

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

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

        → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    BTW: Why no one hacks?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      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.

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the solution of div2b please !!

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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

    → Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply
»
6 years ago, # |
  Vote: I like it +85 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 3   Vote: I like it +40 Vote: I do not like it

        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 :)

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

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

          → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Wow! Can someone confirm this is correct?

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it +30 Vote: I do not like it

            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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              6 years ago, # ^ |
                Vote: I like it +8 Vote: I do not like it

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

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                6 years ago, # ^ |
                  Vote: I like it +22 Vote: I do not like it

                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.

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  6 years ago, # ^ |
                    Vote: I like it +8 Vote: I do not like it

                  Thanks, I get it now.

                  → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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.)

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
6 years ago, # |
← Rev. 4   Vote: I like it -55 Vote: I do not like it

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?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +98 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +38 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yeah, that hacks my solution as well.

          → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +35 Vote: I do not like it

      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.

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    41372869

    → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    pref[kols][sum] += chis;

    here the sum can be greater than 100. so just add an if condition

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

41372257

41372242

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Depends on which operations. For example, fetching memory: not really, bitwise operations: yes.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +23 Vote: I do not like it

[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://codeforces.net/blog/entry/61086

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

→ Reply
»
6 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Hope that we can see contests by Magolor again.

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it -16 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

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

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 3   Vote: I like it +56 Vote: I do not like it

        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.

        → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Lmao rekted

        → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it -24 Vote: I do not like it

Is this contest rated??

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why am i getting TLE in D ? 41423817

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can solve each query in O(1) :)

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

i like cs academy

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply