Vovuh's blog

By Vovuh, history, 2 weeks ago, In English,

<copy-pasted-part>

Hello! Codeforces Round #544 (Div. 3) will start at Mar/07/2019 18:05 (Moscow time). You will be offered 6 or 7 problems (or 8) with expected difficulties to compose an interesting competition for participants with ratings up to 1600. Probably, participants from the first division will not be at all interested by this problems. And for 1600-1899 the problems will be too easy. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 6 or 7 (or 8) problems and 2 hours to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

  • take part in at least two rated rounds (and solve at least one problem in each of them),
  • do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Mikhail PikMike Piklyaev, Maksim Ne0n25 Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round.

Good luck!

I also would like to say that participants who will submit wrong solutions on purpose and hack them afterwards (example) will not be shown in the hacking leaders table.

</copy-pasted-part>

UPD0: I also would like to thank Stresshoover, dreamoon_love_AA, Nebuchadnezzar and nhho for help in testing the round!

UPD1: Editorial is published!

UPD2:

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 MoNsTeR_CuBe 7 340
2 try_agian 7 370
3 HurmousDay 7 396
4 AyaOtonashi 7 404
5 N_o_o_B 7 437

Congratulations to the best hackers:

Rank Competitor Hack Count
1 greencis 72:-31
2 jhonber 30:-1
3 Milkdrop 22:-15
4 awasd 16:-3
5 MarcosK 12:-5
269 successful hacks and 316 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A friendly_potato 0:02
B OFAKMKOFZ 0:04
C MbahFaishol1937 0:03
D AyaOtonashi 0:08
E nvwa 0:22
F1 elevendigit 0:15
F2 XXMihaiXX969 0:21

 
 
 
 
  • Vote: I like it  
  • +147
  • Vote: I do not like it  

»
2 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Div 3! Must be the time for high rating!

»
2 weeks ago, # |
  Vote: I like it -41 Vote: I do not like it

Please make Div 3 rounds as frequent as Div 2. It is really good from the competition point of view. Otherwise Div 2 rounds include upto 2100 rated competitors on the ranklist which push coders like me to the bottom of the ranklist. Its really hard to even get to the top 1000

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    Div. 3 rounds are rather educational than competitive, and CodeForces team with no doubt does an amazing job in terms of number of educational contests (both Div. 3 and Edu. contests).

    Also, I believe that if you want to be in top N, then much better idea would be to study more and get into overall top N than to chose last N and find yourself in the top N (out of those last N).

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      I agree with you but all I am saying is competition should be among equal ones. You seem to say there shouldn't be even div1 and div2.

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it +7 Vote: I do not like it

        It doesnt matter at all . If ur wishes r granted then u may rank top but ur rating wont go that higher . But if u compete with stronger ones then ur will rise much higher for the same position .

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    I think rating doesn't matter at all. Be a better version of yourself that's all matters.

»
2 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

I am really excited about my first unofficial contest.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Good to know I am not the only one feeling good about doing contests unofficially :P

»
2 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

6 | 7 | 8 = 8 . only 6 r enough

»
2 weeks ago, # |
  Vote: I like it -11 Vote: I do not like it

hack nasil olabilirim

»
2 weeks ago, # |
  Vote: I like it +23 Vote: I do not like it

This round will be much easier than the previous one :) At least, I hope so...

»
2 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

I hope there will not be any misbehaviour from the community side this time. :D

»
2 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Is there any possibility to make contest duration 2:15 or 2:30 ?Vovuh BledDest MikeMirzayanov

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I already had a rank of 1900, so the round is not ranked for me?

  • »
    »
    2 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    it's ranked for u.

    Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

»
2 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Standings are showing that this its rated for me..I've become expert in previous education round... Figure it out please..

  • »
    »
    2 weeks ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    I can see one of my "Specialist" friends is considered as non-official participants in this round(He was 1600+ before previous round). I think both situations are from same reason.

»
2 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

I liked problem D, it's very creative.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What is testcase # 37 in D?,..T_T..

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    To solve the case37, I change my double into long double.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      OMG... i got AC to change long double .. T^T

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I got a better idea ,let two numbers mutually prime. And if the max value is 10e10,it does not work.Luckily,in 10e9,it goes well you can test these two cases

        2 999999999 999999999 999999999 999999999 2 9999999999 9999999999 9999999999 9999999998

»
2 weeks ago, # |
  Vote: I like it +26 Vote: I do not like it

Hi. I forgot to adjust registration types (official-unofficial) after the educational round rating update. Sorry, I'll fix. Is it good idea to exclude from rating those, who should be official but was indicated unofficial incorrectly? They can be sure that they are unrated and solve problems carelessly.

P.s. I'll fix from Oman. I'm in a trip now.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Hats off! Sir. It's great to see that someone still working when he is on a trip!

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Imho that excluding such participants isn't a good idea.

»
2 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Why is the following output incorrect for problem F1 example 3?

1 2

1 6

2 3

2 5

2 7

3 4

5 6

  • »
    »
    2 weeks ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    Where is [5 8] Edge ? Your answer is NOT spanning Tree. Because your tree doesn't include vertex 8.

»
2 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

What is pretest 5 in D ?

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    i think it is ai = 0 and bi = 0

  • »
    »
    2 weeks ago, # ^ |
    Rev. 4   Vote: I like it +8 Vote: I do not like it

    maybe handle case like

    3

    0 0 5

    0 0 5

    answer here is 3

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      daaaaamn how I didn't see that we can multiply 0 with anything

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      how the equation is a * d + b then when b == 5 if i choose d == 0 then c = 5 not 0 i-->1 -- > 0 * 0 + 0 == 0 i-->1 -- > 0 * 0 + 0 == 0 i-->1 -- > 0 * 0 + 5 == 5

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      sorry i see that if d == -1 then the answer is 3 sorry about confusion

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What can be the test-case 35 of problem F2

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i think it's something like

    5 6 2

    1 2

    1 3

    1 4

    1 5

    4 5

    2 3

    cheak this

»
2 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

My solution of D passed in C++17 but gave wrong answer in C++14. Can anyone explain why? submitted in C++14 : https://codeforces.com/contest/1133/submission/50944202 submitted in C++17 : https://codeforces.com/contest/1133/submission/50953520

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    it is problem with double, it outputs large numbers like 1.32e+10

  • »
    »
    2 weeks ago, # ^ |
    Rev. 3   Vote: I like it -8 Vote: I do not like it

    I'm facing something like that in problem D 1133D - Zero Quantity Maximization. Could you please help me?

    TLE in test case 42 C++ 17 51011108

    TLE in test case 45 C++ 11 51012754

    TLE in test case 23 Clang++17 Diagnostics 51012897

    TLE in test case 45 C++ 14 51013012

    • »
      »
      »
      7 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Your solutions got a few issues:

      1. Never use double/long double/etc. if you're to maintain the exact value of a rational number. Consider storing it in other alternative, like a fully-reduced fraction (to avoid ambiguity, the denominator of the fraction should be positive).
      2. unordered_map in C++ is a poor idea. This is a hash-table-based data structures, with average $$$\mathcal{O}(1)$$$ complexity for accessing/modifying, however the complexity can rise up to $$$\mathcal{O}(n)$$$ when collision occurs. In this case, the default C++ implementation of the hash function is incredibly weak that there are many testcases have been made to specifically counter it. Either use a map (a bit slower with the logarithmic complexity, but much more stable), or implement your own truly random hash functions for your unordered_map.

      P/s: A few reference for you, if you insist on re-implementing the hash functions. Pretty helpful.
      "Blowing up unordered_map, and how to stop getting hacked on it" by neal.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Test Case 5 in D? Kept getting WA. I kinda knew my solution wouldn't work. But there was a probability it would. CODE

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F2 ? My approach — run dfs to find all articulation edges in the graph with one of the ends as vertex 1. Let this be art(1). If degree(1) < d , then straightaway answer is NO. If art(1)> d, then again answer is NO. Otherwise, include all neighbouring vertices of 1 connected via articulation edges and remaining d-art(1) vertices from left out neighbours and simply run bfs. However, this seems to give WA on test 16.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't know what "articulation" means, but at least there are 2 groups connected to vertex #1(One is consisted of vertex 5 only, otherwise included all vertices except #1, #5).

    So the minimum degree required for vertex #1 is 2, so the answer is NO.

  • »
    »
    2 weeks ago, # ^ |
    Rev. 2   Vote: I like it +7 Vote: I do not like it

    It is indeed wrong my friend.

    The simplest counter-test

    There are no articulation edges, but two components connected to vertex 1.

    The soltion doesn't include finding articulation points. You should remove vertex 1, find connected components. Afterwards make sure to reconnect vertex 1 to found components.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Please Makes me official. <3

My rating is below 1600.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What is test case 58 of E? :/

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Task D:

Attempt 1: eps = 1e-4; WA

Attempt 2: eps = 1e-7; WA

Attempt 3: eps = 1e-9; WA

Attempt 4: eps = 1e-18; WA

Attempt 5: eps = 1e-18; WA

Attempt 6: eps = 1e-25; WA

Attempt 7: eps = 1e-300 AC

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    you can use GCD and map rather than division so you don't need to use eps

    • »
      »
      »
      2 weeks ago, # ^ |
      Rev. 2   Vote: I like it +3 Vote: I do not like it

      Yeah, I mentioned this but I thought that two fractions a/b and c/d with difference less than eps would also be one d.

      Lol I was thinking that way when i wrote eps = 1e-300

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      I'm facing something like that in problem D 1133D - Zero Quantity Maximization. Could you please help me?

      TLE in test case 42 C++ 17 51011108

      TLE in test case 45 C++ 11 51012754

      TLE in test case 23 Clang++17 Diagnostics 51012897

      TLE in test case 45 C++ 14 51013012

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        just use map rather than unordered_map , AC

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it -8 Vote: I do not like it

          Surprised!

          But why did it make the change? Can you please explain? However thank you!

          • »
            »
            »
            »
            »
            »
            13 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Because unordered map insert and delete operation may work in O(N) time in some situations because of collision, meanwhile map works O(logN) time.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Excellent

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Attempt 1: long double -> AC

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can we really use map with double index ?

I thought that this is why I'm getting WA so I tried using Gcd

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can use map with any index you like

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I know but if it's a result of fraction it may give wrong results

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Use a map with a pair as index, the pair being Ai and Bi reduced to their lowest ratio. So no need to use any fraction whatsoever.

  • »
    »
    2 weeks ago, # ^ |
    Rev. 2   Vote: I like it +2 Vote: I do not like it

    I passed D with long double but I'm not sure if this solution will survive after hack wave.

»
2 weeks ago, # |
  Vote: I like it +27 Vote: I do not like it

F2 was perfect

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    what's the test case 37 in F2 ?

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      No ideas

    • »
      »
      »
      2 weeks ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      I got WA on tc 37. When I selected edges starting for 1 randomly.
      Simple counter tc for this was -
      4 4 2
      1 2
      1 3
      2 3
      1 4
      You should select 1,4 and 1,2 or 3.
      You will get WA if you select 1,2 and 1,3.

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        I'm getting correct answer this case , my output is (1,4) (1,2) (2,3) .

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Bonus: Can F2 be solved if the problem asked if any vertex can have degree D instead of specifying the first vertex

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I have a trivial doubt.... What do u mean by first vertex ?

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Indeed this was confusing! They meant the vertex with label '1', but I thought one has to find a possible vertex to be taken as "first vertex" = root of the spanning tree... :-( !

    • »
      »
      »
      2 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Ignore

    • »
      »
      »
      2 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Is this a correct approach for the bonus question posted above?

      First, check the number of connected components for a vertex with degree greater than or equal to D using articulation points DFS. If that value comes out to be less than or equal to D then use this vertex as the start point. If no such point exists then the answer is NO.

      Code = https://pastebin.com/deATp7x6

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Not perfect: They said "first vertex" instead of "vertex with label '1'". My code was searching a possible starting vertex and print the spanning tree starting with that vertex as first vertex = root of the spanning tree. This was quite a bit more complicated :-( ! and it gave wrong answer, already for simple cases like "3 2 1: 1 2 ; 3 1". Here, if you take '2' as first vertex = root of the tree, then you have a spanning tree with the expected property. Their examples were compatible with this interpretation: In the only example with "NO", it was indeed impossible to find any vertex which could have been the starting vertex = root of a spanning tree with the required property.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Microsoft Visual Studio 2010 hasn't the "long double",I can't accept the problem D!!!!! My attitude booms !! And I feel very unfair!

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    Actually, it is possible to solve D without using double, long double or any floating point number.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      yes of course! it should be done with fractions...

»
2 weeks ago, # |
  Vote: I like it +20 Vote: I do not like it

It was one of the coolest Div.3 rounds i've seen! Thanks a lot to creators!

»
2 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve E?

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    For every index , find the the max element which can be inserted in current set, now we have n different ranges (n , different teams ) out of them we need to select k teams such that students count is maximized (remember that a student can be in at most 1 team ) ! This can be done by dp , selecting the current range or not selecting (kind of knapsack problem ) !!!!

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Q-D my answer works similar to other c++ users but I am getting TLE i am even using pypy, any optimization suggest, please!

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C: int arr[]=new int[size]; // getting Time limit exceeded vs Integer arr[]=new Integer[size]; // working perfect

why??

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's because Arrays.sort() for int[] uses Double pivot Quick Sort internally and a test case must've had an anti-quick sort input (giving O(N^2) it a worst-case) causing it to exceed the TL. Whereas, Arrays.sort() for Integer[], uses Merge Sort which gives O(NlogN) in worst-case.

»
2 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

I loved problem D, it was extremely innovative.

»
2 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

surely the best div3 round ever!!

»
2 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

Again failed to cross 1200. "APNA TIME AAEGA"( My time will come).

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Yes, keep solving problems: It may take years but we'll get there!

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve f2?? i am getting wrong answer on test case 35,here is my submission https://codeforces.com/contest/1133/submission/50987588

»
2 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Why grid approach doesn't work for E ?

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone elaborate on dp approach E, what does i and j means in dp[i][j]?

  • »
    »
    2 weeks ago, # ^ |
    Rev. 3   Vote: I like it +1 Vote: I do not like it

    Depends on your interpretation, on mine DP[i][j] is the solution for the problem on the interval with indices [i,N) given j groups available

    So, given a state (i,j), the best solution is made by either using the group that starts with the i-th element, or not using it.

    This is DP[i][j] = max(DP[i+1][j], DP[next[i]][j-1] + next[i]-i)

    Where, if the group that starts at i is [i,k) then next[i] = k.

»
2 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

For problem E : Many solutions have failed on TC:58 if they have used greedy approach i.e.,for each k, calculating maximum length of range for which given condition is true( using binary search ) and then adding them.

code which failed on TC 58 : https://codeforces.com/contest/1133/submission/50976279

This approach is wrong because it is possible to obtain even higher number.For this we need to apply concept of DP.

for eg: consider TC : n=8, k=2, array a={ 3,5,5,5,5,9,9,13 }

By using greedy approach, we get maximum length for k=1 as 6 for {5,5,5,5,6,6} and then for k=2 (i,e., after removing elements from i=2 to i=7) we get maximum length as 1 (for 3 or 13).

so total number of students using greedy approach = 6+1=7.

But this is not most optimal as the best way is

for (k=1) take range as {3,5,5,5,5} = 5 for (k=2) take range as {9,9,13} =3 so total number of students using optimal approach = 5+3=8.

So DP approach (correct approach) :

Tabulate a dp[i][j], ( we will use bottom up approach i.e., first kth team filled then (k-1)th and so on...)

where dp[i][j] --> maximum total number of students included till now (i.e.,from team 'k' till team 'j') such that jth team is filled with val[i] and (j+1)th team is already filled with optimal value(computed in bottom up approach ).

dp[i][j] can be obtained by using the forumula

dp[i][j]= val[i] + max( dp[ i+ val[i] ][j+1], dp[ i+val[i]+1 ][j+1],......,dp[n][j+1] );

where , val[i] denotes length of longest range for which condition is true from ith index. i.e., for array a={3,5,5,5,5,9,9,13} val[]={5,6,5,4,3,3,2,1}

val[] can be precomputed using binary search in O(NlogN).

ans= max ( dp[i][1] ) for i=1 to n.

Time complexity : O(n*k + nlogn) for bottom up tabulation and precomputation of val[].

ACCEPTED Code : https://codeforces.com/contest/1133/submission/50989079

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I just noticed a test in A contradicts what was said in the description

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    the 23:59 00:01 one because the description said the competition happenned on the very same day

    • »
      »
      »
      2 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      It does happen on the same day, it starts at 00:01 and ends at 23:59. Its total duration is 23:58, and half of it is 11:59. Therefore, the middle of the contest happens at 00:01 + 11:59 = 12:00. It would be incorrect if it was 23:59 and 00:01, but it is 00:01 and 23:59 (notice that the order does matter in this case).

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I assume you are talking about the 5th test case for problem number one. It is : 00:01 23:59 and not 23:59 00:01.

      It is clearly mentioned in the question that the first time denotes the start and the 2nd the end time of the contest, considering this the input it valid.

»
2 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

For problem F1, I've used Kruskal's algorithm but picking all edges coming out of the maximum degree vertex first and then add other edges which satisfy the spanning tree property.

This resulted in a TLE. Time complexity for the code I have written (in PyPy 3.5) is O(m+n). How can this be improved?

  • »
    »
    2 weeks ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    F1, doesnt require Kruskal or Prim's algorithm. Just a simple dfs is enough. Find the vertex with the maximum degree, S. connect it to all it's neighbouring vertices and marked them visited except one vertex.

    Just do the dfs from S. Link

  • »
    »
    2 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Python or PyPy is poor to use in this platform. Many competitive programming platforms never respect slower languages such as Python, etc. So use C++ instead.

»
2 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

See to the rankings where trusted participants include people above 1600 ratings

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Previous contest rating update haven't included in current standing yet. It'll be fixed soon.

»
2 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

When will the system testing start? Can it finished before the next compitetion

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello everyone, I am quite new to Codeforces, I tried to submit solution to problem C, after seeing top submissions but I am getting TLE from the same logic in JAVA. Can anyone help me.

My code: http://codeforces.com/contest/1133/submission/50999444

The code I referred: http://codeforces.com/contest/1133/submission/50935270

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Use Integer instead of using int when declaring an array because Arrays.sort() for int[] uses Double pivot Quick Sort while Integer using Merge sort.

»
2 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

i have waited system testing for 2 hour :(

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone tell me what is wrong in my code it is giving wrong answer for test case 4. i have just iterate it over all the edges Your text to link here...

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please tell why I am getting TLE in My solution. https://codeforces.com/contest/1133/submission/50969866 The time limit given in this question was 2 sec.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think it works O((n - 1) *(n + 1) / 2) time, which is bigger than 10 ^ 10.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I want help in question D(Zero Quantity Maximization) can somebody give me a hint for the problem

  • »
    »
    2 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    its easy to say if ai*d + bi =0 ==> d=-bi/ai we make a map for d then take the d who solve to many equation so we take the biggest frequency of d in the map you can save d as pair<int,int> or long double

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

what wrong in my code of B 50962881 it failed on test case 22

  • »
    »
    2 weeks ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    this is your bug in test case 22 if(k==1)return cout << n << endl,0; you can fix it by make n even if(k==1)return cout << (n — n %2) << endl,0;

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me understand why my code is giving RUNTIME ERROR on test case 18 in problem F1? http://codeforces.com/contest/1133/submission/50972145

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

editorial plz

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E?

My solution: Find the team with the maximum number of students and then remove those students from the vector. Repeat until all students are in some team. Then pick the largest k teams. But it gives WA on test #52

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i think you need to implementation DP approach rather than greedy one

  • »
    »
    13 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I think the problem with your approach is when you have many possibilities for the range with maximum size in a given step. For example, consider the following testcase:

    5 2
    1 6 7 8 12
    

    Here you have two choices for the first team: (6,7,8) and (7,8,12). If you pick (6,7,8) as first team you would have to pick (1) or (12) as second team and would get an answer 4. But if you pick (7,8,12) as first team you could pick (1,6) as second team and get an answer 5. I think that if you could know what is the best maximum range at each step (when you have many choices) than the greedy could work. But how to know that without seeing further configurations?

    Update: Actually, I think the problem I mentioned before is not the only problem when we allow repeated numbers. In this case greedy solution will fail for some instances. See this comment for better explanation.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can F2 be solved by finding articulation edges / bridges in the graph and as soon as we find bridge edge we merge them and after that we pick any random adjacent edges of vertex 1 so as to make its degree exactly d. and after make the whole tree connected using kruskal type algorithm? Here is my submission for reference of what i am talking. Pls tell if i am wrong. Thanks