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

Автор keima915, история, 3 недели назад, По-английски,

Good day, Codeforces! Or in my language, magandang araw, Codeforces!

Codeforces Round #597 (Div. 2) will be held on Nov/01/2019 17:35 (Moscow time). Is it rated? Yes, but only for participants below 2100 rating.

Of course, this round is not made by me alone. So, I would like to thank the following people for their help in making this round possible:

There will be 6 problems, and you will be given 2 hours to solve them.

The scoring distribution is as follows: 750-750-1250-1750-2250-2500.

I hope you enjoy the round!

Update: editorial is out now

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

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

best round i ever tested. keima orz

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

Best of luck for your first contest.

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

Are you the first one from Philippines to make a contest on codeforces ?

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

I hope I can become candidate master after this round :DDDDDDDDD

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

After almost 3 years I am back on CodeForces and gonna participate in this round. Wish me luck!

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

It clashes with a codechef round , but after reading comments from testers ,it seems like, i should ditch that and participate here ...

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

I think it must be one of the best contests in Codeforces!

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

I wish contest has strong pretests. I don't like to take wrong answers on main tests.

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

    Whenever 300iq was taster , 193 tastcase passed and then suddenly wrong answer in tastcase 194

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

As a tester, I enjoyed solving problems. Well written problem statements mixed with Chinese culture. One of the problems is about a childhood game and it was completely interesting for me!

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

Keima915 OP, from green to orange in 7 months .. interested about the contest to start my 7 months journey :p

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

hope solve a,b,c

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

Please can anyone say me this round I wanna be specialist how many problems must I solve

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

Expect for the constest!

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

I wish I can get expert in the contest again. :)

Good luck to everyone!

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

I m back Bois.. Had a busy October but now I am back to top the charts again.

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

The contestants had to face some difficulty in the previous contest due to several server failure. Though it was overcome in few seconds but its disappointing to reload the page over and over again during the contest hour. Div-2 rating changes also had to roll back because of some problems and we had to wait for several hours to get the rating changes in the last contest. Hope the authority will take care of these matters in this round.

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

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

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

Best of luck in your first contest!

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

Why first and second question has same score distribution....does that mean they have same difficulty level??

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

how can be a tester?

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

Hope we have a fair race :)

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

I hope that I can turn it into a blue name.

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

Another DISGUSTING reading contest.

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

    Reading is also a part of CP. So you should adjust yourself to read long questions. Else make the question look smaller to you. How? You figure it out ;).

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

      I don't like to read tonns of text after hard work day. It tires the brain completely.

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

        Do you think everyone is only doing CP? Are they not tired?. Let's not make any excuses and just read the question there is no other way.

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

          I don't care about others. Comments were invented in order for people to explain PERSONAL opinion.

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

    Well, I guess that's just your excuse for not being able to solve problems on this contest. The statements were actually well written and short. Go practice instead of complaining.

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

      Well, I don't know if the statements were well-written but problem E's statement is definitely not short.

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

        You're right, they were well written except for E. When I saw that statement I didn't even try to read it and went for problem F.

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

      I didn't even tried. Maybe you're right, I don't able to solve problems, but also i do not want to read giant problem statements.

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

strong pre test cases for problems at code forces I ever seen!!

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

Wrong answer on pretest 13 on problem D, No idea why. :(

Any one have idea what is going on in pretest 13 ?

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

TC 9 of problem C?

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

    Were u taking modulo when calculating the fibonacci ????

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

    That test case got me too. I spent the last hour trying to fix whatever was wrong my fibonacci-number calculator.

    I was modding by 10^9+7 everywhere I could see, but for some reason, my 89-th and onward Fib numbers were wrong. So of course the Fib products were also wrong too. Please send help

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

    If you need help tell the approach of your solution rather than asking what was the test case. After some time you will get to know it right? :)

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

      I found out that ways to arrange characters of length i which are consecutive, can be found out by this formula,

      Pseudocode

      if(i is even) dp[i] = dp[i-1]*2 +1;
      else dp[i] = dp[i-1]*2 - 1;
      

      In my solution, i was doing like this:

       dp[0] = dp[1] = 0LL;
       dp[2] = 2LL;
       dp[3] = 3LL;
      for(int i=4;i<=sz(s);i++){
              dp[i] = (dp[i-1]*2LL)%MOD;
              if(i%2) dp[i] = (dp[i]+1LL)%MOD;
              else dp[i] = (dp[i]-1LL + MOD)%MOD;
              //cout<<i<<" "<<dp[i]<<"\n";
          }
      

      Is the problem with Modulo that i am doing? Please someone help.

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

        First of all, your first "if" statement has identical branches.(now ok)

        Secondly, dp[1] should be 1

        Thirdly, by the formula you have given dp[4] = dp[3] * 2 + 1 = 7, but actually dp[4] = 5. For example :

        intput:

        uuuu

        1.uuuu 2.wuu 3.uwu 4.uuw 5.ww

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

          Here is my output of first 10 numbers. Check once again, i think you are misreading something.

          4 5
          5 11
          6 21
          7 43
          8 85
          9 171
          10 341
          
          • »
            »
            »
            »
            »
            »
            2 недели назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            dp[5] = 8 not 11

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

              Then how I was able to pass 8 test cases? lol

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

                till 8 TC,

                the continuous occurrence of n and u is not greater than 4.

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

              Thanks anyways, I was calculating repeating cases again and again.

              1.uuuuu  2.wuuu 3. wwu 4.wuw
                       5.uwuu 6.uww
                       7.uuwu 8.wwu
                       9.uuuw 10.wuw 11.uww
              

              where 8,10 and 11 are repeating. Wasted 1 hour thinking about something wrong with computations.

              Thank you :)

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

            I calculated according to your first two lines of your comment (the if else part), you said dp[i] = dp[i-1] * 2 + 1 if i is even, maybe you have mistaken even with odd there, anyway, your formula is incorrect I guess.

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

how to solve D?

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

    Kruskal or Prim to find smallest tree. However the graph must be modified a little bit. Add a new node (let's say it's the power supply for the power stations) and the edge from this source to each of n nodes is equal to the cost to build a station there.

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

      Dont we need to make sure that there is atleast one power station? Wouldnt your approach fail when the power stations cost are really high, but the points are close by?

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

        However, your minimum spanning tree will also need to include the new node, which represents a sort of "super power supply" and ensures that at least one node is connected to the new node, and thus has a power station.

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

        Hmm? a tree is a connected graph, thus the newly added node (power supply) must belong to tree too. If the power supply is connected to node i, then you put a station at node i. Since the supply is always connected to some city because of connectedness, there is always at least one power station.

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

        No because we are finding a spanning tree which is connected if the original graph is connected too thus there'll be a path from the power station to every city.

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

What the hell was pretest 13 in D :(((

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

    Did you consider the case when $$$(x_i, y_i) = (x_j, y_j)$$$ even if $$$i!= j$$$. I think this is the mistake, I am not sure though, because I too got wrong answer on test case $$$13$$$. I didn't consider this case, so maybe this is the mistake I made.

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

      IS it matters? Because dijkstra will take care of this fact I guess. CAn you please give the example by which you debug your code?

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

      I considered this case. I was not finding MST though, which I think was the expected soln

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

approach for problem C?

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

    I was getting some kind of fibonacci sequence

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

    say we have len length of string of either n or u, in how many ways we can make pair in the string

    so if we make x pairs of 'n' ,we are left with len-2*x 'n' characters and we have x+1 blocks where we can fill them , so distribute len-2*x objects among x+1 persons such that each get zero or more with (len-x,x) ways

    and iterate x from 0 to len/2

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

    Any chain of U's can be broken up in fib(length) ways:

    Proof: if there are n of them: UU...U we can condition on whether to turn the first U into a W, or not: If we do, then it becomes W(U...U) (with n-2 U's) If we don't, then it becomes U(U...U) (with n-1 U's)

    Now each k-chain of U's or N's in the string has Fib(k) possible strings, so we multiply Fib(k) over all the k's

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

      Nice

      But how did you calculate the Fibonacci sequence?

      I was doing mod 1e9+7 during the calculation and I'm getting wrong answer on pretest 6

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

      Any chain of U's can be broken up in fib(length) ways

      How did you come up with this intuition?

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

        For my case...I understood this by observation, I calculated the results for the first few lengths of chain and then realized the pattern :3

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

        Consider u as 1 and w as 2 , then how many possible combinations exist such that sum is n.

        Let n = 4

        uuuu = 1 + 1 + 1 + 1

        wuu = 2 + 1 + 1

        uwu = 1 + 2 + 1

        uuw = 1 + 1 + 2

        ww = 2 + 2

        There exists 5 ways which is nothing but fib[4].

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

        I saw it in a book (Proofs That Really Count) in the first chapter. It explained that fibonacci numbers can be thought of as the number of ways to tile a 1xn grid using (unlimited) dominoes of size 1x2 and 1x1. There you condition on whether you place a rectangle or square domino in the leftmost place.

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

what is test case 13 in D

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

I thought this was an amazing round :D What lovely well framed questions

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

Does problem D using Prime Algorithm? I did it but got WA on test case 4. What is TC 4 :(

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

    I think you mean the Prim Algorithm. As far as I know, yes.

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

      Yes, Prim Algorithm. Sadly, i still didn't solve it. After solving A, B, C for around 50 minutes. I came to problem D, the statement is so long and demotivate me a lot. After relaxing 10 mins, I decided to read the statement because I had 1 hour remaining time and the problem didn't hard as much as I think. If I started to solve it sooner, I would have more chances to debug. It's experiment for me. Very nice contest =)))

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

        Yeah, I understand. I was puzzled too when I saw the super long statement. Just calm down and don't be afraid of those things. I believe you can do much better in the future. Good luck!

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

          Slightly off-topic, but I love comments like this for the example they set for the CF/CP community. :')

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

    I solved D with Prim's algo.

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

      Dijkstra?I did using Dijkstra....But I guess the algorithm is similar XD

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

        It's almost the same algorithm.

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

          -is-this-fft- Is this prim?

          Code

          Edit: I need to re-order these two statements for AC. lol

          ans += tp.first;
          if(mark[tp.second.first]) continue;
          
  • »
    »
    2 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Kruskal is fair enough

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

    Check out if you have used "long long int" instead of "int". I also got WA at test case 4, and this helped me :)

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

      I used long long instead of int, but It didn't solve. Btw, what is the difference between long long and long long int? are they same?

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

        Yes, they are identical.

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

        My situation is exactly the same as yours.Long long didn't save me.(•́ω•̀ ٥)

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

        Hey bro~I find a lil issue in my code,I defined a variable as int but it should be long long.Thus the program got overflow.Maybe you should check the type of each variable carefully.

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

What is pretest 13 of D? Wasted almost half hour :(

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

UwU

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

dpforces

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

How to solve F?

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

    Dp with digits (in this case is binary digits).

    You have a+b = a xor b + a&b. Then a + b = a xor b if and only if a&b = 0.

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

    I pre-solved it with digit dp. Let $$$f(pos, smaller_1, larger_1, smaller_2, larger_2)$$$ be the number of way to fill the first $$$pos$$$ binary bits such that [ the first number's prefix is already smaller than $$$r$$$ ], [ the first number's prefix is already larger than $$$l$$$ ], [ the second...], [ the second...] and their prefixes have no set bits in the same position so far. The transition is not hard to come up with. The answer is the sum of all entries in $$$f(0)$$$.

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

      I am trying to understand your solution and transition. Could you please explain the transitions and the continue statements? I think this is a much generic approach. Thanks

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

I finally realized that it was problem E until I submitted my code(since mirror sites don't show the indices of problems
I fooled myself XDDDDDD

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

Nice round. F is a fairly common problem btw. But it is still nice :)

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

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

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

Nice Contest and problems.

But A was quite similar to this problem.

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

Find out why this gets WA8 (takes less than 5 seconds), i couldn't during the whole contest :DDDDDDDD

Solution

Question #2: which lines cause the trouble?

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

Ques.D) Shichikuji and Power Grid: In this question which concept and data structure are used. I think so Kruskal for the shortest path and DP for choosing the powerhouse or connection.

Suggest or provide some explanation, I am a beginner for this type of question.
  • »
    »
    2 недели назад, # ^ |
    Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

    I used priority queue to solve.

    1. First, push the cost of setting plants at each city into priority queue along with city number.

    2. Then, start where cost of setting plant is smallest.

    3. Then push the cost making a connection from this city to every unelectrified city (along with city details) and push them into priority queue. Extract minimum cost (setting plant or making a connection) and go to step 3 (n-1 times).

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

    My solution: Using Kruskal:

    Create all the possible edges and their weights(using formula in the statement). Sort the edges according to their weights.

    Suppose you are trying to connect the connected component U and the connected component V using the edges (x, y). Basically you have 2 options:

    • Build a power station in a city in U and a power station in a city in V (Just pick the city with less cost). You don't have to build the edge (x, y) anymore.

    • If you decide to build the edge (x, y) to connect U and V, then you have to build a power station in a city in the union of U and V. Just pick the smallest one.

    Just pick the optimal options for each edge (x, y) and add up the cost.

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

In A I guessed from test cases that a and b needs to be coprime, and the submission worked, But I don't get why is this correct answer. For example a = 3, b = 7 there are infinitely many numbers which are coprime to 3 as well as 7, then aren't there infinite black numbers?

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

    A number $$$X$$$ will have color white iff $$$X$$$ can be written as a combination of $$$(a,b)$$$

    ==> There exists $$$k_1,k_2>=0$$$ such that $$$X=k_1*a+k_2*b$$$.

    So the numbers $$$X$$$ having color black will be the ones such that that equation has no solutions. Since that's the Diophantine Equation(to which there's either an infinite number of solutions, or there are none), having no solutions means $$$X$$$ is not a multiple of $$$gcd(a,b)$$$.

    So if $$$gcd(a,b)=1$$$ then there's no such X.

    Else there will be many; infinitely many.

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

D can be solved using a trick: create a virtual vertex, let's denote it as n + 1, then for every vertex connect it to (n + 1)th vertex with an edge having a weight equal to the vextex's c value. Then the problem becomes finding the MST of a given graph.

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

The competition was awesome !!

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

Maybe I'm the only one who solve B using dp and C using 2-dimension dp (I didn't think of Fibonacci or any stuffs related to it)

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

In problem C, I was using square free Fibonacci series. But, I got WA on pretest 9. Can someone help me?? My solution

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

Anyone notices that there seems to be no one (at least very very few people) that fails system test. Amazing contest!

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

Damn, these 4 ms help me become a candidate master!

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

I converted the problem C into "how many ways you can get a sum s using coins {1,2}"..then somehow didn't able to implement it in time...Its kind of sad

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

    That is a very nice solution.

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

      but I later figured it out that it will not work since,in counting number of ways a sum can be generated from fixed number of coins, order doesn't matters,but in our case order of selection will matter...eg. sum=3 can be generated from coin-sets {1,2} in two different ways {1,1,1} ans {1,2}(note that {1,2} and {2,1} are same) but the answer should be 3.It will convert to staircase problem counting number of ways to reach stair n if you can climb 1 or 2 stair at a time....correct me if I am wrong

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

Can someone help me with solution of D.. Here's my submission 64039124
My idea was to check if a node can be connected with any other node such that the cost for wiring is minimum and less than or equal to the cost to build a power station on that node. If such a node is available then construct an edge between them. Otherwise build a power station on that node.
Lastly, if a component has no such node which has power station in it , then build a power station that requires minimum cost in one of the node of the component..

It is generating way too much minimum cost for test case 13. I couldnt find why

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

A very balanced contest with strong cases , thank you :)

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

I am not able to see home,contest,gym option in my account? What happened..My homepage is not working

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

Great round! Thank you)

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

Is there any proof for the solution of 'C',I understand its solution but why this way only? Please anyone!

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

I had following idea to D. Lets make minimum spanning tree of graph with edges $$$c(i, j) = (k_i+k_j) * d(i, j)$$$ for all $$$i , j$$$. Firstly lets add the cheapest plant. Then sort edges in non-increasing order and we will try to delete every edge. If we are considering edge $$$(x,y)$$$ let $$$c_1$$$ will be component with vert $$$x$$$ of tree without edge $$$(x, y)$$$ and $$$c_2$$$ will be component with vert $$$y$$$ of tree without edge $$$(x, y)$$$. Only one of this components has installed plant now. Let it be $$$c_2$$$ . Then find cost of the cheapest plant in $$$c_2$$$ and check if its better to add plant instead of edge from spanning tree. If its better to add plant, we delete edge $$$(x, y)$$$ and add plant.

But, my solution got WA13. I will be grateful if you point out my mistake.

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

    Not entirely sure but could be that you are not using the "cost" of power plant while sorting, you are only using wiring cost while sorting? Both types of costs need to be consider.

    edges.pb(tii((k[i] + k[j]) * dist(i, j, coord), i, j));
    
    SORT(edges);
    
    
»
2 недели назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

Thanks keima915 !

That was a good contest !

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

However, she died when she was only in fifth grade so she is not smart enough for this.

Wait, what codeforces?

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

Has anyone solved D using dynamic programming?

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

Another solution for D is the O(n^2) version of Prim's algorithm which works better on a dense graph. It doesn't need extra dummy nodes either. Is it the most efficient solution?

I solved D in this way after the round, but my implementation was slower than I expected.

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

Can anyone help me with problem D. I sumbited the same code twice, and in the constest y got TLE, but after resumbitting i got AC. https://codeforces.com/contest/1245/submission/64045463 https://codeforces.com/contest/1245/submission/64035229

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

    Your AC code was just 4 ms away from TLE. It just got lucky. The execution time of the same code can differ by a few ms in different submissions. That is the reason behind TLE. Your code was not just lucky enough to get AC in contest time!

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

D is very much similar to this problem : https://vjudge.net/problem/LightOJ-1059

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

Although the contest was very well written and prepared, but still after seeing the next contest, I am like — "Finally, a div. 3 round...., Yay!"

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

Hello my solution to problem D is either bugged or incorrect. With bugs I can cope but I worry it might be simply incorrect. It fails to pass test 13 (wrong answer).

My idea:

Firstly, take each city and make network out of it, making total n networks. Assume that every network doesn't have electricity supplied to it.

while (there exists network that doesnt have electricity supplied) {
  take any network P that doesnt have electricity supplied

  if (its cheaper to build plant inside P, than to connect P to any other network
      (OR) its impossible to connect P to any other network (there are noo other networks)) {
    build plant (cheapest possible amongst members in P) inside P supplying electricity to it
  }
  else {
    build connection between P andd other, closest possible network (closest = cheapest road)
    merging two networks into one
  }
}

I'm not worried about time complexity as above can be implemented in a fairly fast way. Just whether this should work or not.

Thanks for help in advance.

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

    Hello :)

    I didn't read your method, all I could do to help was stresstest, and I found a case where your code(I used the last submission) fails compared to my accepted solution.

    test case
    your answer
    correct answer
»
2 недели назад, # |
  Проголосовать: нравится -19 Проголосовать: не нравится

The worst round I've ever solved...

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

How are you supposed to solve D using Kruskal's Algorithm?

When I sorted the 2,000,000 edges, I got TLE on Test 7. Is this only because I used Java, or is Kruskal too slow in general for this problem?

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

    I've heard that inbuilt sorting function in java is sometimes slow(maybe it is a quick sort variant),i do not know otherwise...

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

      I have a sort method that randomizes the numbers being sorted first, so that it is immune to the Quicksort TLE. I simply believe that the time constraints are a little too tough for Java, at least using Kruskal.

      I used Prim's algorithm to pass the test case in just 202 MS though.

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

great job I love this round too

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

Can someone help me for problem B? I cannot find out where I am wrong? 64097713

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

    The way you find the optimal sequence of moves(your string 'alice') in the case of YES is wrong.

    Try this case to find what you did wrong.

    test case
    correct answer