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

Автор GreenGrape, 3 месяца назад, По-русски,

Привет, Codeforces! Давно не виделись :D

Codeforces Round #461 состоится в среду в 20:15 по московскому времени. Обратите внимание, что раунд чуть позже, чем обычно.

Раунд будет рейтинговым для участников из второго дивизиона. Первый дивизион тоже приветствуется, но вне конкурса :)

Спасибо Коле (KAN) за координацию раунда, Грише (gritukan), Олегу (x3n), АмирРезе (Arpa) и Сене (senek_k) за тестирование и, конечно, Майку (MikeMirzayanov) за Codeforces и Polygon. Отдельная благодарность отправляется Диме (mitterr1999) и Камилю (pseuda) за идею одной из задач.

В этом раунде вы будете помогать игривому монстрику Импу. Не пугайтесь, условия будут короткими!

Задач будет шесть со следующей разбалловкой:
500 — 1000 — 1250 — 1500 — 2000 — 2750

Удачи!

Обратите внимание, раунд перенесен на 40 минут, чтобы избежать пересечения с раундом на CSAcademy.

UPD. Контест закончен.

UPD. Системное тестирование окончено! Разбор.

Поздравляем победителей!

Div. 2:

  1. sorry-haghani
  2. spec4r
  3. SashaShlyapik
  4. belic
  5. 4783992

Div. 1 (unofficial):

  1. dotorya
  2. Vercingetorix
  3. dreamoon
  4. kmjp
  5. FCB1234

UPD. Выложены разборы D/F.

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

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

Really loved your last round but hopefully this time, there will be a better difficulty distribution in the problems!

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

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

Возможно, там опечатка. Грише*, а не Гришы. Извините, что докопался :)

UPD: исправлено.

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

Когда в ближайшем будущем не завезли раундов в удобное время...

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

codeforces contest is always great and amazing , my bad , may be i will not be able to attend this contest due to travelling , missing it so much :( :( :(

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

codeforces contests are always great and amazing , i always try to attend the contests , but my bad , may be i will not be able to participate in this contest due to some travelling stuffs , and it is much painful for me , competitive programming is my passion

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

Ohh god CM problem setter again.

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

The names of the problems will be about colors of grapes?

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

Is there a relation between the name of the problems and some colors of grapes? :O :D :)

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

Is it rated?

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

Obligatory comment: "Hope the problem statements are as short as the announcement"

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

Have seen you being quite responsive in the last contest. Keep up the good work, and well, wish a quality and balanced contest ;)

P/s: Yup, I still can't figure out the most optimal income when using Perun's ult xD

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

x3n

Хоть кто-то живет в 2к17 году.

PS. Если что я говорю о GreenGrape.

PSS. Если вы еще не поняли нажмите на x3n

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

Thanks a lot for this timing

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

Oh... This contest is even later than others T_T

Too bad I can't enter it because of... time zone problem...

Wish you guys good luck and high ratings anyway ^_^

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

Этот раунд рейтенговый?

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

    Переведя шутку на русский, не заставишь ее звучать по новому. Это так не работает.

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

I hope my rating will be more than 1900. Then this contest is unrated for me. I don't like rated contest. My rating will down if I don't do well in this contest. CONTEST, CONTEST and CONTEST ... RATING, RATING and RATING ... TRAINING, TRAINING and TRAINING ... ......

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

Thank you guys, who create codeforces contests. They have really interesting problems. Live long and prosper. :)

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

Good luck to all

let's see, can i be a Candidate master at the end of this round or not ...

wish me luck... :)

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

So sad that magic is over, can't troll with different colored grapes anymore :(

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

I wondered what is different from participant division 2 and division1

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

really awesome, wait for some blossom

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

A prime number contest!

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

not u again

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

How to download Test #15 of 650C Table Compression?

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

    Unfortunately , the large inputs can't be previewed completely. if you stuck with the problem you can see the tutorial of the contest (here). if you still stuck , you can check out the Accepted solutions (here).

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

"Yet the statements are guaranteed to be short :)" this is the best announcement so far.

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

Yet the statements are guaranteed to be short :)

Thank you very much:)

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

"Не пугайтесь, условия будут короткими!"- то чувство, когда раунд не от adamanta...

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

Unusual early scoring!

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

"Codeforces и Polygon"

Learning some russian.

Learning everywhere. :)

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

    Learning so much that you start to understand Croatian. (Source: COCI 2016/17 Round #6 solution, p. 4, line 8)

    Let Pa < Pb i k * Pa ≤ Pb < (k + 1) * Pa.

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

Hope another great problem set from this amazing head. Big chance to rise up. CF is too good to stay away from. :)

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

Can anyone help me with one problem? I have good answer on test 2 on my computer, but on codeforces I get WA no matter what I do. Obviously compiler settings or something isnt same. Just visit my problem and check last submissions, problem C from few rounds before. 34983468

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

It's quite strange no one noted that this round coincides with CSA round #68 tomorrow! Can't you just delay it 30 more mins? GreenGrape

UPD: the contest is delay 40 mins!

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

Glad to hear this: Yet the statements are guaranteed to be short :) Looking forward to it !!!

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

How to download Test #15 of 650C Table Compression?

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

    Okay, this should be the last time I see this anywhere.

    You cannot do that. At all.

    (Well, except if the problem setter provide the full package publicly).

    For convenience, all test cases are compressed in case they are too big, so large input/output files are near to complete omittance.

    Usually, if you get stuck with a big tests, it can only mean a few things:

    • You ran out of memory (MLE verdict).

    • You ran out of time / your algorithm was too complex (TLE verdict).

    • You handled the undefined behaviors poorly (WA/RE verdict).

    These tests are mostly used to tests how a code works against large input streams, and not to be corner cases, so please check your own source code for places that can be optimized, not just spamming the blogs all the time.

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

Normal guy's Imp.

Codeforces member's Imp.

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

Is it legal?

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

I am gonna solve A, B and C today !

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

Wow :O Rounds

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

Two line summary of the announcement :
1. The statements are guaranteed to be short :)
2. There will be six problems with the following scoring: 500 — 1000 — 1250 — 1500 — 2000 — 2750

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

The time is a little late for me,but I am still glad to take part in the round.

It's really a good chance to train myself. :)

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

I just want to say it's too late for Asian contestants . Hope I will stay alive for being such late......

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

    One hour earlier, but yeah, I feel you, dude...

    12:15 AM in UTC+7 (Hanoi, Vietnam). Uh-oh...

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

Hope I can become Expert!

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

Sanwli saloni, adaayein manmohni Tere jaisi beauty kisi ki vi ni honi Thande ki botal main tera opener Tujhe ghatt ghatt main pee lon Coca Cola tu ROUND GONNA BE AMAZING !

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

    You Should Behave On website like codeforces , though fun is necessary , but people seach for good comments over here . I hope you understand it ! Good Luck for contest .

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

Let's see How this go?

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

i think i will be green this time,thank you GreenGrape.

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

is it rated??

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

can't wait.....

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

Again a round with near 7000 participation :)

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

I hope the long queue is fixed before the contest starts

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

    I hope the int vector is fixed setprecision(10) after the contest end ;!

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

Hope to solve at least one or two problems this time my rating sucks.

»
3 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
How's this possible?!
  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    What's wrong? I thought you can lock the problem as long as you have the "Pretest passed" verdict, irrespective of whether you get hacked or not. Correct me if I am wrong.

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

      Nope, you can't lock after you got hacked. But I think it happened because times are very close.

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

        Oh okay, that's interesting. This probably happened because of the long hack queues today.

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

Contest of hacks... :D

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

very long queue in hacks

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

HackerRank will be proud of this contest

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

I think this contest are more "Successful hacking attempt" messages than "Accepted"

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

A round full of hacks. Even one of my friends hacked me, nice contest

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

Hackforces in a nutshell...

Anyway, to be serious, maybe it was just me, but I think the scoring is still a little bit underrated. This should be 500-1000-1500-1750-2250-3000. C is sufficient to be called a Div2C, D is somehow quite twisted (got 4 WAs verdict on the 4th problems, all on pretest 4).

Not really sure about my opinion about E and F, coz' I have just read it for a short while.

After all, it was fun actually. And these Imps are just cute ^^

UPD: I took my words about D back. Somehow I wish I could think sharper...

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

Can someone please provide explanation for third testcase of problem E.

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

    I think you are confused just like I was — summoning a bird doesn't increase your mana, it increases you maximum mana.

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

    Take 1 bird from the first nest (you don't have enough mana to take two birds), take 10 birds from second nest (your mana capacity is 17 and you have 15 mana so you can take them all).

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

Problem D is solvable with radix sort?

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

    I just used normal sorting with a comparing function that returns numS[a] * numH[b] > numS[b] * numH[a]

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

      Hell man! :'( I tried to do it with normal comparison too but that condition didn't pop up to my mind! How can you prove this works ?

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

        Given a string s, denote f(s) to be the number of subsequences 'sh'.

        Now given strings s1, s2, ... sn, it is easy to prove that if we denote xi, yi as the number of 's' and 'h' in string si, that .

        To maximize our desired value, all we need to look is the value .

        For n = 2, it's trivial that the comparing function wewark described works.

        We will induct on n — say the comparing function works for n and we prove it works for n + 1.

        Clearly, , as after deciding which sn + 1 to choose, we are left with optimizing the value with n strings. (induction hypothesis is used here)

        Now, all we need to do is prove that we need to put sn + 1 as the string with the highest value. This is simply greedy, easy to prove.

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

        Let's assume we have two strings a = sshhh and b = ssshhh.

        we can do a + b = sshhhssshhh.

        And b + a = ssshhhsshhh.

        How many sh's we got after this concatenation?

        We can note that this value is numS[a] * nums[b], because we didn't lose any sh's that were in a or in b, so what we got is .

        The same logic works for .

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

      Do you have a formal proof of such comparator?

      UPD Just came up with your idea.

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

      Got it, thank you all.

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

The 1st problem made for the hack..

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

Idea behind C ?

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

    For small Ks (probably <= 1000) you will find two exact values, so just implement

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

    just do it with brute force :)

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

      Ok. Limits are very large so how do you guarantee fast running time ?

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

        it will find a pair soon

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

          Thats what my questions is. How to prove that ?

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

            It is known that (a very important consequence/equivalence of prime number theorem) .

            For n, k to be good, (n + 1) must be a multiple of . So n must be like ek.

            This should be good enough, as running time is .

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

              Or, say primes >10 will multiply, so it be over 10^18 fast...

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

              Bruteforce works. :)

              This was my approach.
              gcd(1,2,...,k) = 1

              Therefore, lcm(1,2,...,k) = 1*2*3*..*k

              Also, since the remainders have to be distinct, one observation is that for any i between 1 to k, n%i should be equal to i-1.

              This means: n = i*C + i-1 ==> (n+1)%i = 0.

              Therefore n+1 should divide all the numbers from 1 to k. This also means that n+1 should be equal to the least common multiple of 1,2,..,k (in this case its just the product.) or any multiple of this lcm.

              Looping from 1 to k and stopping the loop whenever product crosses n+1. Product crosses n+1 easily by the time we reach i=50 in the loop. We return "No" in this case.

              If k! is equal to n+1 then we return "Yes"

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

        try this

        bool f;

        int top=0;

        for(int n=1;n<=100000;n++){

        for(int k=1;k<n;k++){

        f=true;

        for(int i=1;i<k&&f;i++){

        for(int j=i+1;j<=k&&f;j++){

        if(n%i==n%j)f=false;

        }}

        if(!f){

        top=max(top,k);

        break; }}}

        printf("%d\n",top);

        just look at the output and you will find out why it is possible to do it in brute force

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

    People have this idea:

    Since you need to have all unique values till k. They should be obtained serially from 1,2,3,..k like this: 0,1,2,3,4,5...k-1

    so, n should be of the form: 2x+1, 3x+2, 4x+3, 5x+4, 6x+5, 7x+6,... all at the same time. But if something is of the form 5x+4 .. it cannot be of the form 2x+1 .. (coz one is odd and other is even, for even x, similarly chose a pair for odd x)

    Edit:

    The conclusion seems flawed. Maybe we can continue the logic like this:

    Number has to be of form: 2x+1, so 3,5,7,9.. 3x+2, so 5,8,11,14.. ... ....

    It kind of creating a sieve of eratosthenes, which generates a prime number.

    I don't what that gets us :)

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

Locking after being hacked

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

how to solve D?

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

    sorting : )

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

      merge or bubble

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

        consider to string a and b

        let the number of 's' in a be a.S and the number of 'h' be a.H

        if you arrange a and b be ab

        the you will get a.S*b.H pairs

        so we know that if a.S*b.H>b.S*a.H then a should be in front of b

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

What was the hack for A?

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

Мне, как пожилому гроссмейтеру, контест заехал, a особенно чудесная задача В, на которую я потратил 70 минут)) xDD 8==э

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

Problem A just burn my room

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

What is wrong this this solution for E?

Let dp[i][j] be the max mana we have at tree i with j summoned in the trees before us. The max capacity is always w + j·b for a fixed j so we don't have to store that. I used long long int here and for dp table so no overflow. The answer is the largest i such that dp[n][i] is valid. I kept getting WA on pretest 5.

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

How to solve B? Seems easy cause lot of people solved it, but I only solved C and D.

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится
    ans = 0
    for a = 1 .. n
      for b = a .. n
        c = a ^ b
        if b <= c <= n and a + b > c
          ans++
    print ans 
    
    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Wow.. I'm a fool :) Thanks for your reply! (And all the others too)

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

    can you please tell me how to solve C?

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

      Try 1~50

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

      n mod 1 , ... , n mod k has to be different. but you can easily notice that n mod 1 is always 0. So, n mod 2 must be equal to 1, because n mod 2 is 0 or 1, but it cannot be 0. ... n mod i must be equal to i-1, which means that n+1 is divisible by 1, 2, ..., k.

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

    For a <= n, b <= n, let c = a ^ b, if all other conditions hold, then increment answer

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

    a^b^c = 0 implies a^b = c. So bruteforce for a, b, and check if the 3 numbers can form sides of a triangle.

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

    You can iterate through all possible cases of a and b. c can be calculated by bitwise xor:

    As a xor b xor c = 0, we can agree that c = a xor b.

    If c is not lower than a or b, and not greater than n, and a,b,c forms a non-degenerate triangle (simply check that if all 3 inequalities of triangles are proved right), then you can add 1 to the answer.

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

    Simply iterate over all a, b values . Check a + b > c, a + c > b and b + c > a

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

    I actually passed it with brute forcing which is O(N^3). It gave me 780ms even though it doesn't seem to be the intended solution.

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

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

Test for hack C: 1 2

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

How to solve F? I tried taking all N numbers initially and consecutively removing the one which will decrease f(I) the most but such that f(I) ≥ k will remain true. Just plain intuition, didn't work.

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

    I bruteforced n<=17, implemented it for larger n, it worked well for all local inputs. Still kept getting TLE on the 7th pretest. I just wonder whether it was my complexity, I/O, special countertest designed to make this kind of solution fail...

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

    Explanation — Problem F

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

      Man, them noise and echo are simply unbearable which makes your speech unrecognizable.

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

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

In question D, what is the pretest 4?

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

I think there should be a limit on the number of hacks for each problem... Yeah hacks are a part of CF, but when a hacker with ABC has more points than a non-hacker with ABCD, I think there is a problem.

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

Can anyone give me some idea for 922F - Делимость

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится
    for i = 1 .. n
      for j = i .. n, j += i
        d[j]++
    if sum(d) < k
      print no
    otherwise, kick out some numbers > n/2 - since they do not have multiples - so  that number of pairs will decrease to k
    
»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

В общем контест был отличным. Но в задаче А многие не учли что при x>0 и y==1 ответ No.

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

can someone help me find why i was hacked in problem C? 35018691

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

Short statements not means a lot of hacks.

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

This was the biggest slaughter since I started to participate at contests

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

omg, it was great. hope i'll see you contests later. GreenGrape, live long and prosper.

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

When will the system testing start ?

Update: System testing started :)

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

When someone asks how life is going on?

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

While everybody is discussing today's contest, I just found my love <3

Thanks Mike :)

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

Isn't it obvious that current hacking system sucks? It's a brilliant idea, but really bad realization. Hacking should give you points (maybe even more than 100) if you find hidden not obvious bug in someone's code. But if you just take n = 0 corner case in div2A and it gives you 1500 points that's so unfair: you get that much points not because you are smart or your debugging skills are better than average, but because you have gray guys in your room who always do this mistake.

That's why I think that hacking points must be not a constant, but a function, which depends on how much hacks there are on the problem.

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

    if problem difficulty is 500 points so on one hack your receive 100 is 20% but if problem difficulty is 2500 points so on one hack your receive 100 is only 4%

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

    til i am a grey

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

    Agreed. I hacked 18 solutions (Problem A) using only two test cases And guess what? My own solution missed one corner case and I got WA in system test. But 1800 points gave me an unfair advantage.

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

Many among you would be disappointed because of all the hacks, but I feel that the problems were super exciting and I enjoyed all the brainstorming while getting hacked.

+1 to GreenGrape

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

 I don't know why, but my submission got stuck at test 39 for last 10 min.s. I am on page 6 of filtered list

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

When you find one of the testcases for A  hackerman.jpg

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

I think that there is a problem with D testcases. This is my AC submission.

The problem with my solution is that the comparison is made entirely on integers, and therefore it could overflow.

I'll try to generate the testcase, I think that:

2
sssss...ssssssh
hhhhh...hhhhhhs

is enough.

EDIT: oh yes, I think it was enough. My solution gave 50000, but when reversing gave 2499950000. I don't think I'm the only one who failed for this.

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

    That's actually quite strange since tests 11 and 12 are made exactly to counter this.

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

      I would like to remember that overflow is an undefined behaviour, so anything could happen, even getting an incorrect AC (A guess for why this happens is that the compiler may do some simplifications like x*y/x = y — avoiding the calculation that gets the overflow — maybe something in that line is what happened)

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

        I tested it using custom invocation, and it gives the incorrect output there (50k instead of 2499..etc).

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

      Oh, I think I know what's happening here. My submissions treats different the strings consisting of only 'h' or only 's', so that's why my submission passed.

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

    35024915 this solution gets tle on your test, if i am not mistaken. if so, D should be reevaluated

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

long long contest! #define int long long accept my C and D :)

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

Problem A states: "Initially, Imp has only one original toy. but system test 20 tests for 0 (ZERO)!!!!!!

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

    Print "Yes", if the desired configuration is possible, and "No" otherwise. so when input is 0 you should say no because he have 1

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

      I have read again the problem before seeing your reply and come back here to delete my post, but now i leave it. Of course you are right.

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

Can't believe my STUPID code for C got pretests passed even and finally failed on test 76th!!! I used k instead of i in my loop.

Failed.

vs

Accepted.

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

Couldn't proof the solution for C during the contest. But now, I think I got a proof.Correct me if I'm wrong plz.

If the answer for n is "yes", then for all i from the set [1,k] will have distinct remainders.

We can easily see that for all i [1,k]

n mod i == i — 1,

so, we can say (n + 1) mod i == i == 0 ;

That means all i [1,k] must divide (n+1) simultaneously.

Which means (n+1) must be divisible by the lcm(1,2,3,........,k).

Now the lcm(1,2,3,.........,k) would be > 1e18 when k is > 41(or something) .

That's why the brute-force solution worked.

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

ohuenniy round

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

who is sorry-haghani ?!

HAGHANI ...

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

Can anyone explain? :( 35036774 35011492

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

Solving the B in O(n^3) no problem... i would say a O(n^2) solution was intended but anyway: http://codeforces.com/contest/922/submission/35039399

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

 Hello, world!

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

Ironically,GreenGrape has never been green in his/her entire Codeforces history.

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

Why is my code giving runtime error on test 5 in D : Link

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

This was one of the best and most interesting contests on codeforces that i have given. So much of hacks and good difficulty distribution i should say ,awesome GreenGrape

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

раунд очень годный был

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

http://codeforces.com/contest/922/submission/35048494

why am i getting runtime error thanx in advance

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

GreenGrape has never been Green on Codeforces.