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

Автор Mediocrity, история, 7 лет назад, По-русски

Всем привет!

Приглашаю вас принять участие в Codeforces Round #429, который начнётся 18 августа в 18:05 по московскому времени.

Задачи для вас готовили Фёдор Mediocrity Коробейников, и Владислав totsamyzed Мосько. Большое спасибо Алексею netman Вистяжу за помощь в подготовке раунда, Александру AlexFetisov Фетисову и Владиславу winger Исенбаеву за тестирование задач, Михаилу MikeMirzayanov Мирзаянову за системы Codeforces и Polygon.

Участникам обоих дивизионов будет предложено по пять задач и 2 часа на их решение. Разбалловка будет объявлена ближе к началу раунда.

Надеемся, раунд вам понравится! Всем удачи!

UPD: Разбалловка: 500 — 1000 — 1500 — 2000 — 2500. Обратите внимание, что количество задач изменилось с 6 до 5.. А также большое спасибо Алексею Um_nik Данилюку за тестирование задач.

UPD: Раунд завершён. Просим прощения за все произошедшие неудобства. Поздравляем победителей:

Div1:

  1. anta

  2. LHiC

  3. Radewoosh

  4. dreamoon_love_AA

  5. ikatanic

Div2:

  1. emengdeath2020

  2. Svlad_Cjelli

  3. denis2111

  4. Ehsan22

  5. zjt_ioi_2019_ak

UPD: Разбор

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

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

Let's hope cp will become a real sport. And let's hope for short statement too :))

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

Short announcement, short problem statements. Hopefully.

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

There is a codesprint on Hackerrank one hour in the midway of this contest.

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

Who will be the main character of the round?

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

New round, means new chance for better performance and improving our rate.

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

I think the winner is obvious.

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

Извините за плохой комментарий и плохой русский

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

tank you all for contest. and hope for statement be as short as blog.

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

Where is KAN?

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

Hi , I just wanted to ask that whats the difference in div 1 and 2 like can we say that Div 2 E,F > Div 1 A,B,C,D in terms of difficulty?

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

    Usually, Div 2 C/D/E.. is the same as Div 1 A/B/C.. and so on. The difficulty is in the increasing order.

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

Are 2 hours good for 6 problems ?

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

I wonder what is the story behind your rating graph, totsamyzed. Are you going to be our next dreamoon_love_AA?

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

I hope we will have an interesting contest tonight:) GL

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

OMG :O ThePilgrim Registered for this contest :O

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

    Who is he? :/

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

      he is sad ,he is hurt ,he is dying ,he is lonely ,he is a mess ,he is judged ,he is ignored ,he is suicidal ,he is depressed ,he is misunderstood ,he is tired he is SmSS

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

Kool(Sorry for my bad english)

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

Why was number of problems changed?

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

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

Not the right place for this post, but could some of the contest organizers or idk inform CF staff that email system isn't working. Thanks

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

Did Um_nik save rated contest? :D

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

totsamyzed, don't make us sleep during the contest.

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

Please open additional registration! Why is it even closed? I have not expected it would be impossible to register after the competition started

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

so many spelling mistakes.

having trouble guessing the meaning of div2D

and even no explanation of the Sample

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

    took me a good 10 minutes to get it too, but what do you want, it's all part of the challenge !

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

    I asked for clarification of sample cases. Reply was "read the statement". No i'm asking for clarification without reading the statement -_-

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

RIP English

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

I'm sorry, but these problem statements are all cancerous. When you see a red squiggly line below your text, that means you have a problem. Don't submit text with a red squiggly line under it.

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

What the heck is F(n,k)???? So much broken english...

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

English is my first language and I can't understand Div1 B. It's riddled with typos and the grammar doesn't make sense.

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

    Can someone clarify: "Subset is calling «good», If we save in a graph only edges from subset , and for every vertex i will correct, taht di =  - 1 or it's degree modulo 2 is equal to di."

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

      G=(V,E) is a graph, with V its vertices and E its edges. A subset S of E is called "good" if in the new graph G'=(V,S) we have the following property: for any vertex i in V of G', we either have d_i = -1, or deg(i)%2 = d_i ("deg" meaning degree, the amount of edges in S that are incident to vertex i).

      (hope it helps, though it's a bit too late now i guess)

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

With due respect to the setters, seriously, what is that? I still haven't understood the statement of problem A and B properly.

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

With due respect to the setters, seriously, what is that? I haven't yet understood the statement of problem A and B -_- RIP English.

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

 Does anyone even proofread the problems?

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

Was excited for a rated round :/ 6 more days i guess.

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

I'm going from one extreme to another :/

After reading ABD, I had no option other than withdrawing participation.

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

Worst problem statements I've seen on codeforces in a long time. Very disappointing. The proofreaders are all on vacation or something?

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

Horrible problem description! :/

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

Div2 D is a total disaster. Can't understand anything! RIP English!

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

Horrible problem description! :/

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

Delinur, where u at when we need you?

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

You should really make this unrated. This is not English.

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

Horrible statements, and they're also not answering my questions. Not to mention zero shts were given with regards to the statements' coherence and story.

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

As if we could "save in a graph only edges" from a subset... Really, how old are the proofreaders? Freaking 5?

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

    Okay, this is getting ridiculous. This is what I get when I translate from English to Russian to English.

    Lech plays a computer game where at each level a connected graph with n vertices and m edges is given. Graph can contain multiple edges, but can not contain loops. Each vertex has an integer di, which can be 0, 1, or -1. To pass a level, it needs to find a "good" subset of the edges of the graph or say that it does not exist. A subset is called "good". If we save only edges from the subset on the graph and correct for each vertex i, that di = -1 or the degree modulo 2 is equal to di. Lech wants to pass the game as soon as possible and ask you to help him.

    At least that's understandable.

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

Never seen so many announcements in a single contest :/

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

Thanks for closed registration

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

Man dis, shit is aw full following time I am save Russia probs text in, google translate and read 'from they're.

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

    Man, shit, complete, after I save Russia, ask for the text, translate and translate the text "from them."

    Well I think the best method of reading grammatically incorrect sentences is to translate to Russian and then back, I guess.

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

When your problems' themes are so thin like that (really, Leha somehow found arrays and queries in pockets?), you'd better off not using any theme at all. Just state the problem without involving Leha in any way. For example, Div1D (what I mentioned above) should just be stated as "You are given an array of n numbers and q queries lrk...", so you don't need to stare awkwardly at why Leha's pockets are of any relevance.

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

    Say what you will, I still think that

    "Mom brought him two arrays A and B"

    Is the funniest thing I've read in a long time

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

Hands down one of the worse contests. Close to 2000 people passed pretest in C but less than 50 is able to solve D. The difficulty is so low in A,B,C that difference in ranking is explained by whoever understands the statement first.

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

the predictor isn't working for me .

does anyone have the same problem ?

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

I jumped directly to the Problem D, its been an hour and still I am not able to understand the question at all. So many mistakes in the spelling and explanation, I am leaving this round :(

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

can someone give me brief idea of sample test 2 of Problem D , how is the answer 0 ??

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

    It means: Find a sub graph of the given graph, such that for every vertices i, if d[i] != -1, then the degree of vertices i in the sub graph module 2 should be d[i].
    And you're asked to output the number of edges in the sub graph k in the first line, then k lines follow, indicating which edge you'd decided to remain in the sub graph. Edges are labeled in the input order.

    So, for test 2, a simple answer is to leave nothing in the sub graph, so 0 is acceptable. Another proper answer can be
    4
    1
    2
    3
    4

    BTW, this is the worst description I'd ever seen. I believe even google translate can do a better job :(

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

Problem C and D (div2) are awful. They didnt even provide good sample test explanations as well. And I dont know who are the heads of CF?? I mean, come on, after all this time you should at least look at the problems before deciding it is "contest-worthy".

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

My code gave TLE in C++11 and got PRETESTS ACCEPTED in C++14 :( Is it my fault or Is their any way so that my penalities are taken back.

Please someone suggest me on this.

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

    yeah I lost 150pts for penalty and 160pts more for wasting time until I see this comment :<

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

    time run of 2 version is different. If you use "cin/cout" in problem B without something else, I think it must be TLE...

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

Div 2 D is the worst written problem ever. Even google translator has refused to help me in making me understand it.

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

What a shit contest. Div 2 D is hardly being understood and C is being solved by even those who might have never solved any other C in their lifetime.

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

    true, still made it harder for myself didn't read a[i] >= b[j] , hope i don't get a tle .

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

      I also got myself fucked in A because of a fucking reading mistake. And the sad part is that I locked the problem as soon as I submitted. :(

      Moral of the story ; Dont lock the problem unless you don`t see one or two hacks in the room.

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

    you haven't solved any C in any contest so far, so you dont have any right to comment like this

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

      I have solved C twice before too.

      The only thing is that, I got WA in systest in either A or B in those contests.

      Do your research properly from the next time.

      Just because someone has solved 2 problems in the past doesn`t mean that it needs to be A and B only.

      And I was not talking about this in-fact, I meant that there are people who haven`t solved a C even in practice sessions, and even they have solved C today.

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

Was expecting short statements but not this short...

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

I passed Div2 C just by reading examples :D

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

    I think most did same:)

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

      So.. Is there a necessarily proof that it's correct to do...whatever we did?

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

        Me too

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

        The function F(n,k) is largest when k is 1 and smallest when k is n. So you want the difference between n and k to be as large as possible so you can maximize F(n,k). So just pair the numbers so that the sum of differences is as large as possible (I think greedy pairing works for that).

        It's not exactly a formal proof but I think it's correct.

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

          ​I think this would give you the sum of expected values

          We can naively say that in order to maximise sum we need to maximise A[i] - B[i] + 1 . But that's not a rigorous proof either

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

        Once you prove/guess that F(n_i,k_i)=(n_i+1)/(k_i+1), the question is how to maximize the sum. The answer:

        https://en.wikipedia.org/wiki/Rearrangement_inequality

        So to maximize in this case, we need to sort (n_i+1) and 1/(k_i+1) in the same order, which is equivalent to sorting n_i and k_i in opposite orders.

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

          how is ?

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

            For each m<=n, look at the subsets of {1,...,n} whose minimum element is m. There are (n-m)C(k-1) of those (because once you choose m, you have to choose k-1 remaining numbers from {m+1,...,n}.

            Thus, the weighted average is the sum of m*(n-m)C(k-1) , 1<=m<=n, divided by nCk.

            Using some basic identities (hockey stick), this simplifies down to (n+1)/(k+1).

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

              Yeah I was able to derive the formula , but how do you get all terms cancelled . Also what do you mean by hockey stick ?

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

                https://en.wikipedia.org/wiki/Hockey-stick_identity

                But after thinking a little bit... it's not even needed! There's a simple bijective proof that the numerator equals (n+1)C(k+1).

                If we choose k+1 numbers from {0,...,n}, and throw away the lowest number, we get k numbers from {1,...,n}. How many times does each k-set get repeated? Precisely its minimum-element number of times!

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

                  DELETED (Sorry for my mistake , I get it) .

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

                  Nope, if you take a subset of size k+1 of {0,...,n} and remove the lowest element, you will always get a subset of {1,...,n} of size k.

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

                  I love this proof as it is so elegant and straight forward, yet, I still want to know how would you get rid of the (j*) prefix from this formula.

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

                  Then use the hockey stick formula for the inner sum, and again for the outer sum.

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

                  Thanks, got it now. :)

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

              "Thus, the weighted average is the sum of m*(n-m)C(k-1) , 1<=m<=n, divided by nCk."

              1<=m<=n? why till n? shouldn't it be till n-k+1?

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

                Sure. But it doesn't matter, since if m>n-k+1, the binomial coefficient will be 0 anyway.

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

    This is one of the frustrating things about competitive programming that make me hesitant to participate again. It is possible to get a problem accepted without being able to argue about the correctness. In mathematics and real CS, this is nonsensical, useless and completely unacceptable.

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

      Competitive programming is not math/CS. (I myself am a math/CS person, but I know that in competitive programming I might not need to prove correctness. On the other hand, having math/CS background helps to give intuition whether an approach will likely be correct or not.)

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

        It can be mathematics/CS if one takes the time to understand the reasoning. The fact that it sometimes encourages non-sense (by not requiring the contestants to actually understand their solutions) is one of the reasons I think it's sort of overrated. There have been times when I got introduced to some graph algorithms and was able to code them in a competitive programming environment without having a clue about why they worked. It's a relief that those times are over. I think many competitive programmers just use "pattern recognition" (of the form "I have encountered a similar problem before" or "the samples reveal a plausible approach") and end up ACing problems with a minimal or even nonexistent amount of the much-needed rational thinking. (Yes, I believe that is the case too for a number of competitive programmers who are highly rated on this site or even scored IOI medals and the like). Over the time, I realized that writing formal proofs and good code is more enjoyable for me than competitive programming.

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

      I think this is somewhat a fault on the problem setter's part — had they asked for the value of sum(F(A, B)) it would requires a prove for it. (Maybe they didn't asked for it since it's just Div2C .... but yeah I would rather ask for full feedback and use it as 2D or 2E)

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

    Worst Div2C ever!

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

    same here. but C and D had the worst sample explanations ever.

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

    Spent plenty of time Prooving and the greedy is correct during the contest, although I had observed the feature in the sample. Sad.

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

    how?? I am still confused as to what the question means and a lot of people have seemingly solved it by seeing the samples.

    "Consider all possible k-element subsets of the set [1, 2, ..., n]. For subset find minimal element in it. F(n, k) — mathematical expectation of the minimal element among all k-element subsets."

    This statement does not make any sense to me

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

      Consider all k-element subsets of the set {1, 2, ..., n}. For each subset, look at the smallest element in it. For example, when n = 4, k = 2, you have the following:

      • {1, 2} with smallest element 1
      • {1, 3} with smallest element 1
      • {1, 4} with smallest element 1
      • {2, 3} with smallest element 2
      • {2, 4} with smallest element 2
      • {3, 4} with smallest element 3

      Define F(n, k) as the average of all these smallest elements. So .

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

You know you are 100% sure of your solution when you lock your problem even after getting hacked

photo

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

    Actually I got that "hacked" notification real late. After making an unsuccessful hacking attempt on someone's code, I got the notification that my code has been hacked -_- . Don't know if it was my internet problem or something else.

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

I should have read the Russian statements.

I don't know how to speak Russian but it can't be worse than the English statements.

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

D is easy if you can understand it. I understood it but I can't solve it :'(

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

Is there anyone who got TLE in B div-2 just reading input and printing output

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

Me seeing the succinct statements>>>> hell yeah!

After reading statements>>>> wait, what ?

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

Problem D blew up my brain, how to solve it?

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

    I think if there is a -1 node, then an answer can always be formulated. But other than that, no clue

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

    When there is a -1 vertex, you can simply do a dfs and solve it greedily. When there isn't any, if the number of 1 vertex is odd you can't solve it (the sum of degrees of the subgraph should be odd which is impossible). This is as far as I got, in the case which is left I believe you can greedily solve it aswell but I'm not sure.

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

      I'll call d[i] == 1 vertices black and d[i] == 0 vertices white.
      So given the case where the number of black vertices is even we can solve it greedily.
      We can consider any spanning tree of the graph and do a dfs, let it return 0 if the subtree is solved or 1 if it is unsolved. Hence Black vertices are unsolved and white vertices are solved. Then we will put the edge to the parent if it is unsolved.

      If the parent is solved but not the subtree, after putting an edge the parent will become unsolved and the subtree solved.
      If the parent is unsolved and the subtree aswell, both will become solved.

      We can see that the parity of unsolved vertices is always the same, while running this dfs is simply pushing these unsolved vertices up. Then if the black edges are even at the start, we can simply push them all up the root of our spanning tree.

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

    There is an answer iff there is a -1 or there is an even number of 1's. You can then get the solution by doing a dfs and just greedily selecting edges you need on your way back up.

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

      Can you please elaborate why is there always an answer when d[i]=-1 for some i.

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

        It doesn't matter what degree the -1 node has, so all of it edges can be arbitarily choosed or not choosed. By using this we can fix every adjacent nodes to have correct parity degree, because we can either choose it's edge to the -1 node or not. After that we can make sure the nodes adjacent to the nodes adjacent to the -1 node are good, and so on. Because the graph is connected, we can make every node's degree good.

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

          Going by that logic if we satisfy parity of 3 using 1(the -1 node) we get stuck,don't we?

          4 3

          -1 0 1 1

          1 2

          1 3

          3 4

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

Why does this submission give WA on TC 5 and this submission give AC, when the only difference is the equality sign in the comparator function?

I think that the first one should also give AC..

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

Do you think 1 million number 10e9 can be read with ONLY "cin" in 2 seconds?

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

WHY WWWWWWWWWWW

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

I got Unexpected verdict on my hack in the solution on problem A and receive this result. What does it mean?

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

How to solve D?

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

    pick K elements which are different and remove them from the array permanently , keep repeating this process , in the end , we will have atmost K-1 elements left , those are the only possible candidates for our answer , this can be simulated with a segtree easily.
    Note that K=2 version has appeared before several times.

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

    I think you can just check the frequencies of all the possible candidates for the answer. Sort the subarray. Let sz = (R-L+1)/k. Then the only possible choices are the elements at indices sz+1, 2*sz+1, 3*sz+1... while <= R. Check frequency of each and if any of these satisfy the condition, then that is the answer.

    Time complexity is O(N*K*logN)

    Code

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

http://mirror.codeforces.com/contest/841/hacks

I was trying to hack @MrSoab B solution. I was giving ai=10^9 and n=10^6 as input and it was giving me invalid input why?

Then tried ai=10^7 and n=10^4 bt now i got unsuccessful attempt even though his sum variable was int declared which would overflow on this input?

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

Is there a better solution to D that NlogNKlogK if no , then why is the time limit so strict.

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

    There's funny solution to Problem D which it's complexity is O(cnlogn) or O(cn).

    First, We randomly choose the answer in interval [l, r], then check it.

    For even k = 5, there's nearly 0.2 probability that we can find it.

    Assume we randomly choose 90 times, we can deal with each query with correct probability 1 — (0.8)^90 = 0.99999999810286240993581145418021.

    So for a each testcase, the probability for all the queries are right is 0.99999999810286240993581145418021^{300000} = 0.99943102065261594539434408072871.

    We need to pass several testcases, assume there're 100 testcases, We can get accepted with probability 0.99943102065261594539434408072871^{100} = 95%.

    That's our destiny.

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

    And you can use some simple technology to reduce the complexity to O(cn). Something like Random for each query at first, then get the answer while inserting the elements to a hash-table.

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

    I did with something like sqrt decomposition and it atleast passes in pretest < 500ms

    Set Freq = 300. Max Number of heavy elements having > Freq = 1000

    Process all queries on heavy elements independently. Elements having freq <= 300 can only be answer where r-l+1 <= 1500. So bruteforce on those light queries.

    Something like O((N+Q)*1000 + (N + Q)*1500)

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

    Probably to defend straightforward Mo solutions.

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

    It is possible to solve it in time O(NKlogN) using a wavelet tree.

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

Can anyone provide a proof for Div1 C?

I got nowhere by trying to analyze the expected value.

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

Ok so I almost hacked V--o_o--V's solution for D but I couldn't submit the file because it was too big...later on, I got the answer to my question that I should send the generator...I guess nothing else can be done, now, can it? generally, what sort of syntax should the generator have? I mean does it write the test to standard output? What language should it be written in?

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

    You can choose among many languages. Yes, it should print the test to standard output. Once I luckily got 7-th place in Div2 which could have been 5-th if I knew this. I guess we both learnt it the hard way :d

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

    How to hack his solution? And what's the probability of hacking? :)

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

      A test with 60001 of 1 and the other values all distinct that's querying the interval [1, 300.000] 300.000 times would be just enough. The probability for his solution to work on one query is P = 1 — (4/5)^40. The probability for all the queries to work at once is P^300000 ~= 1e-14. It was failing on my machine after less than 20.000 queries usually. So it was sure deal:))The constant that he chose made it easy to hack. On the other side, if it were much larger than that, he'd get TL

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

        I have 80 as constant :D
        Had pretests passed, not sure about TLE.
        But seems like it's going to fail as well.

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

          On my test, you get 99.4 percent probability of correctness, which is pretty much enough I think. Even if this extreme test were used 100 times in a row, you'll still have a 58 percent chance of getting AC, and for sure there won't be more than 5 or so tests like this one. Also, this test is the worst scenario, so it seems your solution will pass. If they really wanted to make sure it wouldn't pass, they'd have put K <= 8-9 which would destroy any such approach. Honestly, though, I find the randomized approach quite elegant

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

CF admins, why do you let it happen? 674G - Choosing Ads

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

Am i the only one who solved Div.2 C by just looking at the samples, without understanding what the author wanted???

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

Waiting Petr screencast to see myself being hacked. :)

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

Very bad statements (Guys using the Russian statements have an advantage), Long queue at the first 30 mins, Very weird hacking/locking problems bug in my room (not sure about the others).

This contest will be unrated right ?

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

    rated or unrated, I really hate to say this (cause CF really helped me improving a lot) but last few CF contests were really awful and not to forget that there were back to back two unrated contests.

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

    Anyway it was understandable, mistakes were grammar mistakes.

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

      Usually I don't complain about grammar if it costs me a few minutes. But today's B took me 45 minutes to understand, and only after backsolving from examples. When variance in read times dominates variance in solve times, then we're measuring the wrong thing.

      It's not like I didn't try either; I asked very early on for clarification, and got no response.

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

Div. 2 C and D were both shots in the dark for me.

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

Any suggestions on how to approach Problem D?

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

Am I the only person that all problems felt too hard? T_T

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

I was trying to hack @MrSoab B solution with ai=10^9 and n=10^6 it was giving me invalid input why?

then I tried with ai=10^7 and n=10^4 and got unsuccesful even though his sum variable should overflow as he declared it as integer

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

    1) Because you can upload only 256KB input test (maybe) 2) overflow don't mean result is wrong :))

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

Div. 2 C and D were both shots in the dark for me

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

I guessed a solution for div 2 C based on the examples and it passed the pretests. I sorted A and sorted B in reverse and paired them. But is it actually the solution? How does one prove that this works?

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

    Prove that if n1 ≥ n2, k1 ≤ k2, then F(n1, k1) + F(n2, k2) ≥ F(n1, k2) + F(n2, k1), so it's always at least as good to assign n1 to k1 and n2 to k2, instead of n1 to k2 and n2 to k1. This means if you sort B in increasing order, you always want to have A sorted in decreasing order, since otherwise you can do better.

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

    it works because we have min(A)>=max(B) and we have to maximize the sum of A'[i]-B[i] .

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

Achievement unlocked : Successfully challenged a randomized solution

http://mirror.codeforces.com/contest/840/submission/29578088

Phew, I pressed the hack button while hoping that I won't be very unlucky.

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

How to solve Div 2 D ?

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

    If it's a tree, the problem is trivial. But it turns out that the extra edges don't have to be used... so just treat the graph as a tree.

    It's possible if and only if the number of "1" labels is odd. So if there are any "-1" labels, it can always be done (replace all "-1"s with "0"s, except for possibly one "1"). Then do a depth-first search; the edges adjoining the leaves are forced, which forces all the edges all the way up to the root.

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

      Can you give me some similar problem to this, which you called trivial? I wanna try to solve that problem

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

        What I meant is the following.

        Suppose we have a tree (connected graph with no cycles). In this tree, the vertices are labeled 1 and 0; the goal is to choose a subset of "special" edges such that the vertices labeled 0 have an even number of special edges adjoining them, and the vertices labeled 1 have an odd number of special edges adjoining them.

        This problem is quite straightforward, and once it's solved, it's easy to extend to a generic connected graph (even with multiple edges: it makes no difference).

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

      can you explain why the extra edges don't have to be used..

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

        In a cycle, every node has degree 2. That means that if you remove all cycles from your solution, it will still be correct.

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

Div2 e. Kirchhoff's theorem + Gauss method? I just couldn't find matrix determinant.

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

    The answer is not determinant of the adjacency matrix, it is the permanent. Computing permanent however, is NP-hard.

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

The task statements were very bad, but I think that the tasks were still understandable after reading them a few times. It's very annoying and should have been fixed before the contest, but it's really not a reason to make the contest unrated.

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

That moment when you don't understand any of the problem statements and manage to solve them successfully. xD

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

The task 841B How is it possible to have TLE on the pretests for the loop from 0 to 10^6, used to input data anyway, with the task's limit of 2 sec. GNU C++ 11 Thanks.

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

The Problems' statement was understandable to some degree,maybe was below average this time,but you could understand it.. that's how it was for me, It shouldn't be unrated :D

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

Got TLE on B using simple input , output only Can't understand why???

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

    Apparently, you need to use the IO 'accelerating' lines at the beginning of your main (if using C++):

    iostream::sync_with_stdio(false);
    cin.tie(0);
    

    to stay within the time limit

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

Any hints for Div1 E?

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

    Divide all mask into two halfs.

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

    Process all numbers within path by blocks of 256. For each bottom vertex of a block and each value of biggest 8 bits of XOR we can precompute the partial answer in 8 * 256: for each number there is a unique value of biggest XOR bits that make 11111111... after XORing (these will obviously be largest answers in their groups), after that traverse a tree from bottom to top and fill still unknown values by swapping smallest bit possible.

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

Как это может быть, что задача 841B не проходит по времени на претестах, когда используется один цикл для ввода от 0 до 10^6. GNU C++ 11. Спасибо.

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

    Ни у одного тебя, не переживай. (ну или переживай, как хочешь). Хотя странно, что у некоторых падает сейчас на системных тестах, а у некоторых на 7 предтесте упала (притом, компилятор и код фактически идентичны)

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

How to solve Div1 C? Ok well we can divide the numbers into some equivalent classes.... and so what?

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

    --nevermind, this is probably wrong solution

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

    Say you divide the array in groups of sizes X1, X2, ..., Xk. For now, lets consider all of the members of same group identical. In other words label them, and add a constraint that they appear in that fixed order.

    Then, say there exist xi indices in group, which have next element in the permutation belonging to the same group. Then the number of such orderings is:

    Now, we can just use inclusion exclusion on the total number of indices where the next element is in same group. Such a term must be multiplied by when added to the total answer.

    To find the sum over all tuples of xi, we can use polynomial multiplication.

    In the end, multiply the answer by to account for orderings in same group

    I think this could have made a good FFT problem.

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

      If I understand correctly the answer is:

      but could you clarify how this can be calculated using polynomial multiplication? I can't think of how to separate .

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

    f(i, oldBad, curBad) = ways to place i, i+1, ..., n-1 if we have placed 0, 1, ... i-1 and there are curBad pairs of consecutive numbers of the same class as i and oldBad pairs of consecutive numbers of the same class, but different of the class of i

    answer is in f(0,0,0)

    I guess you can figure out the base cases and how to do the recursive step :)

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

    https://csacademy.com/contest/archive/task/distinct_neighbours then you solve this and you're done. It has an editorial, a really nice dp

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

      Lol, I opened that problem and it is solved by me. But I didn't manage to solve it again today [facepalm]

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

      What is the time complexity of the DP solution described in the editorial? I'm having a hard time trying to figure it out.

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

        Indeed, it wasn't trivial to compute. At the time I solved it, I computed an upper bound of N^3

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

          At first glance, it seemed N^4 to me. How did you get the bound of N^3?

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

            Ok, so let us consider my code. The time-consuming part — the one with 4 fors — is actually N^3 because the first and third fors have a total complexity of O(N). The first one is basically choosing the color and the second one (it loops, in worst case till F[i + 1] which is the number of balls of that color) is basically choosing the ball, so the complexity of these 2 fors would be equal to the number of balls (which is N in our case). I know I haven't defined the term of ball or color but it should make sense anyway

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

Was Div2C inspired by Problem 2 from International Mathematics Olympiad 1981 ? Probably a coincidence but I was reminded of it just after reading the statement. (Also, not good problem for a programming competition, in my opinion — many people saying that they just guessed the solution).

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

Not doing this for fun but need to ask this.....Is it rated ?

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

Solving problem A be like

(idea from afaji321)

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

Any hints for Div2E/Div1C?

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

Something wrong with A problem validator because my hack (2 3 ab) was recognized as incorrect test, but it is obviously not true.

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

Can someone say why this code didn't give RTE (in pretests)? — 29563087

int a[n];
for(int i = 0; i < n; i++) {
    cin >> a[n]; 
    .....
}
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    Because it's undefined behavior, so anything can happen.

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

    a[i] you mean !

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

      Why would I even say cin >> a[i] will give RTE? -_-

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

        It's gives RTE because you used n instead of i that's what I want to say !

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

          Did you even read the first line?
          Can someone say why this code didn't give RTE (in pretests)?

          [Anyhow that submission isn't mine. It is of an IMO guy, this is his first contest in CF :) ]

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

            aah sorry ^^

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

            // Implementation practice (Have seen the editorial)

            He has written this on top, Now I get why its beneficial for IMO participants to get better easily. xD

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

    An array is simply a continuous memory segment, so as long as it doesn't go outside it is fine. For instance, this code will print 1..n.

    int n;
    cin >> n;
    int mem[n];
    int i;
    for(i = 1; i <= n; ++mem[n]) cout << i << endl;
    

    as the n-th position in the memory segment is int i.

    EDIT: I've been trying to reproduce this and doesn't seem to work.

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

      No, I think your code will run into an infinity loop.
      even if you set i = 1, mem[n] will have some garbage value!
      In my machine it runs into infinity loop! So i isn't n-th position in the array. It is just undefined I guess.

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

        I tried it several times I believe it depends on whereever the compiler decides to allocate the data. In any case the point still stands, a[n] is simply one more position in the memory, so accessing it will not give RTE although it might give unintended behaiviour

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

Хороший проблемсеттер, и систесты интересные

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

Unrated contest?

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

IS IT RATED?

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

It'd make an interesting statistic if we can find the ratio of submission passing system tests vs the ones that passed pretests for each problem.

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

It will be longest systest ever

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

Hi.

The problem 840D is really similar to this problem.

The solutions for these problems are also similar:

Code for PATULJCI

Code for 840D

UPD: Also, netman accepted the similarity between these two problems.

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

The limits of Div 2 B are too strict participants are getting TLE due to I/O issues and there was no mention of using Fast I/O in the problem

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

I give up.(ignore)

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

    It happens. I think it has happened to everyone at least once. Next time you will use fast I/O. Get over it.

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

      Let's say I get over it, it doesn't change the fact the the problem setter did a shitty job.

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

        Beyond the (very) bad problem statements I don't see why would they do a "shitty" job. I/O problems aren't rare in CF contests, and they can't really do anything against it. They can't test every language for every I/O to see if the intended solution passes.

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

I remember in the Div 2 contest I saw 2000+ people passing pretest for C and thought I was doomed, and now only see ~400 attempts... is it my hallucination?

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

In Div2 problem b many contestants got TLE in pretests and main tests. But same code got ac. http://mirror.codeforces.com/contest/841/submission/29560214 http://mirror.codeforces.com/contest/841/submission/29560699

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

Why are systests so slow? Is KAN running judge on his own computer?

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

    Because div2A(which is like a+b) has 110+ tests and was solved by ~3500 people.

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

    There are 32 pages of TLE on Div2 B. This could cause unexpected slowness of systests because it was submitted by much more people than usually submit a problem that can theoretically got TLE.

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

    Nikolay KAN is not the coordinator of this contest, ask netman instead.

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

Почему решения так долго тестируются?

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

can anyone explain ,why my solution is giving tle . solution

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

    ios_base::sync_with_stdio(false);

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

    Change cin / cout to scanf / printf. Don't use cin / cout if you have some constrains N ≥ 106

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

      but constrains N ≤  10^6

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

        Most probably your browser isn't JS supported.

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

        Yeah, but each of the 106 numbers can have up to 10 digits, which, including spaces, adds up to 11 MB of input. <iostream> can have give TLE on problems with such large IO even with the ios_base::sync_with_stdio(false); crap. To be safe, just use <cstdio> when you see even a couple megabytes of input (or output).

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

    Just add fast I/O, i.e. add these two lines in top of main:

    ios_base::sync_with_stdio (false);
    cin.tie (0);
    
    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      But is it fair.Is their no value for the idea which is 100%correct and just because of Input we are getting 0

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

        Well, you are partially correct, but it is Competitive Programming, it is like you are in racing, so you have fasten your belt to not get injured in accident...

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

    Because you use streams cin/cout that work for a long time. Just use scanf/printf and you will be happy) (sorry for my English)

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    for(int i=0;i<n;i++) {
            cin>>a[i];
            sum+=a[i];
            if(a[i]&1) cnt++;
        }
    
    a[i] is equivalent to *(a+i) in c++
    

    Accessing array element has cost of additional operations. Doing this million time is taking some time.

    http://mirror.codeforces.com/contest/841/submission/29562890 simple cin/cout is passing in this solution.

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

My Grandma is faster than the systest :/

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

RIP randomized solutions on D :')

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

    Nevermind, yeah this doesn't work.

    Guess the intended was to calculate cnt(value, left, right) in O(1) with something like Mo's and doing close to 500 iterations of random choice

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

      I have a divide&conquer approach with K(N+Q)logN complexity. It works pretty well in practice (<700 ms on pretests and I didn't even try hard to optimize the constant). It works with O(K*N) memory if you can handle the queries offline or with KNlogN memory if you need to do them online

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

        Is your solution deterministic? Cause I remember in exactly the same problem 674G - Choosing Ads, all solutions weren't.

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

          It is deterministic. The first observation is that the answer, if it exists, for an interval is, when dividing this interval in 2 others, among the most frequent K — 1 numbers in each of the 2 subintervals. Now, try to solve all the queries offline by using divide&conquer. Solve (left, right) would solve all the queries with left <= x and y <= right. You fix mid = (left + right) / 2 and recursively call the function. Then you just need to handle in O(right-left)*K the queries that have left<=x<=mid<y<=right. You can do so by precomputing for each i:

          1) i <= mid, then you precompute the most frequent K — 1 values on [i, mid]

          2) i > mid, then you precompute the most frequent K — 1 value on [mid + 1, i]

          Now, using this precompution, you've narrowed down the set of possible answers to one of size O (K). you could make an extra check for each of them in logN (to compute its frequency with some easy lower/upper bounds) to see which of them are the really solutions. Now, for each query, you've made O(K) checks of logN each, and overall, you have KNlogN for precomputing, at each step those values.

          The precomputations are easy to make if you traverse the array from mid to left and then from mid + 1 to right and keep a frequency array and those K — 1 most frequent numbers so far

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

It's unfortunate that many O(n) solutions are failing due to I/O (mine will likely also fail); however, I think that if any solution fails for not recognizing the need for fast I/O, all solutions that don't consider fast I/O should also fail — otherwise, the test cases should be considered weak. Currently, several solutions using cin/cout without toggling off synchronization still pass at around 1900 ms. Most of the solutions that pass return once an odd number is found, which suggests test 49 contains an odd number and that the test cases don't contain something like:

1000000
1000000000 1000000000 ... 1000000000

Rather than failing all the accepted solutions that should TLE, the better answer would probably be to re-run all TLEs with a slightly higher time limit.

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

Div2.B test#49 is brutally savage

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

System testing is not finished yet. I bet it will be after 2 hours since the end of the contest.

Looks like checker to verify the solution needs as much time (or more) as a participant to submit...

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

codeforces servers be like

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

Codeforces Div2 Contest for me are like typing contests now a days. Do Easy ones as fast as possible !!! I am never able to solve tough problems :(

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

    ...And don't forget to use fast I/O. Still, I hope we can slowly improve and get to Div1...

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

The fastest system testing EVER

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

Any idea for Problem Div2 D?

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

The problemsetters:

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

1 hour and 30 minutes passed from beginning of systest, still not checked 30th minute...

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

    Luckily number of submissions through time isn't constant, as the test is already at 50%.

    So measuring by the submission times isn't too good.

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

when I see many code for B got a accepted with time 1900ms

oh isit rated?

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

Any idea why people are getting TLE in Test Case 49 in Div2B?

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

system testing is like

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

The system testing seems kinda... frozen.

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

Systest running in O(N^N) :/

Wake me up when it ends.

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

In Div2 C Does anyone have a solid proof of why matching higher n in array A with lower k in Array B always work? I spent 40 mins trying to prove it, then got bored and submitted!

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

    By the rearrangement inequality,

    is maximized when A' is increasing and B is decreasing.

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

      Excuse me, but how did you arrive at that final simplified equivalent of the function ? Also, how can there be multiple valid answers for such function?!

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

        by application of the Hockey Stick Identity.

        What do you mean by multiple valid answers?

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

          Wow! that's very satisfying! Thank you.

          I meant how could there be more than one valid permutation?

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

            I mean, obviously if you have A = {4, 5} and B = {2, 2},  then both A' = {5, 4} and A' = {4, 5} are valid. Other than something like that, I'm not sure what you are talking about.

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

              Quick question: Did you actually prove that in contest time or trusted your instinct? :)

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

                I actually proved it, as the Hockey Stick Identity is fairly common in contest math.

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

        Multiple answers came due to repetition of elements in given array

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

      Is there any mathematical proof for when A' increasing and B is decreasing then the sum of (A'+1) / B can be maximum?

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

        0) Let's transform (A + 1) to A and (B + 1) to B. Currently A and B are natural numbers.

        1) Let's consider the situation for 2 elements: A0/B0 and A1/B1. We will compare A0/B0 + A1/B1 and A1/B0 + A0/B1 assuming that B0 <= B1.

        If B0 == B1, it doesn't matter how to order A-s.

        Else if B0 < B1 ("A0 = A1" is not interesting in this case), let's consider the inequality: A0/B0 + A1/B1 > A1/B0 + A0/B1, B0 < B1.

        We will transform it to the EQUAL one, so the result we will receive can be applied to the initial inequality. We are going to find out the relation between A0 and A1 to satisfy the inequality.

        A0/B0 + A1/B1 > A1/B0 + A0/B1

        (A0*B1 + A1*B0) / (B0*B1) > (A0*B0 + A1*B1) / (B0*B1)

        [B0,B1 are natural, so B0*B1 > 0]

        A0*B1 + A1*B0 > A0*B0 + A1*B1

        A0 * (B1 — B0) > A1 * (B1 — B0), B0 < B1 === B1 — B0 > 0

        A0 > A1

        So if A0 >= A1 and B0 <= B1, we will get the maximal sum. We have to sort A-values by descending and B-values by ascending.

        2) Let's suppose that this way to sort A- and B- arrays leads us to the maximal sum if these arrays contain k elements for some k: A{0} .. A{k-1}, B{0} .. B{k-1}, and B{i} <= B{i+1} for all the acceptable "i"-s and "i+1"-s -- and they are sorted.

        3) If considering (2) to be true it works for k+1 elements, then if (2) is true, it will be true for any arrays of 2 elements and longer.

        So we have 2 arrays: A and B of k elements as mentioned above. We are adding new elements A{k} and B{k} and we want to understand in what cases the sum will be maximal.

        Let's put A{k}-B{k}-pair between the elements in order to keep our current B-array sorted. Now B is sorted but A is maybe not.

        a) A{0} <= A{k} <= A{k-2}, if the array A{0 .. k .. k-2} is unsorted, we can increase the sum for the 1st k elements or keep it the same if we sort these elements only in A-array by descending order, according to our hypothesis in (2). After that, our new element probably can be placed right before the last element in the A-array. If the last element is more than the new one, we can swap them in order to increase or to keep the sum for all the k+1 elements.

        b) A{1} <= A{k} <= A{k-1}. Like in (a) the same logic can be applied.

        Anyway, we will get our k+1-arrays sorted. Let's prove that the current sum for the k+1 elements is maximal.

        Let's imagine that it is not true, so there exists another unsorted order of elements that leads to maximizing sum value. But if these elements are unsorted we can again apply approaches in (a) or (b) to increase the sum, but it contradicts with our last assumption.

        So we have proved with the mathematical induction method that the sum will be maximal in the case if A-array will be sorted by descending and B-array by ascending, or vice versa (as you wish :) ).

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

I do not understand, why does this solution 29564049 get WA in problem div2 A?

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

    I have WA 39 too and same solution. It is because you forgot read '\n' from stdin.

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

      thnx for ur reply, but then why in test case 39? shouldn't it get wa in sample test cases?

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

        No. Because in sample tests (and moreover in system tests up to test #39) to get answer it is enough to read n-1 characters from the second line. So, for example, test like test #39.

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

      check this solution 29558710. i do not understand, does the judge data contain symbol other than [a-z]???

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

        No. In this submission before "%c" goes whitespace, therefore '\n' was ignored.

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

2 Hours for the Contest and 2 hours for the System test. Add 1 more hour. We will be a testimony of 5 hours regular CF Round.

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

Waiting

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

Why tle in Div2.B my sol

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

I have never seen such a lot of submissions

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

This is what happening while testing.

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

Longest 'System Testing' ever!

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

Ideas for Div2D/1B?

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

    I've thougt about corner cases:

    1) If there is vertex with -1, then this vertex is an answer
    2) If there are two vertex with 1 and between them all zeros, then this path is an answer
    3) Else we have at most one vertex with 1 and rest of them have 0. I assume that answer is cycle of zeros. If there not any, then solution doesn't exists.

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

    Only when there isn't -1 and number of 1 is odd we can't find subset.

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

      Wrong

      4 4
      1 0 0 0
      1 2
      2 3
      3 4
      2 4

      Answer is

      3
      2
      3
      4

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

        what with 1?

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

          Nothing, we must choose some edges, you can choose cycle of vertex with di = 0. This edge set satisfies condition.

          Also you can have three vertex with di = 1 and still get solution — any path 1-0-0-....-0-1 will be solution.

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

            Maybe I didn't understand the problem but in your solution vertex 1 don't have any edges.

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

              In input graph vertex 1 with d1 = 1 connected with vertex 2 with d2 = 0.

              Problem is choose subgraph (not neccesary choose all vertex). In test above you can choose cycle 2-3-4-2. Each of vertexes ( in subgraph ) has degree of 2. Since 2 mod 2 = 0 and d2 = d3 = d4 = 0 this cycle is answer.

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

                I have AC.

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

                  Checked your solution. We have different understanding of problem. So mine is wrong. I've thought that you need to choose subgraph, not all vertexes and some of edges.

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

        If that's the case, then the first sample should have a positive answer (by taking no edges, thus vertex 1 doesn't belong in the subgraph because it's isolated).

        The statement is indeed unclear, but the subgraph is supposed to have all the vertices from the input.

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

      Interesting! Do you have a proof?

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

        I think so. When we have odd number of 1 then sum of degree is odd and this is wrong. When we have number of 1 even then we can match vertices with 1 but we are looking only on dfs tree. When you find partner for some 1 then you can change edges on path between those vertices 0->1 and 1->0.

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

I have to say that this was very useful for Div 1 C!

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

    I've tried to check the recurrence (1.1) from the given paper on pretest 1, and for some reason it does not work out, even though in my understanding it is supposed to solve the same problem:

    M(1, 2) = M(0, 2) + M(1, 1) - M(1, 0) = M(2) + M(1, 1) - M(1) = 0 + 2 - 1 = 1
    

    While the expected answer is 2. Would appreciate if someone could point out my mistake.

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

Am I the only one who can predict the outcome of the round only by author's usernames?

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

Is it rated?

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

What the writers of this round need:

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

That moment, when you search in accepted submissions for one similar to yours, so you can sleep calmly without doubts.

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

hi Fedosik.About div2B, n ranged from 1 to 1e6. why a code of O(n) would be TLE by just using cin. because my rank change from 200 to 1k. I hope this will be unrated because of the data of div2B and the statement of div2D.

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

I think the rating updates will be available on the next year

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

Finally my last submission got tested! I hope rating changes will be available by the time I go to sleep(probably not though).

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

Did somebody note when systests started? Would be good to have an exact entry as Guiness World Record of the slowest systests ever.

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

ради бога объясните что это вообще означает "если оставив в исходном графе только ребра из него, то для каждой вершины i будет верно, что di =  - 1 или ее степень по модулю 2 равна di."

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

    Чтобы понять это нужно быть экстрасенсом

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

    Просто в задаче не объяснили, что такое степень вершины — простыми словами, количество инцидентных ей ребер.

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

      извините, но вы объясняете, прямо как в задаче,слииииишком трудно понять:_( как нибудь полегче можно?

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

        После того, как какие-то из ребер убраны, для каждой вершины V считается X — количество ребер, один из концов которого равен V. (Сколько ребер связанных с вершиной V остались неубранными)

        Дальше для каждой вершины V должно выполняться условие или d[V] == -1 или d[v] = X % 2.

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

when the code fails system testing

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

Пацаны, выкладывайте уже разбор. А то я в С впихнул жадность наугад, а доказывать не умею.

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

It was a nice contest but system testing has taken so long XD

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

Waiting for too long... -_-, some more time for ratings update :(

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

It looks like Mike is personally calculating our codes' results. Don't use too much modulos guys, he have to calculate it twice then.

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

    Mike's motto: "Wanna do something perfectly, do it by yourself."

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

    I had no idea how long systesting takes. Since I slept ~4 hours for 3 recent nights I set up alarm for +3 hours and fell to a bed. Now I'm updating the rating and I see you have the 3 place and +20 to rating. Congrats!

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

Div 2 C. Both solutions are identical, both FPC, both must run in O(n+n log n). Strangely mine gets TLE at 47.

29576388 29572292

Sorry for Pascal.

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

I think this result looks weird... It passed pretest 6, but failed at system test 6.

(Image is guoyu1098's Div1 D submission log) Also, dotorya's Div1 D has similar result.

And We could know that ~16 is pretest(from dotorya's submission), but kmjp locked and system falied at test 10. Why this happened?

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

    Actually, kmjp used rand() in his code, so it makes sense.

    But I don't know why my execution time changed between pretest and systest. (My code didn't use random function, except for srand() for debugging)

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

    Maybe the sumission was close to the time limit and aa the server was overloaded by sumissions, it took a little more to judge them

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

    The pretests and actual tests are different.

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

It is over

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

System test took 5 hours to run... is this some record

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

First Stage of hell Completed.

Loading Second Stage.. Please Wait :D

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

stay all night.....QAQ

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

Why CF-Predictor Rating extension not working ?

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

Rating calculation is over I can go to sleep :)

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

Good contest. I enjoyed the problems. The second problem was quite elegant.

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

Why my div2 B O(n) solution got tle only because of cin/cout? Problem setters and testers must check this very carefully even for future contests.

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

    I believe it is expected of contestants to know when to use fast input (10^6 numbers takes a lot of time to read using cin)

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

      Yes but I believe it shouldn't get tle only because of input/output that too when it wasn't mentioned even.Also a lot of participants got AC by using cin/cout.

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

        I think the AC solutions with cin did not have it synced with stdio, which makes it faster. Still, whenever the input is larger than 2 x 10^5, I don't think it is a good idea to use cin (even without syncing it with stdio).

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

          I didnt sync it with stdio.Yes I understand that its not a good idea but if it costs TLE then it should have beeen explicitly mentioned in the problem statement to use fast ip/op.

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

            Just checked your solution, you had it synced with stdio (it is synced by default). If you add the following line to the beginning of your code, it should give AC: cin.sync_with_stdio(false);

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

          To avoid this situation just use scanf

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

Div 2,b problem gives TLE on 7th test case, please help

include<bits/stdc++.h>

using namespace std;

define ll long long

int main() { long n,cnt=0,x;

cin>>n;
for(long i=0;i<n;i++){
    cin>>x;
    if(x%2==0)
        cnt++;
}

    if(cnt==n)
        cout<<"Second"<<endl;
    else
        cout<<"First"<<endl;

}

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

It turns out, valid Scala submissions (29558424) were failing in this round with Runtime Error java.lang.NoClassDefFoundError: scala/App$class :(

Looks like the Standard Scala Library was not included in the classpath for some of the invocations.

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

Memory limit exceeded on test 74 (out of 79). I guess universe doesn't really want me to be red.

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

Please public the editorial :(

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

Where is editorial?

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

If the system testing was so long suggest when we shall see editorial

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

Can somebody please help me? I don't know why my solution for Div2.C got TLE.

29576537

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

    Vector's erase linear on the number of elements erased (destructions) plus the number of elements after the last element deleted (moving), so erasing vector's first element may take times if vector's size is large.

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

For Div2 C, it was like if you observe the input you solve the problem but for me I think the property of A[] that all its elements are bigger or equal to the elements of B[] should be turned to for all i : A[i] >= B[i], this will make the problem a real C-problem i think

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

Wondering if anyone did any math to solve Div2C/Div1A?

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

    Yeah, me :)

    I proved that then found solution without looking sample cases :)

    But, just observation on samples does work :(

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

      It's impressive if you read the problem statement, proved correctness and got it accepted in 15 minutes.

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

        It wasn't 15 minutes :)

        Firstly, I read problem C and found value of F(n, k) then I saw many people solved A, so I passed problem A. That's why I solved A in 9 minutes.

        Finding value of F(n, k) is really easy with some basic combinatorics + probability and I think proving correctness in 10 minutes is enough for someone who have some math olympiad knowledge.

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

          Did you also use Hockey Stick identity in your proof? I saw an elegant proof here in the comments, using (k+1)-element subsets of the set [0,1,..,n] and throwing the minimum element. What was your proof?

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

            That was my writing during contest, I know how my handwriting is beautiful. Everything I used is Pascal's identity. If something unclear (probably everything :D) please tell me so I can explain.

            P.S. I did silly mistake in left bottom (crossed area) so I got as result, my face was like that there (with dafuq emotion :D) :)

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

              Good! You kinda followed the proof of Hockey-Stick Identity using Pascal's Identity. I came across in the comments on this post a very beautiful solution: take (k+1)-element subsets of the set [0,1,...,n] and remove the minimum element from each subset. You will be left with k-element subsets. The interesting thing is that, i will be the minimum of these subsets i times which is exactly what we want. So the result is n+1 choose k+1.

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

Did someone solve proble Div2/C with proof?

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

I find the test data is not strong enough in Div2 D/ Div1 B[problem:840B]. Some Ac code have a wrong answer with the test: 3 1 1 1 0 1 3 Have a result 0 while the right answer is -1.

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

Hi guys please help me... I wrote a code for Problem D/ِDIV2

this is my code: 29600735

I got WA on test 6 and checker comment is: "wrong output format Unexpected end of file — int32 expected" but the output format is ok!

Where is my mistake??

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

MikeMirzayanov, netman: it looks like something fishy was going on with the timing of my submission for D. I have resubmitted my solution from yesterday's contest that got TLE (2.5s) after adding a comment to it (so the resulting program is exactly the same), and it passed all tests in 1.7s.

TLE during contest: http://mirror.codeforces.com/contest/840/submission/29570473 OK in practice with 1.5x margin, same code: http://mirror.codeforces.com/contest/840/submission/29601182

Could it be that the system was overloaded yesterday and thus was giving a bit more TLEs? Maybe it's too late now, but please consider rejudging yesterday's TLEs and/or investigating the timing instability.

Thanks!

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

    (I realize that my solution initializes random generator from current time, but given that we query the random generator millions of times, the effect of that should average out very well)

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

      I've submitted it 3 more times today, and the timing is consistently under 2s.

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

        Everything written below is specific to Java:

        This happened with me too in practice a couple of days ago. I submitted a solution to one of the problems that passed in 1714 ms / 2000 ms.

        On reading my code again a couple of days later, I realized that a part of the code was unnecessary, and I deleted it and re-submitted. But, to my shock, this time it got TLE.

        I resubmitted instatntly again it and got AC in 1994 MS. I thought of writing a blog, but didn't do it on fear of down-votes.

        Is it possible for runtimes to differ by as much a 250+ ms ?

        1st submission : Link AC

        2nd submission : Link TLE

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

    Interestint. But you can use the ChairmanTree. The "K" is very small.

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

      From what google says, "ChairmanTree" seems to be the same thing as a persistent segment tree. I'm not too sure though, can you elaborate on this data structure?

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

Please, investigate why with C++11 compiler we had the TLE for the Div2-B. It hasn't happened for C++14. If it is a compiler issue, please remove this compiler from the system. Thanks.

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

    It is not a compiler issue. You just have to use fast I/O: reaf and printf Also, you can add these two lines at the start of your main method: ios::sync_with_stdio(0); cin.tie(0);

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

Did anyone except me have solved problem E Div 2 using inclusion-exclusion principle ?

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

I thought I solved problem C Div 2/A div 1 in O(nlogn) time but I'm still getting TLE Can anyone help me speed it up? (http://mirror.codeforces.com/contest/840/submission/29610925)

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

    It looks like your nested for loop is making it O(n2). Also you don't need to check if B[j]>A[i] you are told in the question A[i]>=B[j] for all i,j.

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

How to do div2E ? any hint ?

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

    If a and b can't be adjacent, and b and c can't be adjacent, then a and c can't be adjacent.

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

      After removing squares from the number, it becomes, for a and b, a must be equal to b to make their product be a perfect square.

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

sorry,but tutorial pls?

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

Please provide the editorial!!

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

Would you please made a contest unrated for me? I am into problem solving more than choosing appropriate method to read from input.

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

Since the editorial is taking a long time to upload can someone explain me DIV2 / problem D concept ? I am unable to devise a solution for this problem? Thanks in advance.

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

    if the number of vertices with d==1 is odd and no vertex with d==-1 exists then it is impossible to find a solution otherwise there is always a solution! try to prove this! then change d of any vertex with d==-1 to 0 or 1 in a way that remained graph have a solution!

    now consider one of spanning trees of the graph, it can be obtained by a dfs or similar! there is several ways one way is construct the needed subgraph from leaves of tree! in each step it's obvious an edge between a leaf and its father should be in final subgraph or not (if its d is 1 add upper edge to final subgraph, change the d of its father to 1-d and remove it from tree. otherwise only remove the leaf from tree) continue removing leaves to become the tree empty! 29595499 {sorry for my poor English!}

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

      I guess in first line of your answer... after" no of vertex with d==-1" you missed something? And it is really hard for me to prove the hypothesis.

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

        I edited that to make my mean more obvious! tnx :)

        the constructive alg I said can be used as a proof to! :) prove it by induction when u remove a leaf the remained tree has smaller size,is connected and parity of the number of vertices with d==1 is the same as previous tree!

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

          For the following test case ::

          4
          0 1 1 1
          1 2
          1 3 
          1 4
          2 3
          2 4
          3 4
          

          Number of vertices with d==1 is 3, and there is no vertex with d==-1. But the answer for this test case is not -1( That is solution exists) And the solution is 0. Correct me if I am wrong? And I really appreciate that you are replying to my silly doubts? I am not that of a coder :P

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

            In any graph summation of verices degree is even... The proof for impossibility in case like these!

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

Разбора я так понимаю нет?

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

What should be the output for the problem DIV2 / problem D for the following test case

4 6
1 1 1 1
1 2
1 3
1 4
2 3
2 4
3 4

Please also explain How you got to that output? Thank you in advance.

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

    Any pair of edges that don't share a vertex will work. For example, 2 1 6

    That is, the edges 1-2 and 3-4. Every vertex will have 1 "good" edge incident to it, which is odd.

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

      i have one doubt ... If we remove edge number 1 and 6....So in the remaining graph all the vertex from 1 to 4will now have even degree.. and therefore (degrre%2) == d[¡] condition will be violeted ?? Correct me if i am wrong

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

Has there been anyone who passed Div 1 D with the Probabilistic Approach?

If I set the limit too high, I get TLE and WA for too low limit. Do you have any suggestions?

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

    Use Mo's algorithm so that when you process a query [l, r], you can get the number of occurences of a number v in [l, r] in O(1) time. My solution in upsolving tried randomly 70 times and passed. The complexity is , where C = 70 is the number of times you try for each query.

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

      Well, this is so unfair :'( , in my current random solution where C_max = 50 (I even change C in relation to k) and the complexity is O(N + 3 * C * Q * log(C)) and I still getting TLE :'( (only WA if I reduce C), how can an O(N * sqrt(N)) algorithm works when N = 3 * 10^5?

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

        It should work comfortably since Nsqrt(N) is like 1.5*10^8 for N≈3*10^5 and the constant factor seems low. The key is that you want the effects of increasing the number of trials to have minimal impact on your complexity.

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

Автокомментарий: текст был обновлен пользователем Mediocrity (предыдущая версия, новая версия, сравнить).

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

Does anyone get access to the editorial?

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

Будет ли русская версия разбора?

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

Год назад на скамейке в общественном парке Леха нашёл массив из n чисел. (Div2 E)
Год назад я сидел на скамейке в общественном парке (Oxxxymiron "Песенка Гремлина")

Как по мне, явная отсылка