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

Автор laoriu, 10 лет назад, По-английски

Hello everyone!

Today, there will be another CodeForces Round at 18:00 (Moscow time). It is a Div. 2 contest, but Div. 1 participants can take part out of competition also.

My name is Vuong and this is my very first CodeForces round. Hope that this is not the last one. I would like to thanks Maxim Akhmedov(Zlobober) for help me preparing the round, Maria Belova(Delinur) for translating problems into English, and Mike Mirzayanov(MikeMirzayanov) for such a great Polygon and CodeForces.

Be sure to read all problem statements before contest ended. Hope you enjoy the contest.

Good luck and have fun!

UPD The contest is over! Thanks all of you for participating!

Here is top 5 participants:

  1. khykhm110
  2. My_First_Lady
  3. Perditio
  4. AkatsukiPain
  5. s_z_l

The editorial can be found here.

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

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

Would Score distribution be dynamic?

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

Thanks for the problemset. Good luck to all! :)

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

I can go to bed before the system test over!!!! Because my university will cut off the electricity at 11:30, and my computer can last for only 3 hours without outer-power! What nice news!

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

If I'm not wrong, this is the first round set by a Vietnamese! Good job! :)

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

I have been wndering....how many languages does Delinur know?? :D

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

    Usually, problem statements will be written in English, if the author wants it to be put in an international site.

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

    I know don't the exact answer. But one day during a conversation, she said this "But I can translate your message into 4 other languages if you want :P". It means that she knows may be 5 or 6 languages or more.

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

22:00 is good time for me to participate. Thank you for your contest.

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

    You didn't even register for the contest

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

      I went to register page at least 3 times but failed to register because of some network problems. After coding problem B, I realized that I didn't register for this contest.

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

I hope codeforces won't be down today :S

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

Countdown time and Announced time are Different. I am confused.

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

I wonder will the time be at 18:00(MSK) in the future or 19:30(MSK) for mostly?

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

    I hope most rounds are on 18:00 MSK in the future. That 1-hour switch has really some impact on us(Chinese).

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

I think :
codeforces Round 277(Div. 2)== Happy Birthday contest !!(for MikeMirzayanov's daughter)!!:)

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

i wish we won't have hack or other problems in this round

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

I bet that there will be one more blog post by DmitriyH after this round.

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

Punish him/her please! (S)he wants solution

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

Кто-нибудь до раунда читал вообще русские версии условий?

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

How to solve C ????

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

    You always need to fix only a half of a string you are staying at.

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

      I did exactly that. Got WA on pretest 2. I am sure its a silly mistake on my part. :(

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

      But How to do it by minimum operation ?

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

        Assume we are in the first half of a string. You are to find the segment which you must fix (leftmost and rightmost positions in the first half). Now you can choose the best way to visit all the segment, there are only two of them:

        right - pos + right - left and pos - left + right - left

        Of course, you also have to do min(abs(s[i] - s[n - i - 1]), 26 - abs(s[i] - s[n - i - 1])) operations for every i=1..n/2

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

          What if both left and right are on the same side of pos?

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

            You can take the absolute values, giving

            min(abs(right-pos)+right-left,abs(pos-left)+right-left)

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

              Well, my implementation ( 8656932 ) was a bit different. So I had to give that extra check, where both left and right were on the same side of pos. Lelby also gave that check ( 8659477 ), but he commented differently. That's where I got confused.

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

        You have to move from first char which needs to be fixed to the last one (or opposite way if shorter).

        For example if number or fixes for characters in string aaaaacdefg is 0, 3, 4, 5, 6. Then if you are on position 2, you move to position 5, if in position 3, move to 2 and then to 5 and if on 3, then move to 5 first and then to 2...

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

        We need to operate only with one half of string. Consider we choose left one. If p > n/2 just reflect it. Them found two indicies — 'l' first letter which need to change and 'r' — last letter which need to change. Minimum action for movement will be min(r-p,p-l) * 2 + max(r-p,p-l) if p inside [l;r]. If p is outside first we need to go in this range. Now we know how much ticks we will spent only on movement, during this movement we'll be on each letter. So just calculate cost of each change in range [l;r]. Result will be movement cost + change cost.

        O(n)

        I hope my approach is right :)

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

How to solve D ?

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

    Define root of a set as the node with minimum (av, v).

    Now we can consider all the sets with that root (each of them will be counted once).

    It can be done via simple dymanic programming.

    http://codeforces.me/contest/486/submission/8659287

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

    Take a fixed minumum number low then maximum value is low + d.

    Find number of sub trees which has at least one node with minimum value and does not has any node that bigger then low + d or less then low. It can be done with dynamic programming in O(N).

    Overall complexty is O(ND)

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

    Thank you both very much! I've got it.

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

Идея решения по Е:

  1. Ищем первую (такую, что её элементы максимально сдвинуты влево) наибольшую возрастающую подпоследовательность.
  2. Берём правый элемент и пытаемся найти справа элемент, который может его заменить в подпоследовательности. Если получается, то и элемент и все элементы, которые могут его заменить — 2. Если не получается — 3. Заменяем данный элемент самым правым.
  3. Повторяем второй пункт для всех остальных элементов по очереди.
  4. Если какой-то элемент не получил 2 или 3, то он 1.

Не смог реализовать, потому что не знаю как оптимально искать наибольшую возрастающую подпоследовательность; как быстро искать все элементы, которые могут заменить данный; устал и хочу спать.

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

    В последовательности 3 4 1 2 этот алгоритм не работает. Правый элемент 4 подпоследовательности 3 4 никуда нельзя сдвинуть, однако 4 содержится не во всех наибольших возрастающих последовательностях.

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

      Ну вот еще одна из причин, почему я не стал писать это решение)

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

Why some people didn't get overflow in first problem when they calculated sum of first n div 2 even numbers and calculated sum of first (n+1) div 2 odd numbers?

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

    I don't know. I made an unsuccessful hack because of this!

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

    It overflows, but both overflow the same, so when they subtract the overflow is gone. If you can find a case such that one overflows but the other doesn't (very unlikely and might not exist because 1018»1015), I think their solution will fail. I spent the last 15 minutes on W|A (Wolfram Alpha) trying to do just that, but haven't succeeded. A program would probably do it faster though.

    EDIT: Actually I think now that even if one overflows and the other doesn't, subtracting them will again mean the overflow didn't matter. 281474976645119 makes one overflow and the other not, but it still works as the overflow is ignored.

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

    let's hope for system testing!

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

    Apparently some solutions failed for the input "3037000499"

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

      This doesn't seem to break one solution I'm looking at. Can you show me a submission that fails it?

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

        This one fails (i failed to find this test in time). 8652729

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

          Ok thanks. It's different because they find the sum of all numbers and subtract twice the sum of the odds, and since they divide by 2 after overflowing, subtracting no longer always removes the effect of the overflow.

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

How to solve problem D(problem D is very hard!!)?

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

    My sol is to DFS each note as that node is the max node, then use DP.

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

    Every valid set can be uniquely determined by the smallest node in it.(If there are more than 1 node has the smallest value, we choose the one who has the smallest id). So let's choose an node to be our special node, and starts to dfs under the limit that our special node has the smallest val and smallest id and the gap is no more than d. We get a sub-tree of the original one. And considered sub-tree, You can use dp to count how many way you can choose a set which contains the root (our special node)from the sub-tree.

    It's a classical dp problem on trees. dp[node] means the ways to choose a set which contains the root and the others node come from the sub-tree of it. And you want to calculate dp[x] for the the node x, you just go through his son, and we can either not choose the part from this son's sub-tree or just take it, which has dp[son] ways. So in total (1 + dp[son]) ways. Multiply the sons choices up. And we get the ways to choose a set from the sub-tree of x which contains the node x.As we can let every node in the tree to be our root(special node), we can get the answer for the question.

    Check my code hope that helps.

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

A was easy, B was interesting, C was time-eater and interesting too.

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

+100 to persistency

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

 img

Ban Samsung please.

Translation: he asked me to send him solutions of A, B and C

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

    wow the request is so interesting

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

    this site has no report system?

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

    Did you sended him smth? No? There is no reason for ban then. Yes? Then both should be banned.

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

      I don't think temak would've asked to ban him if he has sent something o_o

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

        It's very same situation as — "You got SMS message: 'Mom! Please, send me 300$ to X-XXX-XXX-XX-XX I'm in big trouble!!!'. You can ignore it, and then there is no criminal. But it's possible to find the owner of this number, send the money and then arrest him, because his attempt was succesful". So there is no chance that Samsung will be banned, because solution wasn't sent! But still, temak posted this image and waiting for something.

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

    that's why Iphone better than samsung:D

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

дорешиваю codeforces training season 2 episode 7.

внимание вопрос: это специально так сделано, что пока идут систесты, ничего другое не тестируется?

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

    У попыток одинаковый приоритет. Вперед тестируются те, которые были сделаны раньше.

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

how to print negative number (A problem) from squee_sp00n's A

if(n&1){
			cout<<"-"<<n/2+1<<endl;
		}else{
			cout<<n/2<<endl;
		}
»
10 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

It seems that nobody solved E using large prime modulos like me.

What was the intended solution?

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

    I solved it in that way :)

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

    I think it is to count the number of indexes belong LIS of length i :) If there is only one index of length i then it must be type 3, otherwise type 2.

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

    Could you explain what do you mean by "large prime modulos" ?

    I solved it simply using segment tree for some calculations.

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

    Quite surprised there's an antihash testcase for 2^64 modulos :|

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

      While constructing testcase for string hashing is not so easy — hacking similar solution for this problem is very easy (and it is well-known olympiad problem). Just take a look at sequence 2 1 4 3 6 5 8 7 10 9... How many LIS it have? :)

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

        Yes, i realize it's not hard to make such testcase, my bad for assuming anything modulo something is hard to hack :)

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

Will the contest also be unrated as the past contest???

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

    No :)

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

    Don't think so. Last one was unrated because of problems with servers etc. Rankings are just always updated few hours after the contest.

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

Sigh

Top4 are once again unrated, two of them registered in the past 24 hours. I'm not saying they are cheaters, but that happens way too often lately :\

Awesome problems by the way, solved all 5! Thanks, author :)

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

why getting wa in test case 16 in 486A - Calculating Function .. my soln 8655625 it gives correct output in my compiler

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

I HAVE A COMPLAIN IN CONTEST IT SHOWS PRETEST NOT SHOW WRONG OFTER CONTEST ITS SHOWS WRONG ANSWER WHY YOU WOULD NOT SHOW AT THAT TIME?

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

    Welcome to CodeForces :D

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

    PRETESTS =/= TESTS, obviously.

    This is the format of the competition. Your solution is tested on some part tests that usually do not cover all corner cases and maximal constraints. After the competition your solution is graded on the official tests.

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

    pretests are a very small fraction of the entire test

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

    I don't know the exact reasons, but if I need to guess, there are probably three reasons for that:

    1) Because of pretest/test separation, there's less need of computation while we're in contest; that's why we can get faster feedbacks.

    2) It's much more exciting and fun to wait for system testing to see your actual results.

    3) Hacking mechanism is based on this feature; this is also related to second reason since hacking is fun.

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

      what a joking u its not fun always you show wrong answer at contest but today you cheat me it;s not fare.I wana my full points its your mistake not mine otherwise i'll never participate in your contest

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

    This is not your first contest, right? There are few tests when you submit, but all tests are tested during system tests...

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

this contest is unrated ?

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

that My_First_Lady seems to have used different templates on C and E. and submitted C after E in two minutes.

just saying.

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

    Yes, that's very suspicious indeed. Sadly I've never seen anyone banned for such reasons which is why we have tons of unrated accounts and/or teams ruining top5 of Div2.

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

Очень понравились задачи. Получал удовольствие во время решения задач. По чаще бы таких раундов! )

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

see this two code for 1'st question whats differnt.

include<stdio.h>

include<math.h>

int main() { unsigned long long int n,i,j,k; scanf("%lld",&n); if(n%2==0) { i=n/2; k= i*(i+1); j=-(i*i); printf("%lld",(k+j));

} else { i=n/2; k= i*(i+1); j=pow((i+1),2); printf("%lld",k-j);

}

} 2.

include<stdio.h>

include<math.h>

int main() { unsigned long long int n,i,j,k; scanf("%lld",&n); if(n%2==0) { i=n/2; k= i*(i+1); j=-(i*i); printf("%lld",(k+j));

} else { i=n/2; k= i*(i+1); j=(i+1)*(i+1); printf("%lld",k-j);

}

} but first shows wrong answer and second shows correct answer what the difference between them

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

    ...

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

    In case the guy really doesn't understand smth and not trolling: The first programs uses pow function (http://www.cplusplus.com/reference/cmath/pow/) The declaration of this function: double pow (double base, double exponent); — that means result for even integer numbers could be 255.99999999999 instead of 256 since for float(double) numbers those values are pretty same. But here j=pow((i+1),2) you're doing cast to integer. So result could be 255 instead of 256 and no one can guarantee which one exactly.

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

Most of the solution failed test case 31 and 39 for problem B. They didn't know when to say NO :P

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

Heh, had solution for C, but just assuming that there's only one turn, not that the cursor always remains in the first half. Much more complicated to write that way : S

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

codeforces should try to improve their website performance during contest..

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

8652439 Why can this solution for problem A can pass all the data? It is an O(n) solution!

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

    The loop

    for (int i=1; i<=n; i=i+2)
     s=s+i-i+1;
    

    is so simple, that compiler (with optimizations on) turns it into

    s = s + n / 2
    

    because loop is really just incrementing s by 1 on each iteration, and we know precisely the number of iterations. Thus it becomes O(1) solution.

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

      oh...One of my friend attempted to hack this solution with a big number... two unsuccessful hacks... Sadness

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

Why my solution to A 8652258 passed all tests? It almost wrong. Can someone answer me

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

Country wise rankings table has been updated

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

Mind if I ask why 4 out of 5 top are unrated?? I wonder if multi account is OK!

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

Why the next round will be called "Codeforces Round #277.5 (Div. 2)", not "Codeforces Round #278"?

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

    Because next contest that will be after 7 day called "Codeforces Round #278", "Codeforces Round #277.5 (Div. 2)" was created after this contest, and will start earlier