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

Всем привет!

Во вторник 11 июля 2017 года в 19:35 по московскому времени состоится Codeforces Round #423 для обоих дивизионов. Часть задач будет совпадать с задачами Финала VK Cup 2017, кроме того, команда Codeforces подготовила еще несколько задач для проведения полноценного раунда.

Обращаю внимание, что с использованием задач из финального раунда VK Cup будет проведено два раунда, поэтому прошу финалистов воздержаться от обсуждения задач до проведения второго раунда.

В каждом дивизионе будет предложено шесть задач, из которых будут четыре общие. Задачи этого раунда предлагали, готовили и тестировали: gritukan, demon1999, fcspartakm, Perforator, MikeMirzayanov, PavelKunyavskiy, qwerty787788, Belonogov, izban, tourist, vepifanov, AlexFetisov, winger, Errichto, Gassa, naagi, ashmelev, Endagorion, ifsmirnov, Arterm и я. Большое спасибо всем, кто помогал с задачами!

В этом раунде будут разыграны призы от компании ВКонтакте! А именно, среди тех участников раунда, которые решат хотя бы пять задач во втором дивизионе, или хотя бы три задачи в первом дивизионе, будут случайным образом выбраны пять, и они получат сувениры чемпионата. Нет никаких ограничений на страну или язык для получения приза. Требования участия в чемпионате тоже нет, приз может выиграть любой участник раунда. Точный алгоритм определения победителей опубликуем до начала раунда. Во втором раунде с использованием задач финала также будут призы!

Удачи!

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

Div. 1:

  1. W4yneb0t
  2. moejy0viiiiiv
  3. koosaga
  4. Radewoosh
  5. dotorya

Div. 2:

  1. ccz181078
  2. rqy1458814497
  3. houruize
  4. _Is_It_Rated_
  5. liutianyi000

Разбор тут.

Соответствие задачам с VK Cup 2017 - Финал:

Обладателями сувениров становятся:

Место в списке претендентов Соревнование Место Хендл
19 827 19 zeliboba
42 827 42 kevinsogo
114 827 115 triploblastic
125 827 126 lexuanan
138 827 140 alex256

Поздравляю!

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

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

А будет еще один раунд как в том году?

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

    Обращаю внимание, что с использованием задач из финального раунда VK Cup будет проведено два раунда...

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

Thanks for your efforts

But how do you make sure that no one of the finalists has leaked the problems ?

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

Is it rated?

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

    no it's not, they wrote the word "rated" as a joke :)

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

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

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

      OMG, 300+ upvotes on a single comment. I want to thank my parents for bringing me up, my friends who have always supported me in everything I do and everybody who voted for this comment. Also, a huge "Thank you" goes to Mike Mirzayanov, without whom this would not be possible, for creating this awesome platform.

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

Does souvenirs includes the cute cats?

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

Duration of the rounds? 3 hours, or more?

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

15 reds

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

666

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

666

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

Wow! the number of problem setters exceeds the number of problems itself. xD

It must be a challenging round.

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

    The problems of this round are proposed, prepared and tested by

    Not all of them are problem setters. So we can't be sure that the number of setters exceeds the number of problems.

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

The start time is too late

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

Okey, who wants to receive championship souvenirs, put dislike!

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

Codeforces server seems awfully slow. Does anyone know what is the matter with vjudge1 , vjudge2 and so on. There is a huge number of submission from these ids.

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

    Well, vjudge(.) accounts are used to submit solutions from VirtualJudge and there are not so many submissions to hack codeforces. However I worry that there can be problems with codeforces during the contest and also API is not working which I use participating in the contests(

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

glhf every one

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

Good luck everyone :D

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

I got so used to times specified in MSK timezone (which is also more convenient for me) that I thought this one is in MSK too and completely ruined my schedule, oops

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

    In the English post it is written explicitly that time is in UTC, isn't it? On the contests page the times are noted with a timezone, right?

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

      Yeah I know it's completely my mistake, I was quickly checking it on my phone without paying much attention.

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

For div 1 contests, will task be same as on official contest, or we will have one easier ?

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

Thx for preparing the contest... GL all coders :) Let's Rock

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

.

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

With all due respect to all problem setters and testers... I don't know why but seeing 'tourist' in the list gives a different feeling whole together..!!! Seems to be an awesome contest on it's way !

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

delay :)))

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

10 minute delay? :(

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

And again delayed...

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

I think winner of div 2 will be ccz181078 :)

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

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

delay------10 minute.

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

I have a feeling that Div2 result will mostly be decided by the speed of solving the first 2 problems.

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

Я думаю что сегодня этот codeforces round пройдет хорошо

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

You know what's worse than being in the friendzone for long? Being in the gray zone after a ton of contests. :(

Hoping to change that in this round. Need +40. Good luck to me! Good luck to everyone! :)

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

Where is the scoring distribution?

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

To determine the winners we will use the following algorithm.

  1. List all participants from div. 1 who solved at least three problems from top to bottom of the standings, ties broken by the time of last AC.
  2. List all participants from div. 2 who solved at least five problems from top to bottom of the standings, ties broken by the time of last AC.
  3. Append the second list to the back of the first list.
  4. Use the following code to generate the indices of the winners in the resulting list. The seed is the score of first place in the next div. 1 contest. The length is the length of the list.
code
  • »
    »
    9 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    "The seed is the score of first place in the next div. 1 contest."

    I can see people in the next contest posponing their submissions by few minutes and intentionally unsuccessfully hacking just to get a more favourable seed.

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

    And? Who won? :D

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

    I wrote some scripts to make the process of winners determining easier, and they produce results slightly different then Xellos's. Here are my results (not official yet):

    List place Contest Rank Name
    19 827 19 zeliboba
    42 827 42 kevinsogo
    114 827 115 triploblastic
    125 827 126 lexuanan
    138 827 140 alex256

    The seed is 5581, the length is 213. The output of the generator is 19 42 114 125 138. The scripts I used are below. Xellos, have you used any scripts? If so, can you see where the difference came from?

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

      The list places are the same for me. I didn't use scripts, just went through the scoreboards manually, marked off ineligibles and then added 1 to list places for each smaller ineligible place; maybe I added incorrectly for place 131.

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

      I believe that my results are correct, so now they're official.

      If anyone has comments about the code, please comment.

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

what will be my contribution if i ask is it rated? and what the hell of lating?

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


Всем привет. По каким-то причинам последние дни не работает API codeforces поэтому CF-Predictor не работоспособен(: Надеюсь, API вернут и на следующих раундах все будет хорошо:)

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

как вы решили задачу C div2 ? у меня тл на 5 тесте

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

This contest has more hacks than the U.S. presidential election!

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

Is there anyone easier way to do E than FFT?

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

Easy div.2 A hacks

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

    How can i hack other's code ?

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

      You need to lock this problem firstly(problems page), then you can open other's code (room page, double left click / ctrl + click on their score on problem) , look through and try to hack (button will be at the end of code).

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

        There are no constraints? e.g. rating only lock?

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

          You can lock only task you have already solved(solution has passed pretests) and you cannot send any code on this problem after lock.

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

4 1 2
1 1 1 2 Ez hacks :) P.S.: Sorry, room 125 ^_^

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

    Answer is 2 right?

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

      yep

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

        why 2 ? i thpught the answer is 0

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

          If a group consist of one person, it is seated at a vacant one-seater table. If there are none of them, it is seated at a vacant two-seater table. If there are none of them, it is seated at a two-seater table occupied by single person. If there are still none of them, the restaurant denies service to this group.

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

    Hacked is better than system testing failed

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

WA on pretest 11 on Div2 D. What could be this case?

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

    how is it 2? the first one will take an a table, the next 2 a b table and the last 2 the last b table. isn't this right?

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

      I assumed the same but..

      If a group consist of one person, it is seated at a vacant one-seater table. If there are none of them, it is seated at a vacant two-seater table. If there are none of them, it is seated at a two-seater table occupied by single person.

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

        oh god, i understand now lol. that restaurant has some stupid policies.

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

          Could it be said that the pretests were very weak?

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

            the pretests were fine. if i had wa i would have wasted too much time trying to debug, not realizing that i understood the statement wrongly.

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

    I think very many solutions falls in this test, me too...

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

Is the hack for C TLE ???

If so I'm screwed.

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

Hack for C div2 or A div1?

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

4 1 2 1 1 1 2

Hack test in problem A :D :D Good Luck all :D

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

people were hacking faster than eminem rapping

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

TC 11 for DIV2 D any idea?

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

How to solve E?

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

After a really bad performance on A and B...I know if I continue to do this contest, as usual, I am definitely not going to get a good result, so I opened F. I did F for more than one hour and I didn't pass pretest 19 until the contest ended.

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

    Why even bother with A and B? You can start with F straightaway :D Yes, this strategy might not give you the best result, but at least you will spend the contest solving an interesting problem.

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

When you cannot debug a simple FFT solution for 1 hour :'(

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

4 1 2 1 1 1 2

Hack test in problem A :D :D Good Luck all :D

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

What is the hack for Div2C?

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

What is the hack for Div2C?

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

How to solve Div 2 D? And is Div2 E just a simple segment tree that remembers for every letter and every position % 10 number of occurences on every prefix?

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

    I solved Div2E nearly the same way you described and used bit instead of segment tree.

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

    From one node, the other nodes extend in k directions. like a bfs.

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

    tried the same, but got mle. i suck at implementing seg trees.

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

    For Div2D.

    The tree wil be of star shape. So, put k vertices around centre. Keep doing this until you have less than k vertices. Then, put each of the remaining vertices in each of the branch. Maximum distance is

    • 2*floor(n-1/k) in case when n-1%k==0

    • 2*floor(n-1/k)+1 in case when n-1%k==1

    • 2*floor(n-1/k)+2 in case when n-1%k>1

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

      How do you prove (even intuition behind that) that a star tree generates the lowest diameter?

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

        Followin is just an attempt to prove. Correct me if I am wrong.

        CASE: n > 2k

        We can prove this by induction.

        Let's say we know the best tree consisting of n - k vertices and k leaf nodes. So, our required tree will be formed by adding k vertices to the best tree consisting of n - k vertices and k leaf nodes , one at each of the k leaves.

        CASE: n <  = 2k (This is base case)

        We can clearly see that in this case it will be star. Any other shape of tree yeilds greater diameter.

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

          The proof is pretty gappy. You don't prove that in the first case, there can't be a better solution.

          Also, when using induction in graphs, most times it's more efficient to go backwards, inspect a graph, take away a node/edge, and by knowing the statement was true for the previous graph, it can be shown, that it is for the current graph also.

          If you use the induction forward, there will be troubles to proove that you can achieve any graph this way.

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

        There can't be a node with higher degree than k, because if a node had more edges, then the network would have more than k exit nodes.

        Let's assume the highest degree is smaller than k. Pick the highest degree node, and choose the two longest "branches" starting from it. At the end of these "branches" there has to be an exit node. If we would have a node instead of this one, with degree of k, then this two longest "branch" would be at most as long as it is now, because all the non-exit nodes, can be distributed into more parts.

        Also with this change, other lengths won't be longer, because it can be seen easily, that the longest path in this new network must go through the centre of the "star".

        In conclusion, the star network isn't worse than any other, hence it's one of the optimals.

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

I found D easier than C in the contest.

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

Hack for C div2 or A div1????

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

Only 250points difference between C and D? Really?...

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

This was a CF round for me :D

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

Also div2 A hack: 5 1 2 1 1 1 1 1

It worked, if somebody didn't count the number of split tables, just used a boolean.

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

I tried to hack Div2 C for TLE. So I tried hack through generated input, then spammed some large string and same index. I care that sum of the size of the strings are equal to 10^6 and sum of k values are equal to 10^6 but I got invalid input with this error "Validator 'val.exe' returns exit code 3 [FAIL Expected EOLN (stdin)]". What is the possible reason?

If anyone succeded to hack via generated input, can they show their generation code?

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

    You forgot to output newline somewhere

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

      So sorry to bother you again, can anyone find the mistake? Here is the generation code.

      using namespace std;
      #define PB push_back
      #define MP make_pair
      typedef long long int ll;
      int main(){
          std::ios::sync_with_stdio(false);
          cout<<1000<<endl;
          string t = "";
          for(int i = 0;i<1000;i++)
                 t.PB('b');
          for(int i = 0;i<1000;i++){
              cout<<t<<" "<<1000<<" ";   
              for(int j = 1;j<=1000;j++)
                  cout<<j<<" ";
              cout<<endl;
          }
          return 0;
      }
      
      • »
        »
        »
        »
        9 месяцев назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        You mustn't output " " at the end of the line.

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

test case for div2-A 5 1 3 1 1 1 2 2 i have hacked the code of problem div-2 A of doyenne his code gives ans=2 but correct answer is 0 but still showing an unsucessfull hack some body please help me ..why ??

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

    No, correct answer is 2. First guest takes free 1-seater table, then 2nd and 3rd take 2 free 2-seater tables. 4th pair of guest takes last free table. So last pair goes out.


    Правильный ответ 2. Первый садится за свободный одноместный, 2 и 3 за 2 свободных двухместных. Первая пришедшая пара занимает последний двухместный столик. Последняя пара уходит.

    У твоего комментария какой-то косяк с языком. Он на английском, но, видимо, поставлен русский язык.

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

Div1 C memory limit too strict ???

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

    Yup :( I just changed vector<pair<long, string> > to vector<pair<long, long> and string[MAX] and it passed. How to check difference in memory in this case?

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

      I changer my segtree size from maxn*4 to maxn*3 and it passed damn

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

What was that rogue test case in problem A Div 2 that many people missed?

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

in Div2 B if all the cells are black the solution will be -1 or 0 ?

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

div-2 A 5 1 3 1 1 1 2 2 i have hacked the code of user doyenne his code gives 2 as a answer for above TC. but correct answer is 0 for above TC. some body please help me out ?? why

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

    TC n=5, a=1,b=3, t[]=[1 1 1 2 2]

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

    ans is 2 bcoz first 3 group will occupy different tables as given in question than there will be only 1 table left for the 2 sized groups

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

pretest 7 in E was an antitest for doing fft mod 2^27*3*5+1? Or did i make some stupid mistake?

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

System test is started...

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

Waiting for System Testing is like waiting for your HIV testing results...

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

That feeling, when you couldn't solve task during contest and solved it for 6 minutes after contest

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

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

 Div 2 A

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

test 8 in Div2 C :))))

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

such shitty pretests for div2C

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

Anyone getting Memory Limit Exceeded on test 8 in div2 C? :(

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

The contest is a massacre for any problem solver XD WOW

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

Memory Limit Exceeded on test 8 in Div2 C :(

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

    If I understand the statement well, you can have a string of length 106 (e.g. aaaa...aaa) and then 106 positions for this string : 1, 2, 3, ..., 106. Maybe in this case you register 106 times a string of size 106 ?

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

      yes. i was pushing the string to each of such indexes. Instead of pushing, could have just stored the max. length string for each index. (instead of creating a vector of string, sorting it and picking the last one. :P)

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

Very funny. Write some complicated statement in d2 C/d1 A. Do not add appropriate pretest and watch majority of the solutions fail. Did you guys bring enough popcorn?

Edit. Some people still don't know. The strings coincide, so the total amount of occurences can be huge, you should set each letter only once...

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

    Sorry, are you complaining about the fact that a solution that is obviously too slow gets TLE?

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

      I'm complaining that it was not obviously too slow. It is the fact that you can't discuss as majority of submitted solutions failed.

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

        Copying strings of length 105 from 106 different positions gives 1011 operations. What is not obvious about that?

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

          The fact that they can overlap. It was mentioned that they can coincide — I understood that they can have some common parts but not that the positions may overlap.

          The statement was not clear — perhaps examples showed that problem but it should not be required to read them to understand the task or at least it should be mentioned that "be careful, statement is not too good, read the examples". Besides it was not clarified what does it mean to be lexicographically minimal.

          Bottom line is — the statement was confusing which was proven by very high rate of unsuccessful submissions.

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

            You're just grasping straws. If you made the assumption that strings cannot overlap you cannot blame that on the statement not explicitly mentioning it.

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

            The statement doesn't say that they don't overlap. Thus, they may overlap. I don't see what can be unclear about it.

            P.S. The only thing a high rate of failed submission means that (surprise!) a lot of people submitted an incorrect solution. These solutions are blatantly wrong, it's not a corner case or something.

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

    i do, but still TLE... I'm curious.

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

      Probably java.

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

        Yes, and I used my own SortedMap implementation, which made the code about 2x slower than when using the standard TreeMap implementation. Still O(nlogn), pity that it was rejected.

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

          I can confirm java is probably the problem. I translated my Java solution that failed systests into C++ and I got AC. It's annoying that problem-setters often seem to make bounds that are very unfavorable to java users, but understandable considering the main focus is on making sure suboptimal C++ solutions to not pass.

          Reference: 28433564 28453400

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

            But there is a linear solution to this problem.

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

              I get that, but based on the bounds I expected am NlogN to pass in time. Maybe that's because I generally compare 10^8 operations ~ 1 second, which might be more accurate for C++ than Java.

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

                I don't get that there's a linear solution to this problem. But, that's why I'm not red and will have to wait for the tutorial...

                EDIT: Oh, yes, now I see, use an array instead of a (tree)map, that's linear indeed, thanks.

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

I don't get how my submission to div1A (28436078) can get a TLE... Can anyone help me understanding this? It seems to me that my program does something like 5·106 operations in any case...

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

    I was wrong. Deleted.

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

    The length of the answer can exceed 106. So you have an access violation that changed the loop counter or something like that.

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

      but I used array size 2e6+4, still I got tle on test case 8. Any reason for that?

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

      No it's not the problem, I have no access violation.

      Actually I got it : I wrote s = v[remember[i]] in a loop of size 106, and v[remember[i]] can be a string of length 106. So if I simply erase this and replace s by v[remember[i]] in the next lines, it should get AC... :'(

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

    same doubt

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

    You made the same mistake I did, copying the string each iteration instead of referencing it:

    s = v[remember[i]];

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

When you fail at A and C... Because of edge cases... I failed C because i used constant too low (2*10^6)

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

When you fail at A and C... Because of edge cases... I failed C because i used constant too low (2*10^6)

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

Div2C/Div1A how could this pass systest? http://codeforces.com/contest/828/submission/28450333

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

    It takes about operations. The worst case is 1000 strings, each of length 1000, and each appearing at 1000 positions that are spaced 1000 apart.

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

      guys i still struggling to get AC :( , if someone can help me

      I got WA on test case 5 and my solution works in O(|Needed String|)

      Here

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

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

Did O(m * log2(m)) pass in D?

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

How to solve E div2 ?

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

    I built segment tree for each length of e, every position in e, every letter. So it's about 220 segment trees. I didn't use custom allocator, so got TL. But solution with custom allocator gets AC.

    PS: can somebody explain me better solution?

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

      I also did something similar but using a space around 40*N and BIT trees.

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

        ML is not problem. Every adding operation uses O(logn) memory, so it's O((n + q) * logn). My solution used 393 MB  <  512 MB.

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

      I didn't use a custom allocator either. But I made sure that when I was looking at length L, my Fenwick trees all had size n / L, maybe that makes a difference. Here is my solution: 28440263

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

        I think because you used arrays you haven't troubles with memory allocation. And I'm not sure, but Fenwick works faster than segment tree

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

Who wants it to be unrated? XD

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

For Div 1 A/ Div 2 C, consider the following testcase:
4
bcc 1 3
c 1 5
bcbc 1 6
cc 1 4
The answer should be "bcbccbcbc" but the accepted solutions output is "aabccbcbc". Why so? The question states that there is at least k occurrences of each string!

EDIT: My mistake! Interpreted the question wrong!

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

    Question also states that you need to print lexicographically smallest string of all possible strings(answers). In that case u can assume that at least k means exactly k and put 'a' at all the remaining positions of string.

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

Why is rating predictor not working ?

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

So why I'm getting TLE? :/ C SOLUTION

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

Can someone tell if the round was actually rated?

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

When do Codeforces API goes up?

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

Thank you for the contest, the problems were great. However, there is one tiny issue.

28439979

Look at this submit. It passes flawlessly pretests and then gets TLE 16. We can easily notice what happened — author is outputting answer via unsynchronised cout. The real question is — wasnt there any maxtest in pretests in such a valuable problem? KAN

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

A solution with policy-based DS fits exactly in the time limit in Div 1 C:

http://codeforces.com/contest/827/submission/28452503

It is such a sad fact that i didn't notice that i got WA during contest because i forgot to check the set size.

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

Time Limit 2 secs

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

есть подозрение, что аккаунты, зарегистрированные буквально за пару часов до контеста и случайно решившие 5 задач на самом деле являются твинками людей из 1ого девизиона

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

Problem C in div2 says "**It is guaranteed that the sum of lengths of strings ti doesn't exceed 10^6**".

I got RE in this submission: 28448052 Here array size was 1001000.

I got AC after increasing array size 2*10^6 in this submission: 28452964

Why?

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

please can anyone tell me why i am getting a TLE in 28448213

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

can anyone tell me why i am getting TLE i dont think so that my code is taking more than 2 secs CODE->28448213

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

Can someone explain their solution for Div 2C String Reconstruction ?

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

    Keep an array of indices, (we have an array a of length 2,000,000, if a[i] is marked with an index j, this means that there is an occurrence of string j at position i, if multiple strings occur at the same position, save the index of the longest string which occurs at that position). Then, we loop through all of the positions. For each position, if the position is marked and we are not currently printing a string, then we start printing the string marked by the current position. If a position is marked and we are currently printing a string, then we check to see whether the leftover string we are currently printing is longer than the string marked on the current position. If the string marked on the current position is longer than the leftover string we are currently printing, then we stop printing the leftover string and start printing the string marked on the current position. If a position is not marked and we are not in the middle of printing a string, then we just print 'a', since 'a' is the smallest letter.

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

28448669

//lol;

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

My Rating=2017 in year 2017 :), so to me seems like a notorious coincidence

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

Why does this TLE for Div2C

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

What is the prize selection algorithm?

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

For Div2 C, can anyone tell me, why I am getting WA on test for my code: 28454008

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

A bit of bit magic helps you to solve E div 2/ C div 1 in O((n / 32)2) time.

Code: 28454011

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

Ugh, n = 1 on F... 28450889 vs 28454566. This is the worst way to get a problem wrong. I want a refund for my brain :-P

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

can somebody plz point out the mistake, I tried for hours now, here's the code 28455191

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

Ah! String Shallow copy denied me a double digit rank.

string a = "This is a blunder. I knew it. But I forgot. Dont mess it up"

string b = a. //This takes not O(1) but O(n) time :(

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

when will next round?

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

Challenge in div2 C

Add this constraint

"the string can only be reconstructed using the input strings"

this is how i understood the problem during the contest and i thought that it was very hard problem

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

I can't access neither my submissions page nor any other user submissions page since the round ended. Server returns page with "The page is temporarily blocked by administrator." message. Does anyone else experience this issue?

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

Can someone help me with the Div 2 part C 828C - String Reconstruction. I wrote a solution but get black spaces in between the final string for the answer. Can someone tell me what the mistake might be?

Here is my source code:

int main(){

//ifstream cin("testcase.txt");
ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

char s[1000000];
long long int n;
cin>>n;
long long int m=0;
while(n--){
    string str;
    cin>>str;
    long long int x=str.size();
    long long int t;
    cin>>t;
    while(t--){
       long long int a;
       cin>>a;
       if((a+x)>m)
         m=a+x;
       a--;
       for(long long int i=a,j=0;j<x,i<=a+x;++i,++j){
         s[i]=str[j];
       }
    }
}
//cout<<m<<endl;
for(long long int i=0;i<m;++i){
    cout<<s[i];
}
return 0;

}

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

    The given strings, don't fill the whole string. You have to put 'a' s on every position, which wasn't occupied by a character from the input.

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

      I tried that too.

      I initialized the answer character array 's' with all a's.

      Still I do get blank spaces.

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

problem A was good problem for this that never take any question easy.

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

keep calm && never give up.

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

Can Someone explain there solution of Div2C Please.

Thank You!

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

is this contest rated btw?

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

Can anyone tell me why my submission is getting a WA on div1A/div2C ?

My Submission

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

    2

    aca 2 1 5

    aba 1 3

    Answer: acabaca

    Your answer: acaaaca

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

      Thanks for the help, was able to rectify that. Getting a TLE on TC 8 now. Will have to make the solution more efficient, I think. :)

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

        Yes. You have O(ANS·k) algorithm (where k is sum of ki), but exists O(ANS + k) algorithm that much shorter and easier

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

      smirnov.i can you help me :/ ?

      I got WA on test case 5 while my algorithm works in linear time O(|Size of needed string|) that's good enough

      Here

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

        Did you check for the test case provided above in the same comment thread?

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

        3

        aaa 1 1

        abbb 1 3

        bb 1 4

        Answer: aaabbb

        Your answer: aaabba

        After if in 42 line you have to write i = ii;

        But your solution seems to bee not linear too, because in lines 37 and 43 you copy the string, so I can give you a test when you will have to copy O(n2) symbols :-)

        BTW, your solution is very close to AC, you just have to think how not to copy all the string

        • »
          »
          »
          »