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

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

Hello Everyone!

I would like to invite you to CodeCraft-17, which will take place on Thursday 12th January 2017, 9:05PM IST. The round will be a Div1 + Div2 combined round and is rated.

Felicity, IIIT Hyderabad presents Threads ‘17, the magnificent annual technical fest, is finally here in its 13th edition! With a plethora of intellectually engaging online contests in various fields of programming, mathematics and general knowledge, Threads is a celebration of the spirit of computing and engineering. The grand algorithmic sprint called CodeCraft, parallel programming in Kernel Cruise, mathematical enigmas in Gordian Knot, jeopardy style CTF event called Break In, overall Threads '17 has something to offer for every kind of computing enthusiast!

Codecraft Poster

I would like to thank Nikolay Kalinin (KAN) for helping us in preparing the contest,to Mike Mirzayanov (MikeMirzayanov) for the great Codeforces and Polygon platform and the Threads Team for helping in preparation of the problemset.

Prizes

  • Top 25 participants win Codeforces T-shirts.
  • Additionally, 25 randomly chosen participants from top-500 will also win a Codeforces T-shirt.

You will be given seven problems and three hours to solve them. The scoring distribution will be announced later. Good luck everyone!

UPD: The constraint of registration for eligibility to prizes has been removed. Everyone who participates in the round is eligible for prizes. Sorry for the inconvenience caused!

UPD2: Scoring is 500 — 1000 — 1500 — 2000 — 2500 — 2750 — 3500

UPD3:
The contest has ended. Thank you all for participating. Hope you liked the problems.
It was our first codeforces round and it was really exciting for us to see how the contest progressed!
Editorials and list of T-shirt winners will be published soon.

Congratulations to the winners!

  1. tourist
  2. W4yneb0t
  3. anta
  4. Um_nik
  5. ershov.stanislav
  6. LHiC
  7. jcccccccccccccccccccccsb
  8. GlebsHP
  9. jiry_2
  10. Egor

UPD4: Editorial has been posted.

UPD5: The random t-shirts winners will be announced tomorrow according to the algorithm described in this comment.

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

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

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

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

Random --> there is a chance for Div.2 users :)

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

?

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

I hope one day i will get a T-shirt from Codeforces. that will be the best recognition of my hard work. I can't dream for a T-shirt in this round but some (+) rating.

»
9 месяцев назад, # |
Rev. 3   Проголосовать: нравится -35 Проголосовать: не нравится

randomly !! Come on there is nothing random in coding even random functions don't work randomly

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

    Well, there are some ways to generate truly random numbers :)

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

      How? And what does "truly random" even means?

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

        the random numbers are generated by alghorithm like von neoman or using the common method (last number generated*constant + increament) MOD m beacuse of that it's not truly random .. so the truly random numbers are the number which can really generated randomly by some way

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

          that's what i meant and people sink me in much down vote(i don't like it)

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

            I suppose there are 2 reasons for it: 1) Your colour. 2) What's the point of pointing that out? I am sure the words have appeared here many times before, so people here might be tired of seeing it.

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

              aha you mean likeability and judgment.
              1)likeability: as much as you have color tends to red as much as you may be right.
              2)judgment: you probably writing that to get contribution.

              it's not facebook guys there is no celebrities her as much practicing as much tend to red & as much u help others as much u get contributions

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

          Why are you going too far?

          We have absolute random here, You know, There's no logic behind the codeforces community's votes...

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

            you're totally right sa1378. take my downvote

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

            huh! Not too randomized!!! Actually, the name of the writer, the color, his picture and then the comment is a little important!!! I like Sid! Upvote...!

            UPD: To be honest, my rank in the CF's contests are more randomized(*_/*)! I wrongly read a problem again and I spend much of my time on it and then, BOOOMB! Hope you read all of your problem correct!!!

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

              I like the second part of your username! upvote :))

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

                Clarification: "An" means "Shit" in Persian...

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

                  And It was just a mistake in my username. (~) Hope I can change it next year!!! +_+

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

Time to say goodbye to grey and cyan, and restore my blue color :D

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

7 Problems, 3 Hours... Eager to take part in the contest

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

Looking forward to the longer contest :)

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

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

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

It is rated!

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

Longer time and fewer problems than Goodbye 2016.Wondering if the problems gonna be harder. How difficult will the problems be?

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

Any past contestants of CodeCraft can measure the problems difficulty equivalent to common rounds of codeforces for newcomers?

:-)

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

** ** *****.

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

Here is something wrong with HTTPS certificate:

net::ERR_CERT_AUTHORITY_INVALID
Subject: felicity.iiit.ac.in
Issuer: StartCom Class 1 DV Server CA

Could you check it?

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

    You can add an exception in your browser to access it. Our ssl certificate is issued by startcom and it might not be installed. Let me know if the issue persists.

    • »
      »
      »
      9 месяцев назад, # ^ |
      Rev. 4   Проголосовать: нравится +10 Проголосовать: не нравится

      Why do you choose Certificate Authority "starcom"?

      starcom is the worst choose CA, bcs it lost the trust. And it's not problem of my browser, it's a issue of CA because this CA abuse too many rules of creating certificates.

      And "Starcom" was bought by "WoSign" who lost the trust too.

      proof: mozilla blog, google blog

      Could you use self-signed certificate? It is not better choose but it is better than starcom IMHO

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

From the post: Note : Don't forget to register on our website to be eligible for prizes.

The page for that registration is (perhaps?..) https://felicity.iiit.ac.in/threads/codecraft/

Aaaand, the Register link leads to... https://felicity.iiit.ac.in//auth/login/

What's the matter with you people, asking to register before registration is even working? Edit: I mean, there are currently no means to associate a Codeforces account with the "registration" on your site.

Also, the site font is poorly readable in Firefox in a wide range of scales (but looks fine in Chrome).

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

    not really!

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

    For registration for prizes, all you need to do is create an account on our website with the "nick" same as your codeforces handle. In case the nick is already taken please send us a mail @ threads@felicity.iiit.ac.in.

    • »
      »
      »
      9 месяцев назад, # ^ |
        Проголосовать: нравится +12 Проголосовать: не нравится
      1. You know, you could have mentioned the "same nick" part in your post before people try to register.

      2. In some cases, mine and knst's included, what you ask for is impossible.

      • »
        »
        »
        »
        9 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        1. I will update the post.
        2. We have resolved the issue of nick. Please try again.
          Sorry for the inconvenience.
        • »
          »
          »
          »
          »
          9 месяцев назад, # ^ |
          Rev. 2   Проголосовать: нравится +39 Проголосовать: не нравится

          Try again what? I've already registered under different nickname, since the site didn't allow my nickname to be used. And, I don't see any way to change it now.

          Edit: From the post: UPD: The constraint of registration for eligibility to prizes has been removed. — Thank you, I like this solution!

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

            Argh, was reading comments and registered there and only then I have read this UPD..

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

Error: Nick must be at least 6 characters long

really? And what I should write? knst_SPACE_DELIMITER?

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

Wow, this contest has my mind firing on all sorts of topics.

CodeCraft — Beer. Craft Beer.

Felicity — I am thinking about the CW show Arrow when I see this, but when I see the the font, I think about FireFly. I don't even watch firefly. Something about it makes me think about it.

Last is Threads. I am thinking about some gangster and his threads.

Well, anyway, thanks for the mind simulation and I am looking forward to the round!

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

"Note : Don't forget to register on our website to be eligible for prizes."

I registered it on the website and it redirects me back to the front page. When I re-open the register page it still says "click here to register", what did I miss?

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

    Once you have registered, you can login and update your account information. Don't forget to set your nick same as your codeforces handle. In case it's already taken, please send us a mail @ threads@felicity.iiit.ac.in

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

      Sorry, I see no way to update account information on the Threads '17 site. Please do kindly provide a link, or instructions how to find it, if such a page exists.

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

      I still get this page after registration, is this behaviour normal, or is it because of my nickname doesn't match with my CF handle?

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

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

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

Waiting for a round with codeforces stickers as presents.

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

what's the mechanism of the randomly chosen :/

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

Всем Удачи:)

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

У меня одного цвет ников неправильно отображается?

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

    Это волшебство. Ты что, не веришь в Деда Мороза?

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

      Почему тогда мой остался прежний :(

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

        ПоТоМушто верить надо, а ещё читать тута, это сделано было для сверх Div2)

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

That's great , if -by chance- i get a T-shirt i will offer to replace it with +200 rate :"D

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

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

Gordian knot looks interesting, is there some sort of archive of the past problems to have a look at?

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

Wow, nice round. Never got a t-shirt ever. Good luck with me, haha.

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

Looks as if the contest already got some negative feedback(s). The problems regarding the registration and all... Hope the problem set is good.

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

Looks like this will be a magic round.

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

Will the drain be adjusted to the contest's length? If it was not planned to be, PLEASE DO SO :)! It was argued many times why not adjusted drain is a cancer and the longer duration the bigger cancer! Please, please, please.

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

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

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

My First Indian Contest, Hoping For A Positive Rating Change.... bharat mata ki jai....

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

all we can do is hoping for the good contest

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

Was the score for the problem just changed? Specifically what caused that?

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

why I can't register to the contest !!

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

Worst contest ever!

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

А может кодфорц уведомлять о своих новогодних штуках в приглашении на раунд?

После тяжелого рабочего дня я долго смотрел в это безумие (серые ломают красных, оранжевые с -2 по А и т.д.) и мне казалось, что это нормально для 1&2-div раунда. Аж пошел свои задачи продебажить лишний раз. Потом глянул на рейтинг в профиле одного серого и все понял.

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

Pretest 12 on problem B is an immovable object..

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

    I guess your initial value for ans is less than 1 and your code cannot output correct answer for this test case:

    input:
    1
    1
    
    output:
    1
    
    
  • »
    »
    9 месяцев назад, # ^ |
      Проголосовать: нравится -13 Проголосовать: не нравится

    Use an unstoppable force on it. :)

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

for the first time I feel there is so much time left for the contest to end. :(

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

Great Contest ... hoping for the increment in rating !!! Best of luck Guys

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

testcase 5 1 1 1 1 1 answer is 1 this case sucks

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

after the contest gets over , help me solving problem C.I have done the mathematics behind it but dont know what algo to use and what data structure to implement my maths

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

    Two pokemon of types i and j can be permuted if the number of occurences of pokemon type — i and j are equal in all the gyms.

    Try to prove it.

    My pretests passed though.

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

      as is said i got the maths.You are correct.But i dont know what data structure to use and how to implement it.

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

        I used hashing technique, but I'm not sure this is a wise way to solve this problem.

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

that moment ,when you help people but you can't help your self ... -hack A then you hacked !-

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

Did anyone solved problem C with hashes?

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

Can someone explain how to do C?

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

    For each pokemon type x, maintain a multiset of indexes of gyms containting x. Now form clusters of similar multisets. A cluster of size n can contribute n! ways to the answer.

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

      Could you explain why the contribution is n! ?

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

        It's the number of permutation. You can permute all the N pokemons (from that cluster) between them and the number of each pokemon type from that cluster is the same.

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

      I did something very similar to that. Can I ask how you calculated n! mod m? And how you modded your answer variable in general?

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

        m can be maximum 1e6 so just precalculate fact[i]%MOD (1<=i<=1e6)

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

      but gyms and their count in that gym both must be same right??How do you deal with that

  • »
    »
    9 месяцев назад, # ^ |
    Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится
    code
    • »
      »
      »
      9 месяцев назад, # ^ |
      Rev. 2   Проголосовать: нравится +15 Проголосовать: не нравится

      This code is not needed once we have access to this: 23747486
      No maps, no tries — the code is very simple.

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

        I wish I could think of simple solutions like that.

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

          I am even more impressed by the fact that he came up with a solution in 4 minutes =)

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

        Can you explain what is being done over here in this code !

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

          Each vector a[i] has indices of pokemon gyms where this pokemon initially was. On sorting, the vectors get sorted among themselves.

          Now, if a[i]=a[i-1]:

          These two pokemons were present in the exact same gyms with same frequency in each of them. Now, we know that any permutation of such sets is a valid one, thus, we increment 't' and multiply to the ans.

          eg- if input was
          3 5
          4 1 2 1 3
          6 2 3 3 2 4 5
          4 2 3 4 5

          Then, a[] will look like this
          1 : 1
          2 : 1,2,2,3
          3 : 1,2,2,3
          4 : 2,3
          5 : 2,3
          ans = (1) * (1*2) * (1*2)

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

            I cannot understand what you did after storing the indices of gym for each pokemon?

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

              It's not what I did, it's what Tourist did.

              He sorted the array of vectors. The sorting resulted in lexicographical sorting among the vectors. In my comment above, a[] looks like that due to lexicographical order. Each vector in a[] represents a pokemon( we don't care which pokemon it originally was, we just care about the vector it represents ). So, if two pokemons have same vector, this means, they can be evolved into each other. Similarly, if k pokemons have same vector, they can be evolved into each other( hence, answer for this group of pokemons is k! ). If two vectors are not same, then the corresponding pokemon can't be evolved into each other.

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

                Let me add a few minor points.

                Each vector<int> can be thought of as a type descriptor (not pokemon descriptor) and we compare those type descriptors with each other (not pokemons).

                Each type descriptor is composed out of pokemons (well, their's type).

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

Overall a quite good contest but it feels sad when the ranking are decided by number of successful hacks instead of speed of solving problems.

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

anta did 18 successful hacking attempt while tourist 10 (both are good)..... after that tourist solved problem 'G' and placed first.

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

WHY,WHY in problem D is needed to set limits up to 75?Why not 50??It is so strict.

Problem E is a very good problem to practice your oeis skills....

Please,pratice more before making a round,and even if you try don't put stupid problems with stupid observation and stupid limits.

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

    How exactly did you use oeis?

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

      Treat primes independently,you can easily get that you can deal only with px and only x is important,generate answers for n = 2, 4, 8, 16 and do oeis for every n with r = 0, 1, 2, 3, 4.

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

    I did OEIS for two vectors with fixed N, saw that they are quadratic and cubic polys, interpolated and factored polys for many different N and saw a simple pattern:

    A factor pe of N contributes to the product:

    • r if e = 1,
    • (r - 1)r(r + 1)(r + 2)...(r - 1 + e - 2) * (r + 2 * (e - 1)) / factorial(e) otherwise.

    fix: r here is r from query increased by 2.

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

    How to solve it, was it based on mobius function? Fr(n) was multiplicative, probably. Also I tried to use if p is prime, f0(p^a) = 2, f1(p^a) = 2a + 1, f2(p^a) = (a + 1)^2, f3(p^a) = (a+1)(a+2)(2a+3)/6, and then it got lost.

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

      f_n(p^a) = f_{n-1}(1) + f_{n-1}(p) + f_{n-1}(p^2) + ... + f_{n-1}(p^a) = f_n(p^{a-1}) + f_{n-1}(p^a). I just used dynamic programming to precalculate all values.

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

    No need for OEIS in E. It is just plain dynamic programing for O(MaxR * MaxPrimePower).

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

for problem B, with this input

3

3 3 3

the output is 3 ?

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

    yep!

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

    Yes.

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

    I have copied one solution and on my computer the answer is 1, obviosly i hacked him, but got Unsuccessful hacked attempt, now I saw that on codeforces for same solution the answer is 1, why so ?

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

      Did you copy or retype? (you can't copy during contest)

      I think you have made mistake in typing his\her solution.

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

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

Can anybody explain how to solve D?

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

    I used the following dynamic programming:

    1. A state is a mask of already seen numbers (the largest number is always at most 20) and the position in the string.

    2. A transition is just going from one position to some other to the right from it and adding the corresponding number to the mask.

    This solution is fast enough if implemented properly.

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

      The key observation is that out of the n*(n+1)/2 substrings, there can be at most n*5 substrings that correspond to numbers between 1 and 20, so you can cut a factor of n from the runtime.

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

        You forgot about leading zeroes.

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

          There are still at most 5 transitions. 0 is not allowed, so leading zeros only move the start of the valid range to the right. They can't increase its length.

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

            Ahh, if we fix start of interval there are at most 5 ends, I missed that, nice.

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

Hacking is hard when you are colorblind...

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

What was the approach for problem E?Did it involve mobius inversions?

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

    I noticed that the function is multiplicative. So I tried to solve for a prime power pe. Notice that

    .

    If you let then the above translates into

    .

    This recurrence is the same as counting monotone lattice paths from (0,0) to (e,r). Combining with base cases, you can find the solution

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

Problem B hacking case 3 1 1 1 output: 1

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

To solve Problem D, I was using the fact the maximum number could be 20. Hence my DP array should be :DP[1<<20][75][75] (which is MLE) where the state of DP is(mask,idx,currentCuts). How can i optimize my memory ?

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

    you dont need to keep track of currentCuts as you just need the total sum and not the actual value for each K

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

      Thanks.It was to silly of me to put currentCuts in DP state.

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

      Damn... But I have managed to squeeze into time and memory limits with keeping track of currentCuts :)

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

the friend residing in that city dies, so he is unhappy as well.

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

tourist again :( !

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

Hacking of C was so exciting.

For example, Errichto used XOR for hashing. So I wrote Gaussian elimination.

Errichto and wokop22's best strategy was submit a code just before the contest ends. So I don't have enough time to hack it.

And the result of this is Errichto's win. Congrats!

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

    That sounds kind of contest-breaking, they shouldn't be about this.

    I'll remember it as a viable strategy regardless. :D

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

    I'm glad you had fun. And during the round I didn't realize that my solution is hackable because of xoring — so I learnt something today.

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

Hi. I am noticing many people this round who are colored red and rated Grandmaster. However, when I click on their profile, their rating is much less than 2400. Does anyone know why this is? Is it a bug with the website?

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

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

Thank you for good contest.

Special thanks to C (which can be solved without hashes :)) and E authors.

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

    How did you solve C without hashing?

    I used sums of rand()s, but it's basically the same thing as hashing.

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

      One can show that storing the vector of pairs (gym, count) for all Pokemon is fast enough in the worst case.

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

        What is the worst case complexity for such sorting and how can we prove it?

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

          It depends on your choice of sorting algorithm. I don't know exactly what std::sort does, but it got AC.

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

      Well, actually problem is about splitting pokemon types into clusters, where in one cluster number of pokemons of each type is same in each school.

      Let's build this clusterization sequentially, adding school by school to it.

      (You may ask here what "clusterization" is. Clusterization here is array c[i], which contains identifier of cluster for each type, one class will have same numbers, and different from all others).

      So how to process a school?

      Group pokemons together by type and count them (in each group, you will have pairs "type, count" after it). Then group pokemon types by number of pokemons in them. (This step can be done in ), don't touch pokemon types with zero pokemon count, it would be too slow).

      Now we have "old clusterization" and new classes to split it.

      Iterate over groups of types with same number of pokemons. Split each group by current clusterization. Take note, that each subgroup will have a common type.

      So we will simply assign to c[i] some common unique value for all types in this subgroup. (How to get this unique value? Just maintain the maximum of current values in c[i]).

      Remark. We just didn't payed attention to group with 0 pokemon types, but if you look carefully you will see, that it's c[i] don't need to be updated.

      Remark. All steps above are done in time.

      Remark. If you have troubles understanding text above, you may want to draw some pictures on paper -- draw a circle and split it's area into pieces. Consider this to be old clusterization. Add some more circles into previous one, it should have some non-trivial intersections with previous classes. Consider this to be groups of pokemon types with same number from new school, currently processed.

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

        How do you store such clusters? I was trying to avoid sets/maps but in the end had to store clusters as sets, to allow quick removal (when intersecting one cluster with another). 23753670

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

any ideas how to solve B? I found it quite hard to do it in O(N) or O(Nlogn)

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

    If gcd(a, b) != 1, a and b have at least 1 prime in common. For each prime that divides each number do freq[prime]++ and take the greatest of frequencies.

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

      I tried that with once with clasical prime factorization(23760980) first and then with sieve(23762396) and both time TLE on 11th pretest :(

      • »
        »
        »
        »
        9 месяцев назад, # ^ |
        Rev. 10   Проголосовать: нравится +1 Проголосовать: не нравится

        what you are doing wrong is you are generating prime numbers uptil (100000).the prime number count uptil that is 9950.So your run time will be 10^4*10^5=10^9 approx. which will result in a tle on case 11 .I was having the sae problem.Then i did something smart .I calculated primes only uptil sqrt(10^5).And while traversing array i kept on dividing the arrays with these primes.At the end what was left in the array were themselves primes which u can count in an O(n) operation.So the complexity was brought down from 10^5*10^4 to 10^5*sqrt(10^5)=10^5*10^2=10^7 approx which is within time bounds

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

        Instead of checking until X every time, save a vector for each number with the primes that divide it. Remember that the sieve is O(nloglogn) so the memory complexity of having the prime factorization is O(nloglogn) as well.

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

    do something like sieve function.

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

    Do the prime factorization of each element of array. Elements which have atleast one prime factor in common will have gcd>1,thus they can be included. Maintain an array x in which x[i] is the count of array elements which have x[i] as one of its prime factor. Answer will be the maximum x[i].

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

    This is my idea.Although i dont know whether it will pass the system test.It's O(n(sqrtn)loglogn). First i ran seive algo to generate prime numbers till sqrt (n).That took me sqrtn(loglogsqrtn) time.after generating the prime numbers i divided each array element by all these prime numbers till sqrtn that i generated.In doing so i also mantained a count which will be the answer variable.With each prime a new answer.i also kept on dividing array by these primes so that after i had used all the primes what was left were only further primes in the array.I counted each primes occurence after sqrtn in array and then reupdated the answer if possible.Its O(n*sqrtn*loglogn)

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

    Make array D[100000], where d[i]="lowest divisor of i(not 1 of course)", then for every integer of the input (let it be x) save the values of D[x] in other array. Then determine the maximum number of equal elements in this array and this will be the answer. But have not passed system tests yet.[FAILED]

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

      Huh you're sure?But just because 2 elements don't have same lowest divisors it doesn't mean they are coprimes.Try 3,6,33 your algorithm output is 1 (?) but answer is 3.

  • »
    »
    9 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится
    for(int i = 2; i <= mx; i++){
        now = 0;
        for(int j = i; j <= mx; j += i)
            now += cnt[j];
       ans = max(ans, now);
    }
    

    Works O(mx * log(mx))

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

      How?

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

        N / 1 + N / 2 + N / 3 + ... N / N = N * (1 / 1 + 1 / 2 + 1 / 3 + ... + 1 / N) = N * log(N)

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

          Not the time complexity but the explanation of solution.

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

            gcd(x,y) = g implies x,y >= g and g | x,y .

            The outer loop just fixes the gcd and the inner loop sums up the counts of all multiples of that gcd .

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

    Am I the only who had been surprised when seeing Zlobober is asking this question and then noticed that it's Zlobber not Zlobober? :/

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

      Yay, I was also kinda surprised. Just wait until magic ends, and it will return to normal.

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

        It seems like my handle is giving me some privileges in comments.

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

    While this submission did not pass system testing (WA on test 82)...it was such a monumentally hilarious idea that I think it should be public..

    23759222

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

wish no fst!

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

Thank you!

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

Really unusual problem set, not very hard, but no easy problem..

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

I tried to hack this solution for problem B. It uses strlen() for computing length in each iteration. So, I thought it would O(n*n) complexity. I gave input string of "zzz..." 10^5 times but it passed easily. Any help on why did it happened ?

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

    A compiler can optimize it if the string doesn't change (it's not guaranteed, though).

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

      Suprisingly, I successfully hacked another such solution(here) with the same case.

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

        Its because he is using global variables. Hence (almost) no optimizations.

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

        One solution uses GNU C11, the other uses GNU C++. Does this make the difference?

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

    Modern compilers are smart, so perhaps they take this opportunity to optimize and place the calculation before the loop.

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

    AFAIK, compiler is not optimizing semantics of strlen and other funcs.

    But strlen's implementation is bloody fast -- it can be written using SSE for example.

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

Nice set of problems! Problem statements were well articulated.

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

Used hash in problem C, failed systest. #notcool#feelsbadman

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

This time lots of hacks & system failure !!!! :P

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

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

    Can someone explain me this comment? Does it suggest that tourist invents better problems? I don't get it.

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

      It refers to the CodeCraft tagline, "So you think you can code?"

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

Hmm...

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

mtomic the TOPPEST of ANIMALS!!! Take a bow son, take a bow!!!

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

And there were 104 tests...

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

Got WA on C because of low RAND_MAX. Gotta love Windows.

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

    Me too.

    Something like rand() * rand() + rand() would probably work.

    EDIT: Confirmed, got AC with this change.

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

      rand() * MAX_RAND + rand() is better — all values can be achieved, assuming that consecutive calls of function are independent.

      Edit. As mareksom pointed out (thanks!), my way isn't perfect either. It isn't deterministic which of two rand's will be computed first and thus theoretically two runs of the same program can give different behaviour. So, it's better to do int tmp = rand(); int big = tmp * MAX_RAND + rand().

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

        To be completely precise, assuming that rand() gives a uniformly distributed value on [0, RAND_MAX], and that two consecutive calls of rand() are independent random variables (that is not true, of course, but imagine that), to get a wider uniform distribution, you should use int tmp = rand(); int big = tmp * (RAND_MAX + 1) + rand(), since RAND_MAX (that is equal to, for example, 32767 under Windows) is an inclusive bound.

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

Am I the only one who copied wrong spelling in hurry just because of this line in explanations

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

Как много тестов на второй задаче....

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

How many tests were provided for G?

Because it is really bad feeling.

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

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

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

here is a bug in system testing with my code 23767420 in problem 757E - Bash Plays with Functions my submission got WA on test case 57 while when i compiled on codechef ide with the same code it gave me the correct answer....i also faced the same problem of compilation before some time but it was on practice mode but this time it will affect my rating please resolve it if possible

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

    Did you run the code with test case 57 as input (on the codechef IDE)?

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

      yes i run my code with by taking 20 initial case of test case 57 and on codechef IDE it gave me the correct answer for those 20 case while on codeforces it gave me wrong answer on 1st case in 57 test case

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

Test cases for D are so weak! We don't have to use 20 to pass all cases.

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

Почему у TooDifficuIt в положении старый ник, хотя он его поменял?

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

I thought of getting TLE on C using just vectors and sortings without hashing. But it gets AC fast enough.

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

Awesome contest :)

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

Yay finally became orangy on my birthday :)

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

    Yay finally I failed another contest, even though I scored F I won't get 2200 before my round :<

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

I think I have a different approach for Problem C. Have a look at my code

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

Why can the maximum number be 20 in problem D? I think it should be 16 only. Because minimum number of bits required to represent all numbers from 1 to 16 is 70. Minimum number of bits required to represent all numbers from 1 to 17 is 76. And the string length is only  ≤ 75. Am I right?

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

What about problem F? I'm really curious.

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

Congrats rajat1603 for becoming red

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

magic is so buggy with rating changes!

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

Someone just copied tourist's code for problem G and got AC but using C++14 instead of C++11 heh

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

    he also changed one cout to printf.

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

    Yeah, and the funny thing is that neither changing cout to printf nor submitting under C++14 works for me :)

    Resubmitting many times might probably help.

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

      or add some comments :)

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

      Another way to make it pass is to politely ask compiler to produce faster code using O3 (23772403).

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

      I heard from the problem setter that the expected solution was O(N * log(N)) and that only highly optimized O(N * log2(N)) should have passed.

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

        During the contest I tried to submit the solution that does not use the fact we swap only the adjacent elements, but it used Cartesian trees and it worked about 6-7 seconds on maxtests. After the contest I managed to replace all Cartesian trees simply with vectors and binary searches, it still works in and fits in 2.1 sec: http://codeforces.com/contest/757/submission/23772311 Though, it now relies on that only the adjacent elements are swapped.

        This solution may even be optimized to if we use fractional cascading technique, but it is much harder to implement and I'm not sure if it would significantly reduce the running time.

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

          How could fractional cascading work? I think my approach is the same and I have thought about fractional cascading, but it seems like there may be too many children for each node so we can't store next-level pointer for every branch.

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

            Seems you are right, I didn't notice that in contrary to segment tree in centroid decomposition we have many children. Looks like it makes impossible to find the right position in O(1) when moving from level to its child.

            Ok, I don't know how to solve it in :)

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

            I've just realized that if we ternarize the tree by adding d - 3 edges of zero length to each vertex of degree d > 3 (as described in the editorial), my approach works fine, since the centroid decomposition tree becomes no more than ternary and we need to store no more than three mappings from current level into children levels.

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

              Right. It's funny that binary tree actually works better in a centroid decomposition solution in this case. :)

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

              Well, I met a new problem when I tried to implement it: is there a simple way to maintain fractional cascading after a swap? Since swap is a relatively simple operation I guess there might be one, but I can't find it.

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

    The TL of Problem G seems to be too tight!

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

      Maybe the author has a better solution. If not I would be sad about these constant factors...

      Anyway, I should foresee this before implemented it, but "solving the last problem" is really a beautiful fantasy :(

      Edit: All right, I'm stupid. It seems like I used some unnecessary data structures...

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

When will the list of Tshirt winners be announced? Anytime soon?

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

Could not even understand problem C?

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

3 101 Why answer is 5 in Problem D?