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

Автор Neodym, 10 лет назад, По-русски

Доброго времени суток! 20 августа в 19:30 по московскому времени состоится 262 (Div. 2) раунд. Участники первого дивизиона могут принимать участие вне конкурса.

Задачи подготовили 2 автора — Василевский Виктор(vitux) и Семченков Алексей (я). Мы приносим благодарность Геральду Агапову (Gerald) за помощь в подготовке раунда, Михаилу Мирзаянову (MikeMirzayanov) за удобные платформы Codeforces и Polygon, и Марии Беловой (Delinur) за перевод условий на английский язык.

В задачах раунда вам придется помогать разным хорошим людям. Мы надеемся, что задачи покажутся интересными участникам обоих дивизионов:)

gl & hf!

UPD: Будет использована стандартная разбалловка.

UPD2: Также мы благодарим Виталия Аксенова(Aksenov239) за правку русских условий задач.

UPD3: Приносим поздравления пятерке победителей:

1) buptcjj

2) 6wr1

3) ladpro98

4) shaojj

5) linjek

Также приносим поздравления jellygendut, который занял 20е место и решил задачу Е — ее решило всего 3 человека.

Никто не решил все задачи, но каждая задача была решена хоть кем-то.

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

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

The link to timeanddate is broken ;)

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

Brace yourself, newly registered users are coming.

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

Один из авторов ВК

Bredor заценит :) Наверное, в задачах надо сортировать банки с Ягуаром

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

пожалуста — поставте я хачю быть первым

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

Two consecutive Div.2 only rounds ! :|

Time for a Div.1 + Div.2 round :)

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

I think this is time to be pupil.. :D

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

Happiness is , checking the 'Contest' tab each alternate day, and finding a Codeforces Round there! :)

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

    sadness is to discover that the contest is div2 only

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

      Sadness is losing internet connection in the middle of a rated contest while you just want to submit a problem and having connection back as soon as the contest finishes! :)

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

        Happiness is to find out later that the solution you wanted to submit was actually wrong and thankfully you did not make any other submissions as well in the contest. Ratings saved -_-

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

          No, happiness is finding out that you actually submitted it somehow and got a REALLY high place because of it.

          And sadness is finding out that it failed on systest no. 124.

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

            As I see, happiness can be anything! :D Maybe we should create this topic: What is happiness at Codeforces?

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

            is that happened to you? Failing on 124 B(

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

              In Gym, once. But not in this "happiness/sadness situation".

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

    A lot of happiness and sadness theorem :p

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

A wave of "Black ID" ~ ~

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

    I don't know why your handle of codeforces is so special :|

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

      The first time when I used Topcoder Arena,I thought that "TopCoder" have a better message,so chose It.It is To Be Top Coder for me , but not for TopCoder,INC.##Too young at that time .~,~ ~,~

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

gl & hf :P 2 mny CHRs

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

The first Codeforces Android Application is now available on the Google Play Store. You can download it here-

https://play.google.com/store/apps/details?id=com.innsolutions.codeforcesstats

With this app you can do the following things- 1. User Info- Basic Profile Info, Rating Change History, Submissions History of any user. 2. Compare Users- Compare the overall info of as many users as you want or Compare Head To Head which lets you compare upto 4 users in Common Contests, i.e., contests in which all the given users have performed. 3. Search Problems- Search for problems by tags, index, name, contest id or solved count. 4. Search Users- Search by name, handle, organisation, city or country.

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

    sadness is , in our country we can't visit google web page,because of Great Firewall :(

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

    LOL! :D

    I try It Application. It seems to me that it's a completely useless app. Sorry.

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

      Hey knst no need to say sorry. You did not like this app, that's fine. This app does what it's supposed to do, whatever's written in the description. If those features are of no use to you, just go ahead & uninstall it.

      As far as the ad displayed there is concerned, i have nothing to do with it. Those ads are put there by Google & i had no idea these type of ads could be displayed. Well I'll remove the banner ad in the next update. Sorry for the inconvenience.

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

I have a question (I'm new to here.. I've attended just one round in Codeforces)

If I register this round, then I must attend the contest? so If I have a important thing to do, and I can't attend the contest, then my ratings will fall down?

(sorry for bad english :< English is not my native language...)

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

    Rating won't be changed unless you submit something.

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

      Aha! Thanks for your reply. I've worried about that..

      I'm a high school student in Korea, and the contest will be started at 00:30 AM in korea.. It's too late here :<

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

Time i move up to specialist or maybe Expert

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

gl & hf :)

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

Help me :( I am new here and I am not able to find any link to register for Round262. There's just date and time link but no registration link :/ Someone help me quickly, only 90 minutes left for registration.

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

Let's (not) hope for more math(!)

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

My first contest hope I get good ranking :D hue hue

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

oh,div.2!why two times?

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

oh,div.2!why two times?

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

Hope for all "beautiful" bruteforce problemset only and strong pretest :v

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

I think some of the people in Div. 1 are using some fake accounts to enter Div. 2 contests and because of this we can't rise. I think you should find a solution to this problem.

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

Let's have fun and enjoy codeforces!

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

what a hot contester:O

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

Scoring?

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

I've always had this question in mind.

When you click on Registered Users > Friends.

How are the users ordered? On what basis?

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

Sadness is electricity go out in the middle of a rated contest ! Egypt !!

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

WOW, a record in registrants 4824 :D

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

gl & hf

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

Over 4000 contestant take part in. This will be an interesting round!

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

hi can someone from codeforces look into it hightail gives it correct ans but it fails on pretest 1

sub id-7526210

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

Shame.

x

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

There are many newly registered users on top of standings... the same to what happened at recent contests...

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

Wasn't B harder than usual?

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

I think my solution of problem B will not pass system test, but i got 4 successful hack on problem B. :P

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

    the same :D

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

    What is the tricky test in problem B?

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

      writing your own pow() function :P

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

        Is it because of integer overflow?

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

          nope, precision error when casting to long long, pow() function returns double, just check this, cout<<pow(5,2), then after casting see this cout<<(long long)pow(5,2), returns 24 instead of 25

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

            I wrote my own pow function, and i failed the system test because of overflow. Anyway thank to you that now i know i should use my own function for pow for precision.

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

            Do you know how could i reproduce it in my computer? I get 25 and not 24 in both cases, I swear... When i run the testcase in which i failed in the final tests in my computer, it returns the correct result... I HATEE THISS!!!!

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

              it can return either 24.999999999, if you cast in this case, it would return 24. But it may also return 25.00000000001, and in that case you will end with 25 only after casting. There may be some case where it is failing. Try printing the float values in your submission.

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

              you can use the O(log n) implementation in pow

              a^n=a^(n/2)*a^(n/2) if (n%2==0) a^n=a^(n/2)*a^(n/2)*a if(n%2==1)

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

      Some people enumerate the x rather than s(x).Some people didn't consider all the answer should less than 1e9. Sorry for my poor English.

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

        Some people check s(x) in range 1..72, and I don't understand why.

        Are they really thought, that max(s(x)) == 72?

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

          They probably thought that 10^9 has 9 digits and 10^9 — 1 is 99.999.999, which has 8 digits. And 8 * 9 = 72.

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

          But one man in my room check s(x) in range 1..100 and check res=b*pow(i,a)+c in range if(res <= 1000000000) And it is clear solution... :)

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

            It is really a correct solution cause s(res) can't be bigger than 81

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

              It is correct; for s(x) ≥ 82, you will simply fail either the check s(res) = s(x) or the check res ≤ 109 all the time.

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

          I did max in range 72. Made the silliest of counting mistakes!! Green now!!

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

Кто-нибудь писал на B C бинпоиск по ответу + дерево отрезков или я один такой? :D

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

    может на С?

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

    А чем Вам не нравится перебор суммы + решение обычного линейного уравнения и неравенства?

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

    Я писал, но только в С)

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

      Но ведь ты не участвовал в контесте...

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

    Если С, то вместо дерева отрезков можно воспользоваться другой идеей. Будем держать счетчик, обозначающий сколько нужно добавить в текущем элементе. А также массив, для каждой позиции в котором будем хранить на сколько нужно уменьшить счетчик.

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

Lets make a predictions D's test #7 K equals 3 ..!

I only doubt on 3'Ks for my solution.

UPD: a bug found. maybe K equals 2.

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

What is the tricky test case for Hacking B ?

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

Problem B was so easy to hack! Just use (for example) "5 710 1" as an input for people who used int instead of long long :)

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

There was something wrong with pretests for the second question . I was getting the correct output on my compiler. But when I added if(x == 13726)cout << "" ;

I could pass the pretests I don't know why .
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

While I'm trying to hacking a solution by generate input using generator in c++ I see a line. ( I don't remeber it). I put -o2 but it doesn't work. What should it print in that line?

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

Can somebody please explain, why http://ideone.com/rbsIwP works on ideone, and not on the judge (or in codeblocks either). I wasted around 50 minutes wondering about the problem with my solution, and at last just gave a try to user defined power function and it worked. But why was i getting different results from two judges running the same compiler??

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

    If you used pow(), then note that this function works with floating point values and might not compute the exact answer. For example, pow(5, 2) might return 24.99999999.

    It is generally undesirable to involve floating point computations in places where integer math would suffice.

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

      Ok, I knew it returns double so used casting....but just carelessly ignored the fact that it might need a ceil function as well...will try testing with (long long)ceil(pow());

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

Contest is over ! I solved C by binary-search the answer + O(n) check. D seems to be hard with that xor operator. I got E pass pretest using back-tracking n elements from a set of a few boundary points. Hope my solution can get AC.

Upd: Yeah!!! E Accepted. Hello Div 1 :))

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

Wrong answer pretest 1 of problem B ??? really frustrated!!!!

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

    Got the same problem then one of friend told me not to use the built in power and replace it with your function implemented simply iteratively and it worked. I hope same is the case with you :)

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

    Yes, that happened to me as well. You have to define a pow function yourself, the default one won'w work (no idea why honestly).

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

i did't see "contiguous "... so C i used priority_queue Pretests passed. it must failed system pass..... sad .... and my room had one B i(1~72)... want hack him...but no data...

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

how to solve B ?

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

    you must try all of s(x). s(x) is in range(1..81). so for each s(x) you calculate x=b*s(x)^a+c. If x>0 && x<1e9 you add x to the list of answers. Something like that :D

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

    x = b*pow(s(x),a) + c As s(x) <= 81 as x <= 1e9 Take a loop from 1 to 81 For each i find x = b*pow(i,a) + c If s(x) == i and 0< x < 1e9 then x is a solution

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

    My solution for example. You check every sum of digits from 1 to 81 and compute X from equation. Then just check that sum of digits of X is equal to yours.

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

    You just need to iterate through different possible values of s(x) as there are only 81 possibilities for it in case of 999999999 it will be 81. now find the expression b*s(x)^a +c and check whether obtained x has the same s(x) value or not.if yes increase the counter.also need to check whether x<=10^9.

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

      could you explain pls why there are only 81 possibilities,i couldn't get that point.

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

        If s(x) is the sum of the digit of number x, then the maximum sum we can achieve is with number 999999999 (10e9-1). In this case, s(999999999)=81. Hope this helps :)

        We cannot have a sum larger, since 9 is the biggest digit we can get

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

    I was getting wrong answer on pretest 1. Can anyone check my submission. I did the same thing as you guys mentioned. http://codeforces.net/contest/460/submission/7530259

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

      Never use already implemented pow function unless you need it for doubles, write your own, its not hard, and even O(exponent) one is okay with time :)

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

      7534711

      You must be careful with pow(). Also, there is bug somewhere else.

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

I just noticed D asks for any subset with cardinality <= k, not any subset with cardinality = k... Now I know why everyone was getting AC so fast :P (hint: the xor of x*4, x*4+1, x*4+2, x*4+3 is always zero)

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

    how to solve K=3?

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

      2·2i - 1, 3·2i - 1, 3·2i for some i if there's any; otherwise the XOR is at least 1.

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

        that seems not to be the only condition. counter example: 5 ^ 10 ^ 15 = 0

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

          If the range includes the numbers 5, 10, 15, then the range also includes 7, 11, 12 (generated by i = 2) whose XOR is also 0.

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

        I'm wondering: how did you think of this triplet?

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

          I thought that 3, 5, 6 works (gives XOR of 0), so there is a possibility with three numbers. Then I toyed around with proving of stuffs. Like, the most significant bit that is set among the three numbers must be set twice for the XOR to be 0 (e.g. 5 and 6 both have third least significant bit set). Then the remaining number will obviously be the minimum, and consequently to minimize the range covered (and thus maximizing the probability of a range having these numbers), we need them to be . Then the second most significant bit must also be set twice, so we have three numbers 2i + a, 2·2i + b, 3·2i + c where , and obviously we minimize the range covered by letting a = 2i - 1, c = 0, and b = 2i - 1 follows. Then I also managed to prove that this is the best solution; that is, if these numbers aren't possible (and k = 3), then there is no solution with XOR 0.

          Confused? Yes; I'm not even sure how I managed to stumble on that solution.

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

          I used this in my solution. Suppose k = 3 and there are three such numbers whose XOR gives 0. Let's look at the numbers bit by bit. First, the highest bits will be

          1.....
          1.....
          0.....

          (there is no other possibility). Now, for the next position, there are several possibilities. First, all three bits can be 0:

          10....
          10....
          00....

          We can actually do this for zero or more positions:

          1000....
          1000....
          0000....
           ^^^
           0+ times

          But on the last position there has to be something different, otherwise the first two numbers would be equal. So, on some next position there won't be three zeroes, and we arrive to the other two possibilities for this position. The second one is

          1000..1...
          1000..0...
          0000..1...
           ^^^^^
           0+ times

          We want to keep the numbers close to each other because of the l, r constraints. So let's make the biggest number small as possible and the smallest number big as possible:

          1000..1000
          1000..0111
          0000..1111
           ^^^^^
           0+ times

          And for the third possibility:

          1000..1...
          1000..1...
          0000..0...
           ^^^^^
           0+ times

          notice that if we can use it, then we can also use the solution for the second possibility. So, the final answer is

          1000..1000
          1000..0111
          0000..1111
           ^^^^^
           0+ times

          or 2i + 2j, 2i + 2j - 1, 2j + 1 - 1 for permissible values of i, j. Now we can just check all values of i, j and see if the result fits between l and r.

          And now (I realised this after seeing chaotic_iak's answer), if we have an answer of form

          1000..1000
          1000..0111
          0000..1111
           ^^^^^
           0+ times

          then the answer

          11000
          10111
          01111

          also fits the l, r constraints. So we can let j = i - 1 and only check

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

    if x%2==0 then x^(x+1)^(x+2)^(x+3)==0 :D lol

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

    nice observation, thank you

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

My solution for problem C was failing the test case

6 2 1
1 2 2 2 2 1

because of an under flow that I discovered 3 mins after the end of the contest ! :D Ok that's something new :D

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

    And I failed the B because of an overflow and failed the C because of an underflow :)

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

In fact, this competition was really fun. I knew I will be hacked at B, cause I didn't check the upper limit, so I started searching for people that didn't do same thing, and got 5 successful hacks. After that, I noticed that a lot of people were only checking the sum of the digits up to 72, so I started a brute force program to find some solution which sum of digits is >72, and found one, another +500 points. In fact, the thing I wrong-solved it gave me bonus points. The thing I forgot to set upper bound of binary search to 2*10^9, so I lost that task, and only one guy also forgot that, the guy who hacked me. :D Btw, the contest was great!

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

How to solve C , Can anyone explain ?

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

    Binary search the solution, and try to implement your own check method, can the minimum be x?

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

      Can u explain ur check method ?

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

        Uhm, lemme try(atleast how I did it) First, make an array left, such that left[i]=max(0,x-a[i]) After that, iterate through that array, and see, if the current number of "open" intervals is less than left[i], open more left[i]-cur intervals, always number of total intervals and number of current intervals. You can check my solution, it failed because of the high constraint, the check method is right.

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

http://codeforces.net/contest/460/submission/7531713 what was wrong with my div2 C solution? I used binary search

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

    One problem is that the answer can be more than 1e9.

    For example:

    1 10000 1
    1000000000
    

    The answer is 1000010000, so you just need to change "high".

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

This contest was very frustrating >.<. At least I learned that using the built-in function pow() is bad and I definitely won't use it in future contests. The amount of newly registered users placing in the top 500 is insane, and seeing others in your rooms getting hacked by reds before you can even try to hack them is sad. Please let there be a contest for both Div1 and Div2 soon to stop this!

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

fastest sys test I saw in my life !

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

thx for B =)

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

HATE LONG LONGs!!! HATE COMPILATION ERROR!!! I was late with my correct D solution just for 5 seconds!

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

Back to Specialist !

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

In the task statement for B, it is clearly written: "Print only integer solutions that are larger than zero and strictly less than 109.". However, the output for the 10th case is:

6 208000352 1333225037 -2113928864 -881045069 855318976 -1059281175

Can someone offer an explanation, please? :)

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

Hi, I try to make a solution for B problem, but my solution failed in the final case, however I can not understand why, somebody can explain me, here is my solution http://codeforces.net/contest/460/submission/7531464

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

    You check whether number is smaller than 108, rather than 109 (count zeroes). AC:7534579. And exponential format is your friend (it is absolutely precise because mantissa of double is 52 bits: 7534816) in avoiding such errors.

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

    the argument to sumDig() function in the following line can be greater than what 'int' can store :)

    if(i == sumDig(b * pot(i,a)+c))
    
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    In function SumDig(int a) , I think the parameter should be SumDig(long long a) instead

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

Well, I'll be green again :-(

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

First blood on E! And 1 condition away from 2nd place...

I'm surprised at how many people failed it and especially at how many reds did, it seemed like the pretests were quite strong (due to asking for a complete solution). I solved it using DP on states (,) of towers placed so far, plus not trying all points but only border points — observe that if we can pick points (x + 1, y) and (x - 1, y), then for (x, y) to be picked as the last point in a possible solution (these other points don't give better solutions), and respectively, but then and we can move this point (x, y) left and right without changing the answer; similarly for the y-coordinate. Then, I get an O(N3R3) solution with a good constant.

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

I tried to solve C in a different way, Like , I built a segment tree with range minimum query with the left most minimum value. Now each day , I find int r = RMQ(1,n) and update range from r to r+w-1 with value 1. after mth day the RMQ(1,n) is the answer. I got WA in case 8. I don't know if it is due to my wrong implementation of the segment tree or my idea is wrong. Can someone tell ? Here's my submission 7531931

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

Bad Day for me in problem B.

Hacked

AC

The only difference is that I did not check for x > 0 && x < 10^9.

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

Codeforces round 262, div 2 problem 2

http://ideone.com/7ghrM6

my code is working correct on ideone (for the incorrect test case) but its giving wrong answer here. Please help!!!

http://codeforces.net/contest/460/submission/7533280

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

    Dont use implemented pow, write your own.

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

    try to code your own pow function because you loose data going from double to long long.

    inline ll ipow(ll x, ll a)
    {
    	if(a == 1)
    		return x;
    	if(a == 2)
    		return x*x;
            // and so on..
    	return 0;
    }
    
»
10 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

For Problem B

my solution on ideone gives the correct output for the case : 3 2 8:

http://ideone.com/JctOLq

but on codeforces compiler it is showing different answer: http://codeforces.net/contest/460/submission/7534562

can somebody explain why ?

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

    It happened because you used the pow function which works with doubles and has precision errors. It has been said in an earlier comment that (long long)pow(5, 2) returns 24 instead of 25 because the double returned is 24.9999 and it is casted to an integer value.

    The MS C++ compiler has another implementation for pow and it works better in this problem. This is how I got ACC with the inbuilt function.

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

Very nice contest. D was very interesting , especially when k = 3. E was a bit harder than usual. I only succeded in makeing a back placeing half of the towers and put the other ones simetrically. I am not sure of it's correctitude , but I think it's a way to go as N ≤ 8.

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

Problem B, Getting right answer con muy visual studio and ideone, but in the contest shows a different answer,#7533294

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

Забагованный Codeforces...

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

Can anyone figure out why this code is giving wrong answer?

For same input it is giving correct answer for testcase1 on my computer but it's showing different output on your platform.

http://codeforces.net/contest/460/submission/7535021

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

    It looks like on Codeforces code calls built-in function pow(double, some_type) from cmath instead of your function. AC: 7535252.

    By the way, didn't you write in Russian thread?

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

Can someone please give a clear explanation how to solve problem C?

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

In problem C, test case 5

10 8 3
499 498 497 497 497 497 497 497 498 499

How is the answer 500? Isn't it supposed to be 499?

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

    Water indices [1, 8], [2, 9], [3, 10] (one-based).

    EDIT: Wrong reading. (I didn't solve C.) Water indices [1, 3], [2, 4], [3, 5], ..., [8, 10] instead.

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

    We have m = 8 and w = 3. So lets do 8 operations:

    after 0 operations: 499 498 497 497 497 497 497 497 498 499
    after 1: 499 498 498 498 498 497 497 497 498 499
    after 2: 499 498 498 498 498 498 498 498 498 499
    after 3: 500 499 499 498 498 498 498 498 498 499
    after 4: 500 500 500 499 498 498 498 498 498 499
    after 5: 500 500 500 500 499 499 498 498 498 499
    after 6: 500 500 500 500 500 500 499 498 498 499
    after 7: 500 500 500 500 500 500 500 499 499 499
    after 8: 500 500 500 500 500 500 500 500 500 500
    
»
10 лет назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

vitux Neodym I am always getting this stupid warning in B, even though** I have no printf statement in code**? Please tell me the reason. it is not even allowing to submit.

Code : http://ideone.com/2kAsED

Here is the screenshot. Screen-shot : http://postimg.org/image/5rtdr33kt/

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

Can someone explain how to solve C using binary search?

I can't figure out how to check if some number 'X' is a solution.

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

    the check function is f(x) :

    you can do it greedy,

    for i to n
       if seq[i] >= x : no do nothing!
       get how much do need to do until x  (seq[i]-x)
       restart need to m
       add need seq[i, w+i]   
    
»
10 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

When will i get the editorials for this contest

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

Problem C : Please Explain why updating from left-Most or Right-Most minimum solve the problem.Will It be work (Select any continuous Subarray of length m containing minimum number) and why??[contest:460][problem:C]

.

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

    i doubt the 'any continuous subarray of length m containing minimum' will work, but left most or right most will

    this is my general idea : input : 6 2 3 1 2 1 2 1

    updating left most smaller will resulting an array : 2 3 2 2 1

    then, because 1 is smallest, we choose updating index 4 till 6, becoming : 2 3 3 3 2

    if we update the middle first (index 3), it will has result : 1 3 2 3 1

    and after that, anything we choose will still have value 1 in array

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

Народ, выручайте! В прошлый раз я поднялся с ученика до эксперта на двух задачах А и В с 1 удачным хаком, а сегодня я стал фиолетовым благодаря тем же двум задачам и 5 удачным и 2 неудачным хакам. Как вы хотя бы задачи С решаете? У меня они решаются в 50% после разбора, в остальных случаях после 5-10 вариантов решения...

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

    Последние штук 5 Сшек я не смог решить, кроме той, что была сегодня. А та, что была сегодня — я на 30 минуте уже придумал решение, но ошибся в логике в одном месте, поэтому сдал не на 44 минуте, как хотелось бы, а на 90...

    А еще у нас с командой была тренировка недавно, основанная на 106 и 108 раундах. Там Сшки элементарнейшие, практически никакой идеи нет: одну из них так вообще решило больше человек, чем Б.

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

    LOL, только после написания предыдущего сообщения, я увидел, что у меня +165 к рейтингу... И теперь я имею такое же возмущение, как ты... Одна лишняя попытка по Б, штук 6-7 неудачных попыток по С, сдал все задачи черти когда (вместо адекватных 4, 10, 45 — 5, 18, 90), занял 300+ место, а рейтинг так сильно вырос... Что было бы, если бы не было косяка хотя бы в С... По примерным подсчетам тогда бы я набрал 2600 очков, занял бы 155 место, а примерно в том же районе у Des_Payfor рейтинг вырос с 1572 (у меня было 1550) до 1755 (у меня стало 1715)... 200 мест разница в табличке, а рейтинг вырос всего лишь на 40 меньше, чем у него...

    UPD: Все места указаны с учетом виртуальных участников... Но без них всё равно странно: 40 место и 150 отличаются всего на 40 единиц рейтинга!!!

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

      Вот это малина — если бы я не стал надеяться на удачу и ломать неудачно решение на последней минуте контеста, у меня было бы этак 50 место вместо 173)

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

        А в моей комнате уже нашелся умелец, который поломал всё что можно было) И мне не досталось...)

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

If you have WA1, but you think, that your program works correctly, run it from the Codeforces.

Different compilators — different answers. I have the same mistake, but it helped me.

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

Topocder SRM 630 in 6 hours, will miss it :(.

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

Irony of the day ! When I thought that this is was not my contest. I had a message from Codeforces telling me that I got one of the best rating changes in this round.

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

Problem C: A teacher can have a birthday after 10 ^ 5 days? :D

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

My Code For Problem B gives the right answer for 1st case on my IDE But Different one on the judge !!

http://codeforces.net/contest/460/submission/7536450

What is the reason behind that !!

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

Country Wise Standings for this round has been updated.

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

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

Hi, I'm new here. I submitted for the first problem two times, I got a run time error in the first attempt and my second attempt was accepted. and I didn't solve any other problems. The strange think is that my rating decreased!! Can anybody explain why this happened? thank you

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

    Your expected rank was less than 1733 and you got around 2400 so that's why your rating was decreased.

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

I wrote short description of possible hacks with some statistics. If you are interested — take a look: here.

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

Hi.

I had error in the problem B, for one case.

Now that I can see the result, it is very strange because on my computer gives the full result.

This had happened to me once I think. What mistake I be making?

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

    Man please do you read posts? It has been asked a lot. Nevermind, you need to make your own pow function because built in pow function won't work. That's the whole thing.

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

    Please read the comments above, the pow function works with doubles and sometimes has problems with precision. Write your own pow function and everything should be better.

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

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

The final answer about using the pow function is:

  • Use the BUILT-IN function with type casts ONLY IF your language is "Microsoft Visual C++ 2010"

  • OTHERWISE use your own function (e.g. when using GNU compilers)

As far as type casts are considered, see this submission as an example: http://codeforces.net/contest/460/submission/7535442

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

    The answer is to avoid pow() altogether for integer math. It works with floating point values, there is no guarantee that it will return the precise answer. Even if it does compute the precise answer for some integer values, double still typically has less than 64 mantissa bits, and the result cannot be always stored exactly.

    For example,

    (long long)pow(5.0, 23)

    on MSVC++ returns 11920928955078124 instead of 11920928955078125.

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

I had seen the editorial,seen the solution but didn't understand the solution of problem-C(present),why we do binary search in that problem,can anyone easily explain me the solution :/ .

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

    I will explain my solution, which got AC during the contest.

    First of all, we can notice that if we binary search the minimum height of a flower, we'll call it X, and we can do at most M updates to make each flower of height >= X, any minimum height < X can be a solution of our problem, because we can do the same updates as for X.

    Now, we have X and we try to see if X can be a valid solution. Let's note S[i] = minimum number of updates we should do over the first i flowers to make each flower with index from [1...i] at least of height X. We look at the i-th flower and we determine it's current height as follows: CurrentHeight[i] = InitialHeight[i] + S[i — 1] — S[i — W]. (S[i — 1] — S[i — W] denotes how many updates we did over the intervals of length W, which cover the i-th flower). If CurrentHeight[i] < X, S[i] = S[i — 1] + X — CurrentHeight[i] (we do X — CurrentHeight[i] updates with the leftmost element as the i-th flower), else S[i] = S[i — 1].

    If S[N] <= M, X is good and we look for a bigger one, else we look for a smaller one :)

    Code: http://codeforces.net/contest/460/submission/7521789

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

"Приносим поздравления" — это как-то не по-русски.

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

Round #263?

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

where are this rounds editorial?