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

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

Сессия почти закончилась и праздники уже на носу. А это значит, что пришло время еще одного контеста! Поздравляю с наступающим Новым годом всех вас!

<copy-pasted-part>

Привет! В 27.12.2018 17:35 (Московское время) начнётся Codeforces Round 529 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6 или 7 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Наверное, участникам из первого дивизиона они будут совсем не интересны, а для 1600-1899 покажутся простыми. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.

Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Я постарался сделать приличные тесты — так же как и вы буду расстроен, если у многих попадают решения после окончания контеста.

Вам будет предложено 6 или 7 задач и 2 часа на их решение.

Штраф за неверную попытку в этом раунде (и последующих Div. 3 раундах) будет равняться 10 минутам.

Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:

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

Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.

Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацию моей работы. Спасибо моим очень хорошим друзьям Михаилу awoo Пикляеву, Максиму Neon Мещерякову и Ивану BledDest Андросову за помощь в подготовке и тестирование раунда.

Удачи!

Также хочу сказать, что участники, намеренно отправляющие неверные решения и взламывающие их после окончания соревнования (пример), не будут показаны в таблице лидеров по взломам.

</copy-pasted-part>

UPD: После контеста вы можете обсудить задачи в местном Discord сервере. Возможно, я приму участие в обсуждении.

UPD2: Разбор опубликован!

UPD3: Также я забыл поблагодарить своего друга Романа Roms Глазова за помощь мне в тестировании раунда!

UPD4:

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

Rank Competitor Problems Solved Penalty
1 1Piece 6 114
2 blast 6 167
3 roma1n 6 167
4 TripToAzerbaijan 6 170
5 forloop 6 183

Поздравляем лучших взломщиков:

Rank Competitor Hack Count
1 MZuenni 219:-8
2 ______-__________-______ 105:-39
3 _bacali 81:-66
4 too_weak_too_slow 15:-2
5 gamezovladislav 11:-2

Всего было сделано 549 успешных взломов и 540 неудачных взломов!

И, наконец, люди, отправившие первое успешное решение по задачам:

Problem Competitor Penalty
A ChiIIi 0:01
B GreacaEgalLuluOri2 0:02
C ChiIIi 0:05
D ChiIIi 0:12
E NTDnewbie 0:13
F kuchnaahopaayega 0:16

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

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

Didn't we just have a div 3 this week? Instead, why not have an educational? Since the difficulty of these contests is comparable to that of div 3 contests and it would be rated for a larger audience.

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

temikgo сможет стать красным или нет?

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

Awesome Anyway I love Live Contests so much

Great Job for your efforts on Writing and testing the problems

Happy New Year for all

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

Div1+Div2=Div3

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

Just first div 3 contest was the real div 3. (in problem difficulty)

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

If the difficulty trend in Div3 rounds keeps going, we might have to expect IOI level problems.

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

    Hey, it's IOI jury's problem that their task was easy enough to fit into div3 contest!

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

Eden Hazard the best player in the world right now

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

Div 3 is easy for me, give me div 4

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

is it contributed?

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

Good luck!

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

hope this round results in higher rating .Good luck my friends !

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

hope this round results in a higher rating to all my friends ... Good luck to all

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

Why I see the "<copy-pasted-part>" again...Could you pay more attention when writing an announcement?

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

    At least he is spending time for making the contest. Announcement is not important more important is how he settled all the div3 contests so beautifully.

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

    Meh, why would you need a different announcement every time? Announcement notifies you of contest (in case you only look at main page and not the schedule) and reminds you a bit of the rules. This one makes its job pretty fine, I guess. It feels like a waste of time to write it from scratch every time.

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

Good luck to all of you! <3

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

****_ahaahaahaahha bad contest you have brain or no? wtf?_**** ****_Div1+Div2=Div3_**** ****_Eden Hazard the best player in the world right now_**** ****_is it contributed?_**** ****_hello i live in a very rural part of czechoslovakia and i am wondering if the contest is contributed and or rated for me thank you_**** ****_are you ssure? i cant find it x(_**** ****_ahahahahaha one two three 123_****

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

Just first div 3 contest was the real div 3. (in problem difficulty)

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

I hope it is not like the previous contest

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

I will do my best and I want to get gray

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

Good luck folks!

Image

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

Good luck to the server

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

Thanks vovuh for div 3 again. I like the higher frequency for div 3 these days.

Hope it's a great contest.

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

How to hack a solution.

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

Got 2 WA using pow() in C++ :( in problem C.

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

How is there 100% systests already? O_o

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

Please help me with Problem E. Any hints?

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

    Yeah you can use a segment tree for it. The leafs should store the count to open and closed brackets.

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

    If a '(' represents 1 and a ')' represents -1 then the bracket sequence is valid if and only if every prefix sum is non-negative and the total sum is 0. When you change a '(' into a ')' it subtracts 2 from every prefix sum starting from that point. The opposite change has the opposite effect. Now just figure out which of these changes make the prefix sums non-negative and the total sum equal to zero.

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

thanks for an actual Div 3 round!!! on a side note, does anyhow know how to D? I struggled at it quite a bit.

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

    If two integers are in the same line, this means they're adjacent in the graph. The input gives you all n edges in the graph (though maybe not oriented correctly).

    Arrange the edges to form a cycle. You may need to reverse your output if the edges are facing the wrong direction.

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

      that's the problem I'm facing — how do you know if the edges are in the wrong direction?

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

        Look at the first 3 values. If they match what's given in the input, then the solution is facing the correct direction. Otherwise, reverse the output.

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

      i tried topological sort but it gave me WA on test 3

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

    The approach I used is slightly different: if a and b are on the same line, then either b occurs on the line of a or a occurs on the line of b. We check which of these two is the case, and immediately know whether there is an edge from a to b, or from b to a. By doing this operation for every line, we calculate all the edges with the correct direction. The only problem with this approach is that it may give incorrect answer for n = 3; but outputting 1 2 3 always works if n = 3, since the all the inputs for 1 3 2 would be correct for 1 2 3, as well.

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

    ezaf dude, if a[a[i]] == b[i] or b[a[i]] == b[i] then next_to[i] = a[i], else next_to[i] = b[i]. then print 1, next_to[1], next_to[next_to[1]], ...

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

    Since n>=3 Consider if we are at node "a" and we know by input that node "b" and node "c" are its next nodes So, case would be like

    Case-1 : a->b->c Case-2 : a->c->b

    To verify which is the case , simple check that if "c" comes in the next_nodes_list of "b". Then it will be Case-1. If "b" comes in the next_nodes_list of "c", then it will be Case-2

    If it is case-1 , then it is sure "c" does not contain "b" in its next_nodes. If it is case-2 , then it is sure "b" does not contain "c" in its next_nodes.

    Use this above condition and put nodes in order.

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

    I solved it in the following way —
    1) every number will appear exactly 2 times, one in the vertex to which it is next and and secondly in the vertex where it is next to next.
    2) lets look for the vertices for which we get 1, and let then be called vertex a and b. so the order is either a b 1 or b a 1.
    3) we go to vertex a and look for b , if b is there it means b comes after a so the order is a b 1, or if not present the order is b a 1.
    3) After getting the order of first 3 element we will look for the adjacent vertices of vertex at index 1 [ 'b' in case of a b 1, and 'a' in case of b a 1], the vertex other than 1 will be the vertex at index 3, after we will repeat this process for all the vertices up to index n-3.
    my submission, time complexity O(n)

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

Problem E was almost the same as BRCKTS problem from SPOJ.

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

Когда можно будет дорешать задачу?

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

Easy round, I solved all problems

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

    You mean you consistently got WA on testcase 2 on all problems?

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

Does hacking help my rating?

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

!(my last comment) = I love div3 rounds :P

anyway how to solve D it looked like a graph problem to me

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

    There is no need for graph. Using 1 as the first number, find the first 3 numbers with brute force. Then its easy implementation.

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

    It was a simple implementation problem.

    1. You just need to find a possible permutation of first 3 elements. lets say, p1, p2 and p3.

    2. Then you can easily find the rest elements.

    How?

    Finding part 2 is easy,

    As you know p2 and p3, you can easily find p4 because, only number after p2 other than p3 is p4.

    In other words, a21 = p3 => p4 = a22; And so on, we can find p5, p6....pn

    For part 1,

    Fix p1 lets say '1'; now p2 and p3 can be either a11 or a12. How to fix them?

    If a21 = p3 or a22 = p3 then p1, p2, p3 is correct; else p1, p3, p2 is correct;

    Check my submission: https://codeforces.com/contest/1095/submission/47575058

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

Can I get a hint for problem C:Powers of 2

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

    Check the binary representation of the input

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

    First find the binary representation to know the minimum powers necessary. Now, if we can represent n using x powers of 2, then we can also do it using x+1 powers of 2, provided x < log2(n). Think about how to get x+1 powers from x powers.

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

      Can you elaborate further by taking an example?

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

        Suppose you have x slices of pizza, but you want to have x+1 slices what do you do, divide one of the slices into 2, now you have x+1 pizza slices.

        Similarly, if you have minimum powers of 2 necessary to make a number. you can keep on dividing the numbers till you get k numbers.

        you can also do it recursively. See my codes: 1) Recursive 2) Iterative (Using a queue)

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

Wonder why Problem F if there are Multiple index have smallest cost pick any of them to build edge to is ok

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

    you can refer to MST Algorithm like Prim and Kruskal

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

      i means the given a1~an may have multiple of them have same smallest value and why i pick any of them build edge connect to others the answer will be same

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

        you can consider why MST Algorithms like Prim and Kruskal do not care about that

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

    Assume we've already chosen which special edges will be present in our tree. We need to figure out the cheapest way to join the connected components that they induce.

    The total weight for the other edges is some expression of the form ai1 + ai2 + ... + aik. We have to choose at least one vertex from each connected component induced by the special edges, so the minimal possible value of the expression for fixed k (ignoring any other restriction) is obtained by first adding the smallest ai from each component, and then adding the smallest ai of them all however many times. By choosing any vertex with minimum cost we will get exactly this value for the expression, so it doesn't matter which one we choose.

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

Can F be solved by Prim's Algorithm?

I thought this is MST problem, but how can we find MST when we have so many edges? I know we can use binary heap, priority queue and some data structures on Prim's algorithm, but I don't get how to fit in time and memory.

Plz let me know if I'm missing something.. (I'm not even sure if this is a MST problem or not)

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

    It is MST, with an extra idea. It turns out the only edges with costs ax + ay that we need to consider are the ones that involve the vertex with minimum cost.

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

    It is a MST problem. Use the set 1 as the given edges. find the smallest ai and make n-1 edges this vertex to other vertices. Call this set 2 of edges. combine both sets and apply prim's algo.

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

Any one can help me with problem E! I have no idea how can i solve the problem!

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

I'm getting a wrong answer by the checker but if I compile it elsewhere I get the right solution.

The checker's log read: wrong output format Unexpected end of file — int32 expected

Can someone explain what is happening Submission

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

In Problem D, can the permutation be in any cyclic order (clockwise or anti-clockwise)? Like for this test case 5 3 5 1 4 2 4 1 5 2 3

is this 1 4 2 3 5 also a valid answer?

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

    No. 1 4 2 3 5 is invalid. You must consider the order. (i.e standing in front or back matters)

    You should check clockwise or counterclockwise. After that, starting point doesn't matter.

    1 5 3 2 4

    5 3 2 4 1

    3 2 4 1 5

    2 4 1 5 3

    4 1 5 3 2

    These are the only valid answers for first example.

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

Problem D is ambiguous, I cannot understand what he want. can anyone help me please. thanks in advance.

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

    There's a directed circle(a premutation p), giving the two vertexes behind every vertex, you should print a valid order.

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

Why all Java solutions on B are getting hacked? Although they all seem correct.

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

Why did my solution for F Link failed?? Update:Solved

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

for problem D, why WA??? Judge says wrong output format Unexpected end of file — int32 expected

link to my code is Your text to link here... please someone check it...

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

A lot of people got hacked on Problem B, including myself. Does anybody know what the issue could have been?

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

    Hey:)

    So Java's Arrays.sort() uses quicksort, and the average runtime is nlogn but worst case runtime is n^2. The hack is an anti-quicksort hack. To fix this, you should declare the array as Integer[] rather than int[], since merge sort is used to sort objects, which runs in time.

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

What does this statement mean in problem "F. Make It Connected"?

You don't have to use special offers: if there is a pair of vertices x and y that has a special offer associated with it, you still may connect these two vertices paying ax+ay coins for it.

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

    If an offer with cost w is included, the cost of building an edge connecting x and y can be either ax + ay or w, it's up to your choice (yet obviously if you're really going to build that edge you would want the minimum value between them).

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

    For two vertices x and y, there may be some special offers. You may potentially use one of these offers during the construction if you want to connect x to y. However, you can connect x to y without using any of these offers, as well. In that case, the cost of connecting x and y is given by ax + ay.

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

Today during contest I got WA on test 1, for problem D. While it ran well on my IDE with correct answer. My submission: https://codeforces.com/contest/1095/submission/47569625

Later after 20 mins I realized, I had left a return false; statement inside the check() function. After adding the line it got accepted. (https://codeforces.com/contest/1095/submission/47575058). If it wouldn't have worked on my IDE I would have fixed it and submitted in matter of seconds, rather than 20 mins of trying to find some error which still works fine on my IDE. Any ideas why it worked fine for all sample cases plus my own custom cases, on my IDE but not on cf server?

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

Today during contest I got WA on test 1, for problem D. While it ran well on my IDE with correct answer. My submission: https://codeforces.com/contest/1095/submission/47569625

Later after 20 mins I realized, I had left a return false; statement inside the check() function. After adding the line it got accepted. (https://codeforces.com/contest/1095/submission/47575058). If it wouldn't have worked on my IDE I would have fixed it and submitted in matter of seconds, rather than 20 mins of trying to find some error which still works fine on my IDE. Any ideas why it worked fine for all sample cases plus my own custom cases, on my IDE but not on cf server?

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

    It's called "undefined behaviors".
    Since the function return a non-void value and you left its ending ambiguous (not stating explicitly if it would return true or false), so depending on the compiler and environment of your PCs, IDEs or online judges, the returning value will fluctuate.

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

declare the round unrated for java users whose B was hacked!

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

      why should that happen?

      there is no difference between getting hacked or failing the system tests (there are also enough problem setters who directly include such testcases for systemtests so no hack is needed).

      And you will learn from this and will think about this the next time you use Arrays.sort...

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

    they gave the java users only 1k ms they should have given 2k ms

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

For java we are allowed 2000 ms for a problem in which the limit is 1000ms but here we got a tle at 1000ms

submission here: http://codeforces.com/contest/1095/submission/47602564

please rectify this

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

      the problem is NOT that java is generally slower! the problem is that you used an algorithm which is in O(n^2) which is clearly to slow!

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

        So according to you what could be an alternative to Arrays.sort() for getting O(nlogn)?

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

        According to the documentation of Arrays.sort()

        Implementation note: The sorting algorithm is a Dual-Pivot Quicksort by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations.

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

        hey i read your blog. Thanks for the information, I got what you were trying to say.

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

I Learn a very important thing in this contest. DO NOT FEAR to read hard problems. I am able to solve problem F easily with kruskal, but i didn't solve it during the contest because I always thought that if I can't solve easier problems (problem C and E), i can't solve the harder one.

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

Hi Everyone,
I got a runtime error due to wrong evaluation of log(n)/log2 by the CF compiler, but it is being evaluated fine in my own ide, and a number of online compilers. Isn`t it unfair for me. my submission,problem c. For input 8,1 CF compiler is evaluating it as 2, where as it should be evaluated as 3

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

    Nope, it crashes in your while

    while((k-cnt) != 0){ ...
    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      yes, but that`s because 'sz' was evaluated as 2, if it would have been evaluated as 3, I would have got "YES 8"

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

        Gotcha, it's weird behavior. As to why, i guess you should consider that doubles aren't exact just as the result of log() isn't, so the division isn't exactly 3. You should avoid doubles whenever possible, in this case when you want to check over log in base 2 you should use bit operations.

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

    Try using log2(n) instead of log(n)/log(2). Idk, it may work or not, but you should have gone for ceil value anyway.

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

I love Vovuh's Problem set...He is making Div3 great

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

My Submission 47584196 was rejected by Codeforces compiler because the values of INT_MAX and LONG_MAX are apparently same on codeforces it works perfectly on my laptop! Isn't this unfair to me? What can i do about this now?

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

Could someone help me with problem E? I think I have not understood what is a regular sequence. In the first example — (((()) , can I change the second bracket to get ()(()) or change the 4th to get ((())) ? I can insert 1 and + into them such as (1)+(1+(1+1)+1) and (1+(1+(1)+1)+1) but why are they not regular ones?

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

What is the solution to Problem B? I am getting WA on test case 6.

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

    There is 3 cases. The first one is to take one element that is not minimum nor maximum: The instability doesn't change. The second case is to take one element that is maximum: The instability will be the maximum of the new array minus the minimum of the array. The third one is to take one element that is minimum: The instability will be the maximum of the array minus the minimum of the new array. So the answer is min(second case,third case).

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

In problem C, Many solutions are getting runtime error on test case 10 that is 1 1 But it is showing right output in almost every other compiler/IDE

Here's my code. https://ideone.com/qVAsiL

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

How to solve E?

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

How to approach problem E?

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

    try to think when flipping a single character will make the whole sequence good , character can be "(" or ")" at each position so just two case, see what should be the number of EFFECTIVE "(" and ")" on both sides of concerned index. there difference must be one(you can verify). but we must be careful that either left or right side should not have parts which cannot be balanced either. while going left to right(maintain array A) try to maintain the net effective number of "(" at each index, means for all 0<=i<=n-1 store number of free "(" from [0->i] , and do same for ")" while going from right to left(maintain array B) maintain num of free")" for each i .

    on which indices we should perform the tests because other indices may give positive test instead of them they are wrong->

    if for any l>=0 A[l]=-1 then we should not check for indices greater than l (convince yourself by examples) because they will never effect left part in any better way so range to check will be [0,l] l can be at max n-1 ,similarly in array B for index i<=n-1 check till you approch 0 or where it is negative first time.

    check should be made finally on intersection of [0,l] and [m,n-1] :)

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

    Calculate balance of given string. Let bal[i]=balance of substring [0;i]. (Balance is a sum of opening and closing brackets). Now go through this array and check:

    1) if bal[i-1]<0 at any moment, then you can stop and print answer, because you won't be able to make correct bracket sequence later anyway.

    2) if s[i]=='(' then by changing it to ')' balance will decrease by 2 from [i;n-1] in bal[]. So you need to check that minimum in bal[] from i to n-1 is >=2 and bal[n-1]==2. If it is true then increment answer variable.

    3) if s[i]==')' then same logic. Just check if min>=-2 and bal[n-1]==-2.

    To find minimum on interval you can just use multiset. See my solution

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

а когда разбор будет?

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

Can someone explain why my code is hitting a TLE for problem E? It should be running in O(n) I think. https://codeforces.com/contest/1095/submission/114321843