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

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

안녕하세요, 코드포스! (Hello, Codeforces!)

I'm super happy to introduce you to Codeforces Round #566 (Div. 2), which will take place on Jun/11/2019 16:05 (Moscow time).

The round will be rated for all Division 2 participants, yet any Division 1 participants are welcome to join us out of competition.

You will be given 6 problems and 2 hours to solve them. Score distribution will be announced later.

The listed handles below are contributors. Thank you for all who listed!

This is my first Codeforces contest ever. I hope everyone who will join this contest enjoy. Thank you!

WINNERS:

  1. Castor
  2. thecodinglizard
  3. puyu_liao
  4. UoA_Kanade
  5. abandonedw1
  6. average_frog_enjoyer
  7. orz_liuwei
  8. emengdeath
  9. ashutosh450
  10. hyfzbtrs

UPDATES:

  1. Let me spread the meme from McDic Minecraft Telegram group — Ggungah.
  2. Score distribution is 500-750-1250-2000-2250-2750.
  3. Editorial is available.
  4. Congratulations for the winners!
  5. I am sorry for weak systests for B and F. Sorry again.
  • Проголосовать: нравится
  • +514
  • Проголосовать: не нравится

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

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

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

Best of Luck for your first contest as a problemsetter.

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

Wa! A Korean round!

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

upvote if you believe there will be kpop tasks in his korean contest

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

Hit you with that ddu-du ddu-du du~

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

I wish everyone high rating!

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

Korean round will be amazing!!!Oh my my my, oh my my my! I've waited all my life. Oh my my my, oh my my my! Looking for something right:)

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

Why Hello is 안녕하세요 but Codeforces is 코드포스 which is shorter than Hello?

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

    Also thought how difficult is it to write just "Hello", just unbelievable

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

    That's not even a Hello.

    It's a Hi. XD!

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

    I have always wondered how Chinese/Korean people write things

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

      That's an art :D

      (However I have not mastered it yet. T_T)

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

      It is actually very simple. We have these Oriental supernatural psychic abilities to inscribe complex letters into paper without using hands.

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

      I wonder how Arabs too

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

        Nope writing Arabic is easy.Arabic alphabets are simple in shape.

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

        No, I'm Iranian and our font, Persian or Farsi is like Arabic. I think it is easy. :D

        Maybe these different opinions are because of different viewpoints. For us Korean or Chinese are hard to understand. But now I see that you think Arabic is difficult. Because we all are used to our own languages and other ones seem strange. But the most important think is that all languages are beautiful. :D

        Sorry for my bad English. :D

        Btw do you Korean think your language is hard? Maybe I'm wrong.

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

          Though I write Chinese since I born, I still think writing it is a exhausting job, lol.

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

          Korean letter seems scary because one syllable is cracked into a single letter. However, it's actually a composition of consonant letters (ㄱㄴㄷㄹㅁㅂㅅㅇㅈㅊㅋㅍㅌㅎ) and vowel letters (ㅏㅑㅓㅕㅗㅛㅜㅠㅡㅣ). So while there are 11172 Korean letters, you only have to remember 24 simple letters- after then you can write all of them!

          Korean people are proud of their language, and we have a "language day" which recently became a holiday. I also think this unique system makes pronunciation much clearer and complete. However, I'm not sure if it's easy, because "easy language" and "easy letters" are a different matter, and "smart letters" and "easy letters" also are. It's my mother tongue, so at least I'm not the one to judge.

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

    Technically it's Annyeonghaseyo XD

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

    let's hope problems statements are long in Korean

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

    Well, if you use hanja honyong(漢字混用) to write 안녕하세요, the meaning of the phrase would be clearer (especially for Chinese). 안녕하세요=安寧하세요, it's asking if someone is free from worry. And, 코드포스=Kodeuposeu. This word is just a transliteration.

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

Waa~~ It will be Good Good Round~~ :)

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

korean round <3

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

It will be good round :D

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

How does it feel to have div2 after div3?

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

BTS brought me here!!

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

i hope there will be short questions !

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

Apologize

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

"...Thank you all who listed!:
- myself, arsijo
- myself
- arisjo
- tester — [some testers and myself]
- Mike"
tm McDic

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

Finally your round has arrived! Congrats! :D

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

The contest has extra-registration?

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

I hope a once wins your round :D

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

Unusual time for the contest, again

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

I wish it will be a great contest . Thanks for this Effort

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

... and who is the mother? did cf and polygon got born by bipartition?

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

크으.. 국뽕에 취한다.. Cheer up McDic !

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

I want to do last contest as a Specialist. -> Blue

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

sees a codeforces round
Me: Codeforces round yay!
notices it's korean
Me: Codeuposeu round assa!

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

BTS bring me here

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

한국어를 공부하는 사람으로서 한글을 보니 매우 기쁘네요!

대회가 잘 되길 바랍니다^^

Я очень счастлив, потому что я учу корейский язык!

Я ожидаю, что этот раунд будет хорошим соревнованием^^

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

Is it rated up to 2100 rating like many other div2 contests?

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

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

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

Maybe the reason for the unusual time of the contest is Iran vs South Korea soccer match!

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

Let me fly up to Purple on gookbbong round~~~~~~~~

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

Do you guys think doing a contest after anesthesia is a crazy idea?

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

퍼플가게해주세요...(Let me go to Purple this round)

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

Hmm. Why does nowadays always 6 problems? Is this only fast coding?

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

https://t.me/mcdic_ch

If anyone needed link to his minecraft telegram channel...

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

    That channel is not used for a long time.. lol. I have active chat group now.

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

It seems that I haven't got the ability to solve problem D as it scored 2000. (smog

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

Seeing the score distribution , i guess it is (speed + implementation) contest.

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

hi team :)

is the contest rated for div 3?

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

That's why I love $$$ $$$ ̶M̶a̶t̶h̶f̶o̶r̶c̶e̶s Codeforces

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

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

What an amazing implementation contest!

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

In D why answer is not center of tree ?

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

    check a look:

    4

    1 2

    2 3

    3 4

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

    Try this case:

    8
    2 1
    1 3
    3 4
    4 5
    1 6
    6 7
    7 8
    

    The only answer is $$$2$$$.

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

      so if the answer is not the center, then it must be one of the leaves right ? How to check that ?

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

        Suppose $$$v$$$ is not a center and not a leaf, then there are two leaves $$$l$$$ and $$$m$$$ at different distances from $$$v$$$ (suppose $$$l$$$ is closer). Consider the vertices at the same distance from $$$v$$$ as $$$l$$$ and notice that some of them are not leaves.

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

          Ok thanks but I know how to prove that. What I want to ask is that if it is not the center, how could we find the leave which is the answer ?

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

        I tried to find centroid on slightly modified graph(I deleted chains starting from leaf nodes) I was late for about 30 sec to submit

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

How to approch E ?

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

    The powers of f3, f2, f1 were terms of different tribonacci sequences with different first numbers. I couldnt figure out the sequence of powers of c, and it was also not there in OEIS :(

    Matrix Exponentiation is must, but couldnt figure out the matrix for c :'(

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

      Yeah, same ... wasn't able to figure out powers of c. Didn't know about OEIS though. Thanks for that :D

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

        If you make $$$n=n-3$$$, then powers of c would be $$$2*\sum_{i=1}^n i = \frac{ n*(n+1) } {2}$$$

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

      You could reduce the problem to solving $$$G_{x} = G_{x-1}*G_{x-2}*G_{x-3}$$$, if you take $$$G_{x} = c^x F_{x}$$$. But, I couldn't see the fibonacci thing lol. Maybe we should have given the contest together xD.

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

      Power for c was (n-2)*(n-3) using summation of AP formed: 2*(1+2+....(n-3)).

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

    The answer is some power of $$$f_1,f_2,f_3,c$$$

    To deal with the power of $$$f_1,f_2,f_3$$$ it is a three-term recursion.(Fibonacci number is a two-term one). It can be rewritten in matrix form, and use fast power for large power.

    To deal with $$$c$$$ it is 2* A062544 in OEIS? It has a closed matrix form and solve it similar to the first one.

    Update 1 : Check tutorial/other stuff for better calculation of c

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

    Let g(x) = logc(f(x)) and h(x) = g(x) + x.

    The original equation becomes h(x) = h(x-1) + h(x-2) + h(x-3).

    After this, the problem could be solved by matrix power mod.

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

      exponent " c " can be attached with f(X) to make it g(x) = (c^x)*f(x) ;

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

        Yes. They look equivalent. I guess I am just not very comfortable with exponents.

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

          I looked at your code https://codeforces.net/contest/1182/submission/55452776

          However, I was unable to understand the last 3 lines :

          ans = mul(ans, pow_mod(C, (3 * ll(a) + 2 * b + c) % (MOD - 1)));
          n %= (MOD - 1);
          ans = mul(ans, pow_mod(C, (MOD - 2) * n % (MOD - 1)));
          

          It would be great if someone could explain them!

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

            Suppose after solving $$$h_x = h_{x-1} + h_{x-2} + h_{x-3}$$$ we end up with something like: $$$h_n = u\cdot h_3 + v\cdot h_2 + w\cdot h_1$$$.

            Therefore, $$$f_n = f_{3}^{u} \cdot f_2^{v} \cdot f_1^{w} \cdot C^{3u + 2v + w} \cdot C^{-n}$$$

            By Fermat's little theorem, we can take the reminder of the exponents mod $$$(MOD-1)$$$ to simplify the calculation.

            I hope this explains.

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

how to solve C ??

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

    sorting first by the number of vowels, then alphabetically, on the one that ends, and then we create two arrays and run by the sorted, we look at the neighbors, if the letters are 2 words, then we sort again and see if the number of letters is equal, then it is 1 word. sorry, i don't know English very well.

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

Shitty fast typing contest.

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

I think in problem C finding m is enough and printing lyrics just makes problem complicated.

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

How to solve E ??

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

Any idea about pretest 16 in C? Is this logic wrong: For a given word,check if there is a word with same vowel count and same last vowel. If it isn't there,Try to check if there's something with same vowel count.

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

    case: 4 a e e u

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

      holy crap. i should have run a pass first for finding all pairs with both vowel count and last vowel same,instead of doing both at the same time. changed that and your TC passes. Is this logic right? ^

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

C was devastating :))

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

Many submission will fail at problem B, i did 4 hacks and was close to 5th.

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

    some hacks were

    single dot (.)

    single (*)

    and (*****)

    and

    .*.

    **.

    .*.

    and

    5 10

    ..........

    ..*.......

    .******.*.

    ..*.......

    ..........

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

    Predicted OMG ^^

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

      hahaa.. even i went to hacking after first 3 problems as it was very hard to solved the remaining in remaining time. i did 4 hacks, submitted invalid input for 5th otherwise it would be 5. LOLOL..

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

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

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

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

A: quite nice

B: cases

C: probably some cases too, didn't think of this task

D: quite an easy idea I think, shitty to implement

E: maths

F: maths

I'm sorry, but I didn't find any of these tasks entartaining, very bad problem set (for me).

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

    good analysis, though d was good. i think the problems were not learning oriented. I was expecting this, as it has became too common in chinese and korean rounds. even dp problems are like they r picked from some maths olympiad books.

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

    I think D is so hard (sad)

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

    first submit D, then talk! you made 9 attempts for D and still couldn't solve it! still a bad problem set FOR YOU?

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

my code shows this output on C Idk why
2
that first
the this
mcdics about
wow round
edit:never mind stupid erase mistake

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

RIP B

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

B = hackforces

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

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

If honestly I don't understand. Pretests must be weak or this was just occasionally? I mean hacks like '.' and '*' and test 23 and so on. I understand that it is my fault but all in all pretests was too weak.

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

    I asked them in the contest time about test only a * and they answered me its a invalid +, so if you were in doubt about this, you could have asked, even tho the pretest should have this test, I think.

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

How to calculate power of c in question E ?

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

Seems like I have to give 2-3 contests to just come back to my original rating now :(

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

it`s a time to be expert ^^

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

E and F was math problem. I think that F was pretty good, because there isn't many Trigonometry Problems

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

What is the test case 23 in div 2 B . My submission is fail on it test case 23 https://codeforces.net/contest/1182/submission/55452743

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

    Only one "*"

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

      There should be atleast" +" symbol it neans all upward down left right and middle should be filled..so how single star??

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

        A "+" shape is described below:

        A "+" shape has one center nonempty cell. There should be some (at least one) consecutive non-empty cells in each direction (left, right, up, down) from the center. In other words, there should be a ray in each direction. All other cells are empty. Find out if the given picture has single "+" shape.

        This is what a + is, so, it s not obligated to have a + shape in the input, and that is why you have to code to find if there is only one + shape in the input, are you kidding me?

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

Can someone check what's wrong in this solution for C? https://codeforces.net/contest/1182/submission/55451525

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

In problem E, I am facing a doubt: I initially thought that I can condense the problem to the powers of f1,f2 and f3(ignore the c power for now). The powers of f1,f2 and f3 will be the nth, (n-1)th and (n-2)th term of Tribonacci sequence. But the powers will be in form of mod(10e9+7). As we know (a^b)mod M != (a^(b%M))%M ex: a=2,b=5,M=3, how do i effectively get the answer?

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

For test case 35 of problem B My compiler gave a 'NO' but codeforces custom invocation is giving 'YES' and I think I handled the case on which it is failing.

here is my submission:

Can someone please tell me why is this happenning?

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

Can you check my idea for solving "E"? In my point of View we can calculate degrees of F1, F2, F3, C F1's degree is Fib(n)

F2's degree calculates by: F(1) = 1; F(2) = 2; F(3) = 3; F(n) = F(n — 1) + F(n — 2) + F(n — 3) F2's degree equal to F(n);

F3's degree calculates by: F(1) = 1; F(2) = 2; F(3) = 6; F(n) = F(n — 1) + F(n — 2) + F(n — 3) F3's degree equal to F(n);

C's degree calculates by: F(1) = 2; F(2) = 6; F(3) = 14; F(n) = F(n — 1) + F(n — 2) + F(n — 3) C's degree equal to F(n) + (2 * n — 6)

Is my solution right? I got problem with Fast Computing "Tribonachi's"

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

anyone can help me ? my code in problem B get wrong on test 23 But i test it locally and i get it OK

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

Congratulation to puyu_liao

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

Make it unrated

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

    Its impossible. There weren`t any technical problems on CF during the round

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

For E,I have an idea.

It's easy to calculate the power of f1,f2 and f3.I have a way to calculate the power of c easily. The transfer matrix:

0 0 1 0 0

1 0 1 0 0

0 1 1 0 0

0 0 1 1 0

0 0 0 1 1

By using this,we can change [a,b,c,d,e] into [b,c,a+b+c+d,d+e,e]

The formula of the power of c is f[i]=f[i-1]+f[i-2]+f[i-3]+2*i-6

Let a=f[i-2],b=f[i-1],c=f[i],d=2*i-6,e=2

So now we can transfer it.

The initial matrix is [0,0,0,2,2],because f[1]=f1*(c^0),f[2]=f2*(c^0),f[3]=f3*(c^0).

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

It was what I worried about. If my country's users set problems for the first time and there was some factors that can be issue, next time my country's (other) users set second problems, people won't expect much.

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

    For your information, I am not the first Korean problemsetter.

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

      I see. Anyway, because it's been a long time since there was Korean problemsetter, more prudence should have been.

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

    ainta and .o. set the best Codeforces Round in the history of Codeforces ever, so it's OK.

    On a serious note, I think the round was nice. B is cool for Div2. D is quite interesting with strong pretests. Difficulty distributions are bit flawed, but it's fine if D/E was swapped, and you can see scoreboards anyway.

    (I actually didn't liked problem F, because one can just copypaste NAIPC 2019 D and play with some stupid binary search. but the model solution was easier, and I think it's not an issue for 99% of participants..)

    In the end, difficulty distributions are not something setter can guess correctly, and interesting problems are much more important. For every CF round, there is someone complaining about pretests and distributions, I just advise to ignore them :)

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

      I, also want to think that way, but since that contest was over before more than 4 years, and since that there was no contest in which Korean was main problemsetter, for users joined after that contest this was like the first Korean problemset contest. It is also true that there are still many chances.

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

Well balanced problem set, nice.

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

problem c: is it valid? this first wow i .

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

Can anyone provide me a clear explanation on D? I thought many things non of them worked properly/on-time.

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

Guys, what is the time complexity of rating changes calculation? Why does it take so long? Can't wait already =)

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

E can also be solved using Reeds Sloane Algorithm(extension of BM for non-prime modulo). Link

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

Test case is weak for problem C, there is no case present in the systests where no. of vowels of a string is more than 100000. I used that number as an array index in some part of my code, got AC even after I miss sized the array.

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

    Exactly. In my solution too I used an array of 100000 for storing the strings with number of vowels. I was sure that my solution would fail at system testing. I was shocked to see it passing. So yeah, Weak Test Cases For Problem C.

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

    I'm sorry about issue.

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

Anyone who can take a look at my solution for E? 55469911

I have no clue why it passed on small range input but failed on the bigger ones.

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

Attention!

Your solution 55457716 for the problem 1182C significantly coincides with solutions Athena_1111/55457716, Anti-Mirzayanov/55458879, gandhipaaji/55458903, shreyanshgeek_unofficial/55458966, Harsh_jiit/55459119, turtle407/55459150, kaptaan/55459742, firefox/55459961, shivansh100/55460142, Izanagi/55460447. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.net/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

I just got this message. I want to clarify (especially for people who are not aware of that) that I was using the online compiler ideone.com (I was using it for the past 3 contests and nothing wrong had happened before) without knowing that apparently my code was public (I didn't even know that this feature exists). I have not copied the code of anyone!! You can check the timing ( MY SOLUTION WAS SUBMITTED FIRST & I AM 100% SURE AND RESPONSIBLE FOR MY WORDS). I have written every line of this code!!! I haven’t even used functions from any website. It really pains to receive this message in the first contest where I do well. What a luck!!!!!!! :/ Be just.

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

Why was I skipped in Codeforces Round #566 (Div. 2), but counted rating.

HELP!HELP!HELP!

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

I wonder if there's a solution for D using tree hashing, which I tried but failed.

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

shit. load shedding caused my specialist dream.

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

stupid Solution for D:

There are two possible types of vertexes, corresponds with the statements of the task:
1. One of the leaves
2. Vertex in the "middle" of the tree.

If there is only 2 vertex -> answer 1
If there is only 2 leaves -> answer is one of them

First of all, let's run bfs from each of leaves, and mark all the vertexes with their depths.
(depth[leaf] = 0, depth["middle"] is the maximum). Now, if vertex with maximum depth is unique, lets check it.
After, we need find one vertex with degree greater then 2 (it is always exist because of quantity of the leaves). Run bfs2 from it.
////Let's define nearest vertex with degree greater then 2 for current vertex like a good.
In this bfs, we need mark all vertexes by the pairs = {distance(current vertex, good vertex), index of the good vertex}.
It easy to proof, that if answer is possible, than there is only one leaf with unique pair {distance to its good vertex, quantity of leaves that correspond for this good vertex}. Now we just need to check this leaf.
code: 55487910

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

Why is my code for E giving wa on test case 5?

Got the error ignore.

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

weak tests for D
test
9
1 2
2 3
3 4
4 5
2 6
4 7
3 8
8 9
answer should be 9
https://codeforces.net/contest/1182/submission/55494688 gets AC but it shows -1 for this case.

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

    OMG I am really sorry about that. I handled almost ten type of trees and it was not enough.. :(

    UPDATE: Added that test in data

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

    I added that data and rejudged your case. I will try to find the way to rejudge all other's unofficial submissions. Thank you.

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

Regarding question C during the contest I submitted first one Then I found a small mistake and changed it to second one. If you compare both submissions the change was a variable n for a constant value. It was accepted, but then just out of curiousity I resubmitted my first submission third one you can compare it with my first one and it is literally the same, and I got AC with this.

However this is clearly wrong I mean you can test it with a small case ( 4 aaaaa aaaaa aaaaa aaaaa) My first and third submissions return 0 which is wrong and my second one returned 1 which is correct. So I'm not complaining about the fact that I lost points by fixing something that was wrong but would have been accepted anyways, I'm just wondering maybe the test cases are really weak or not good enough.

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

    I am so sorry about it. I should try so many various selections...

    UPDATE: Added that test in data