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

Всем привет!

13 мая 12:35 MSK состоится Tinkoff Challenge — Final Round.

Авторы тура — это я (zscoder, Zi Song Yeoh), AnonymousBunny (Sreejato Kishor Bhattacharya), hloya_ygrt (Юрий Шиляев). Особая благодарность координатору KAN (Николай Калинин), winger (Владислава Исенбаева) и AlexFetisov (Алексею Фитисову) за тестирование задач. Также спасибо MikeMirzayanov (Михаил Мирзаянов) за систему Codeforces и Polygon и компании Tinkoff.ru за проведение чемпионата.

Раунд состоит из семи задач, а продолжительность — два часа. Раунд рейтинговый и открытый для всех, т.е. каждый участник Codeforces Div.1 и Div.2 может принять участие в нем. Разбаловка будет объявлена перед раундом.

20 участников Отборочного тура, подтвердивших возможность онсайт-участия в финале Tinkoff Challenge, будут соревноваться в офисе Tinkoff в Москве. Чтобы болеть за официальных финалистов, сделаем отдельную ссылку, которую добавим позже.Вот ссылка на текущие результаты официальных финалистов.

Список финалистов:

Среди онсайт-финалистов будут разыграны призы:

  • 1 место: 50000р
  • 2 место: 20000р
  • 3-5 места: 10000р

Мы надеемся, что каждый найдет интересную для себя задачу и получит высокий рейтинг!

UPD: Стоимости задач: 500 — 1000 — 1750 — 2000 — 2500 — 2750 — 3500

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

Официальные участники Tinkoff Challenge Final Round:

  1. LHiC
  2. SirShokoladina
  3. TeaPot
  4. Kostroma
  5. AlexDmitriev

Победители открытого 414-го раунда Codeforces:

  1. V--o_o--V
  2. LHiC
  3. Um_nik
  4. Petr
  5. Shik

Опубликован разбор задач на английском языке.

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

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

Is everyone allowed to participate in this round, besides not having participated in the previous round?

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

    Yes, you can treat it as a normal Div. 1 + Div. 2 round.

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

      Please update the title in the contest tab including that it is a Div 1 + Div 2 rated combined round.

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

Isn't timing unusual from normal codeforce rounds ? .... Do not want to miss it but have semester exam :(

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

:|

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

Thank you)

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

    Like someone said it's probably held at the same time as the on-site contest, and different countries hold APIO at different times so it's hard to avoid anyway.

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

zscoder Congratulations for becoming red :D

I remember last time you prepared a round you was purple

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

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

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

Are the finalists gonna be in one room?

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

Just come on!

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

..

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

I have an exam, but I'll participate :"D

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

Hopefully,there could be data structures related problems in this challenge......

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

hopefully there will be short statements !!!

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

zscoder is this the round you mentioned here ?

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

кто все эти люди?

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

Hope there won't be delay before the contest.

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

Is the round rated?

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

Some people were hoping if they would participate in a round held by tourist they would become so strong competitive programmers as tourist do. So, maybe that round can teach us how to handle serious business

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

1 hour delaying would be better...

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

Hot Day and cool codeforces!

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

Better Time of contest for us.

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

I predict there will be a question on permutations.

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

I predict that problem C will be easier than previous contest.

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

I predict that problem B will be easy.

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

I'm esemoooooo.

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

Не могу зарегестрироваться на раунд! В чём проблема?

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

I just spotted this lucky cheater sepanta I hope that Mike will take care of him.

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

31 hacks on the same one!! What a cheater!!

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

my solution for problem C is showing "running test case 5" for the past 10mins.

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

I am waiting for explanation why it was not possible just to get Problem C AC at the first attempt.

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

    456
    123
    answer?

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

      162

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

      It's 435

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

      435

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

      Basically there will be 3 numbers in the string, so first player will use 4 and 5, and second player will use 3.

      First player wants to minimize the result, so he will obviously put the 4 before the 5. Since it is better for him to have the 3 put in the front, and since the other player is going to put it at the end because 4 > 3 and 5 > 3, he puts 5 in the last spot.

      Then the second player puts the 3 in the middle spot, and the 4 goes in the last remaining spot, at the beginning.

      Therefore, answer is 435, according to me.

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

        Isn't the output for testcase bcdef abbbc be bccbd ?

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

          My code (which got Accepted) says bccdb.

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

            how ? how much i got is first oleg will place b at first position then igor will place c at 2nd position . now, oleg can place d at last position , now igor will place b at fourth position and then oleg will place c at 3. so the resultant will be bccbd ?

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

How to solve B?

P.S. I feel like either A or B is getting harder than C nowadays. Last contest, I solved C easily, but unable to solve A. Today, I solved C (not so easily), but don't have any idea at all to solve B. It feels just weird...

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

    B was easier if you looked for which height should you cut, in order to find a triangle of area i/max_area

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

    binary search, but I'm sure there is some equation to solve it in linear time

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

      Binary search the height? But how to compute the area of such heights? Since we don't know the length of base of some heights

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

        In similar triangles, we have that the ratio of base/height has to be the same, so you can find the base for a height doing, heightX/heightB, where heightX is the height that you wanna know the base, and heightB is the full base height(the value of the height of the complete triangle).

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

        suppose that b1 is the base with height h1, b = 1

        b1 / b = h1 / h

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

      starting from apex if we join the pieces we get a isosceles triangle . then we get relation of base and height using tan(apex angle) Finally we get height of ith cut hi = sqrt(i/n)*h

    • »
      »
      »
      6 месяцев назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
      double S = h / 2;
      double s = S / n;
      
      for (int k = 1; k <= n - 1; k++)
        cout << << sqrt(2 * k * s * h) << ' ';
      
  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    I guess B is a pure mathematical problem. The k-th answer (indexed from 1) should be sqrt(k/n) * h.

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

    I am finding area of each part and setting difference between area(x[i-1) and area(x[i]) to that number. Used Decimal precision 50. Hope is would be enough...


    n, h=map(int, input (). split ()) from decimal import * k=Decimal (1000000) h=h*k from math import sqrt getcontext().prec=50 C=Decimal (1)/Decimal (h) Tot=Decimal(Decimal(h)/Decimal (2) ) Part=Decimal(Tot/Decimal(n)) x1 =Decimal (sqrt(Decimal (2)*Decimal (Part)/C)) for i in range (0,n-1): curAr=Decimal(Part*(i+1)) curX=Decimal (sqrt(Decimal (2)*Decimal(curAr) /C) ) print (curX/k)
    • »
      »
      »
      6 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      How to determine how long would my program with prec=X run on that servers for any X?

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

    O(1) solution using some geometry properties.

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

    I think B was very easy math. You got lucky to solve C on first attempt, because it was little tricky — check the successful ratio — 659/1914. Anyway, nice problems, hope you agree.

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

    You can compute Tan (a) =h/0.5, and then x*x*tan (a) =i*area., where I represents the first I triangle, and X is half the base of each triangle.

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

How to do F? I hope expected solution is not

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

    I had N^1.5*10, didn't passed 16'th test. But I hope it can be optimized in the way to pass.

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

      I think NlogN*10 should pass. Just hold the information for lazy propagation as a permutation: all digits i became P[i]. Unfortunately, somehow, in an hour I've got 15 WAs, TLEs and runtime errors. However, it makes sense to work, it's just that I had a lot of bugs. You can propagate something like P[son][i] becomes P[node][P[son][i]]

      LE: of course it got AC immediatly after the contest

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

        Implementation is rekt

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

          Neah, it was easy. I don't know what happened to me. I used to have 0 bugs till a week ago and now every source that I code has the stupidest bugs ever. I had the right idea just after half of the submission I made: initially I though that it's enough to hold all relevant moves on some node and then traverse them and push them to the sons, as I thought there are at most 10 relevant moves (through relevant I mean they change something). Ohh, and of course I spent about 10 minutes to find out that there could be operations that change digit x in x... I think this should've been mentioned. Anyway, the problems were nice but I hurried a lot and wasn't careful because I had a lot of WAs (even on C, I still have no idea what I'm doing wrong as I have a complete proof of my solution, even though I think I overcomplicated the problem)

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

          That was a joke

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

        Damn, my solution passes if I switch to size of block exactly sqrt(N) and submit on MS C++ instead of GNU. Such a pain.

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

Can someone please explain C?

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

    xyz abc => answer is xcy

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

      Yeah I came up with a few cases in contest but couldn't figure out a way to make it consistent, could you elaborate?

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

        The first guy will use only (n+1)/2 characters and second one will use n/2. So keep optimal character set for both of them. Now,

        Think about four cases: In his turn,
        1. Player 1, has bad set, what should he do?
        2. Player 1, has good set, what should he do?
        3. Player 2, has bad set, what should he do?
        4. Player 2, has good set, what should he do?

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

            How do you classify good or bad sets for both players ?

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

              If you are trying to make the string smaller, than, you have a good set if you have at least one character which is smaller than all of your opponents. and The other way is true.

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

          thanks a lot

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

          I am really feeling bad on seeing how easily it can be solved !!! I am just too stupid :(

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

            The 1750 points confused me in the first time. Maybe you have a bad day. Better luck next time.

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

      Actually, wxyz abcd is more interesting. Answer is dwcx, while the most naive strategy will output wdxc.

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

      It should be xyc,isn't it?

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

        No, it should be xcy as first guy replaces '?' such that new name would be ??y. Second person have to place 'c' in the middle. Thus we can get xcy as optimal answer.

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

    So first observation is that you will only use the smallest (n+1)/2 elements of the first string and n/2 largest elemets from the second. If all chars from s1 are smaller then it would be easy, you would simply use a greedy to fill the word putting it at the leftmost position. Now, lets have the case where the elements from the first set are larger than the second. You would want to put your largest chars to the right most position, as that minimizes its penalty. So now in these case, you go from largest to smallest and put them in rightmost position. Same is true for the second player

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

      I did something like that, but got WA, could you tell me what's wrong with this code?

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

        I'm not sure if I understood the code correctly but perhaps its this. So first observation is that you will only use the smallest (n+1)/2 elements of the first string and n/2 largest elemets from the second. So you should never add the last element from a set

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

          I should't ever be adding the last element in the set, if it looks that way it is because I sorted the second set and am taking letters from the back

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

            try this case
            abcxyzzzz
            zyxcbaaaa
            Each turn the string should be
            - a????????
            - az???????
            - azb??????
            - azby?????
            - azbyc????
            - azbyc???c
            - azbyc??yc
            - azbyc?xyc
            - azbycxxyc

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

            Ok found the bug, when the letters from the first sit are larger than the second, you should put the largest letters at the back first, and not the smallest at the back

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

      I followed this strategy, this didn't work for me on testcase 5

      reddit abcdef

      This strategy gives dfdede but answer is dfdeed

      Can someone explain why? is answer for (dexy, abde) is also deed ?

      edit[2] : corrected the starting of the output

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

        how can it give efdeed or efdede when there are only 2 e's
        the answer should be
        first person will use letters: dde second will use letters: fed d?????
        df????
        dfd???
        dfde??
        dfde?e
        dfdede

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

    My solution consisted in the following points :

    • First, you can know which letters will Egor play, because, as he wants to minimize lexographical order, it's not worth playing its «worst» letters, i.e. he only plays his (n+1)/2 lowest letters.

    • Same for Igor, who always plays his n/2 biggest letters.

    • Now, suppose it's Egor playing : his goal will be to minimize the lexicographical order, and thus he wants the lowest letter to be in front. If he has got at least one letter with lower rank than one of Igor's letters, he immediately puts it in front, because it will give him a better score than if Egor plays a largest place instead at the front. However, in the rare case where all his letters are bigger than Igor's one, he wants to play at the back of the string his biggest letter, by a similar argument.

    • Same for Igor : he will play his biggest letter at the front, except when all his letters are lower than Egor's, in which case he will play his lowest letter at the back.

    Implementation isn't really hard, it's simply important not to forget to use sets to quickly retrieve lowest and biggest letters from each player.

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

How to solve Problem D?

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

    i think graph should be linear line of compressed cliques and vertices of degree 1 and 2. i.e if deg>2 it should form a clique in combination to other nodes. else -1. but not able to code in time.

    Edit: i got the mistake. it need not be clique.
    
»
6 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

How to solve B ? My geometry is weaker than the weakest's

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

    B was easier if you looked for which height should you cut, in order to find a triangle of area i/max_area

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

    start with the topmost triangle....now this triangle is similar with the original one and the area of the two is in the ratio 1/n...from here you'll get two equations from where value of h can be easily determined...infact in doing so you'll come to a generalised formula fro each partition

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

when I will be able to view answers

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

[Problem D] I needed just 5 more minutes to solve D. Anyway I solved it as follows:
1. For each city, add itself to its adjacency list.
2. Using hashing, we will use DSU to make clusters of cities with exactly same adjacency.
3. Nodes in a cluster will have the same label value.
4. For each city, modify its adjacency list by replacing all cities in it by their representative i.e for (int v: g[u]) replace v by rep(v).
5. Now if there are more than 2 cities in any adjanceny list, its impossible.
6. Do a dfs, and carefully assign values :)

I hope this is a correct solution.
UPD: Here is the code that I missed by 5 mins.
UPD2: It got AC.

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

Can anyone please share the idea to solve problem D?

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

problem C looks complicated any simple solution ?

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

Very interesting C task :D

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

Failed to handle cornercases of k={n-3, n-2, n-1} in E on last two minutes of contest having correct ideas, such a pain.....

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

    What is general idea for E?

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

      By picking element from the beginning or from the end of array you simply move its center by 0.5. Thus for fixed array answer is for even length and for odd length.

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

      Maybe I am wrong (got WA on pretest1) but:

      • if n is even then the answer is max(a[n / 2], a[n / 2 + 1])

      • if n is odd then the answer is min(max(a[n / 2 - 1], a[n / 2 + 1]), a[n / 2])

      and this twist with k is very easy to handle. [edit: to slow]

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

There's this guy in this contest whose id is sepanta and he hacked 35 times successfully..and most amusing fact is the person he hacked is Mr.Fox and he hacked him 35 times!!! the guy sepanta has solved 2 problems (A and B) and is currently standing on 42 :| what the hell???

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

rating: rest in peace

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

what is the 4th test case of problem C?

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

    Probably, it checks how you process the case when min of Oleg equals max of Igor.

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

    try this case abcxyzzzz zyxcbaaaa Each turn the string shouuld be - a???????? - az???????
    - azb??????
    - azby?????
    - azbyc????
    - azbyc???c
    - azbyc??yc
    - azbyc?xyc
    - azbycxxyc

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

Explain please how can i solve B.

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

    Basically the whole triangle's area is h/2. So, each the n parts' area should be h/2n.

    So, for every cut i, you should find h(i) so that the resulting triangle has area i*h/2n. Note that if such a triangle has height h(i), that the base has length (h(i)/h). Therefore, you have to solve (h(i)^2) / 2h = i*h/2n, and the answer is sqrt(i/n)*h.

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

      "if such a triangle has height h(i), that the base has length (h(i)/h)." - can you please explain me why the base has length (h(i)/h) ?

      Thanks in advance.

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

        You can use Thales theorem to prove this, since cuts are parallel to the base.

        Let b the length of the base you want to compute. Then h(i)/h = b/1.

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

      Thanks

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

Anyone please help me to solve B?

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

    See above .many coders shared their idea!

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

    I tryed to binary search de height. I calculated the basis of the triangle using that :

    h/H = b/B so b =B*h/H . ( sorry the bad presentition )

    Then i calculated the Area of the triangle using this basis and the height. ( I couldn't solve B , but i think that was the idea)

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

Quite fast system test today..

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

Fastest system testing I have ever seen :O

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

Ultrafast speed of systest <3

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

Amazingly fast system testing

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

Fastest System Testing ever !!!

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

I have not seen so much fast system test before. Impressive.. :)

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

what's the answer of s = "ddd", t = "aaa" for problem C ?

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

Why did my code got TLE? Complexity looks fine to me — CODE

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

How to hack B?

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

Could someone please explain to me why in Test Case 4 (abc aaa), the answer is aab?

I feel the answer should be aba, because Oleg will place 'a' at Position 1, then Igor would place 'a' at Position 3 because he wants the string to be lexicographically large, so Oleg will be left with Position 2 and he'll place b at Position 2.

Thanks in advance!

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

    What if Oleg puts b in 3rd position. It will become ??b. Then it obviously becomes aab

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

    Oleg should place the 'b' in position 3. Then Igor has to put an 'a' somewhere. Whether it is placed in the first or second location, Oleg will put their 'a' in the other one, giving 'aab'.

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

    Oleg will place 'b' at 3, and after Igor makes his turn ('a' at place 1 or 2, it is irrelevant), Oleg will place 'a' at last empty space. Answer will become aab, which is smaller than aba.

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

27081526 In this submit time equal 405ms, but it got verdict TL. How it could possible?

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

pls anyone could explain me why the answer of the test Oleg's reddit and Igor's abcdef is dfdeed but not dfdede ? (test 5)

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

Can anyone please explain the output of this test case in problem C.

reddit

abcdef

Expected answer is this --> dfdeed

My answer --> dfdede

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

    So, the answer will be of 6 letters. letters for optimal answer- {d,d,e} and {f,e,d} Steps are :- 1)d????? 2)df???? 3)dfd??? 4)dfd??d 5)dfd?ed / dfde?d 6)dfdeed

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

Fastest system test, and fastest rating update ever, nice round :D

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

How to make a segment sum tree with range updates and range queries? I'm asking for problem F, to maintain a segment tree for every digit that have sums like that digit was 1. :)

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

Can problem F be solved with DSU on Segment tree? I tried really hard but still in vain with TLEs. It seems like it can pass in time if I change long long to int, but of course with WA.

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

I submitted two codes one with long double (code) and one with double code.

double got AC and long double got WA on test 1(though it works perfectly on my machine). I always have a rough time with doubles. Am I missing something? some compiler issues?

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

Why ratings are updated without removing cheaters?

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

    anyone knows how to tag the boss? i mean Mike or any of the Codeforces official???

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

      Goto any contest announcement blog. There will be a thanks to MikeMirzayanov. Copy the name. Then, Hover over the codeforces icon at the top of the comment box. Then, select "User". Paste the name. Click ok and post.

      You will see, sir MikeMirzayanov will be tagged. :)

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

In problem C can someone explain test case:

reddit
abcdef

The answer is:

dfdeed
  • Oleg plays with letters dde
  • Igor plays with letters fed
  1. Oleg plays: d?????
  2. Igor plays: df????
  3. Oleg plays: dfd???
  4. Igor plays: dfde??

So why would Oleg now play dfdee? — it is not optimal for him?

He should play dfde?e.

So Igor must play: dfdede

For Oleg dfdede is better than dfdeed?

UPDate: got it

Step 4. Igor plays: dfd??d forceing e on the 4th spot.

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

Now that this round is finished, when will you announce the random playrix t-shirt winners ? KAN

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

hi guys. Mr_Fox is my fake account. sina-ss is my corrently account.

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

Игра:

Дан код с контеста по задаче D

Нужно добавить не более 2 непробельных символов и получить АС.

Есть несколько решений!

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

In D tests does not check for overflow in clique check.

This AC submission http://codeforces.com/contest/794/submission/27090233 would fail for almost every graph with n = 65538, m = 98305

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

Hello guys ! Can someone please help me in problem C. A test case : abc aaa . In the first turn the first player will put 'a' in the first place,then in the second chance the second player can put 'a' either in the second place or in the third place. According to the solutions which have passed they put it in the second place. But i think it will be more optimal to put it in the third place. this way it would be lexicographically bigger from the second player's point of view. Can somebody please explain this to me ?

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

    No. The optimal strategy for the first player is to place his letter 'b' to the last position on the first turn.

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

    As it was written player can place their letter anywhere instead of question marks. So the first turn of Oleg is to place the 'b' at the end. Then, as the biggest letter in Igor's set is 'a' he will place it also at the end. Then, the Oleg's turn is to put 'a' to the first letter. Consequently, the answer is 'aab'.

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

Есть подозрение, что в текущих результатах финалистов кого-то не хватает :D

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

Could anyone explain me the last input-output example of problem D? Although there is note under the example, I can't catch its point.

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

    basically u need 1 to be the 'neighbour' of 2,3 and 4 but at the same time 2,3,and 4 cannot be the 'neighbour of each other, so therefore the output is "NO"

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

I am getting TLE for 11 test case for problem C in nlogn. Still it gives TLE. My Submission : http://codeforces.com/contest/794/submission/27085787 Can anybody please tell me reason for that. Thanks

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

    27115362 Here you go.

    Basically you TLE because of these lines.

        for( i=0;i<n/2;i++){
            sm=sm+a[i];
            lr=lr+b[i];
        }
    

    these operation are n^2 instead of n as you recopy the whole string each time. you need to write it as

        for( i=0;i<n/2;i++){
            sm+=a[i];
            lr+=b[i];
        }
    

    instead.

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

      Thanks a lot. I thought those two operations were same. But in case of string the complexity would change.

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

Everybody's rating was back to that before the contest for a moment to ban sepanta.

Anyway, justice was done. Well done, Codeforces!

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

I tried to solve the problem E.**Leha and security system** https://pastebin.com/haK2wtvr upon submission I am getting run time exception with Exit code is 1

Can anybody help me to figure out what went wrong. Thanks in advance.