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

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

<almost-copy-pasted-part>

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

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

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

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

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

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

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

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

Удачи!

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

</almost-copy-pasted-part>

UPD: Пользуясь случаем, хочу пригласить желающих в летнюю школу программирования Сазанка-2019 (больше информации вы можете найти здесь). Осталось несколько свободных мест. Там буду я, Иван BledDest Андросов, а также приедет Михаил MikeMirzayanov Мирзаянов! Регистрация закончится 23 июня.

UPD1: Большое спасибо Um_nik, Rudy1444, nigus, _overrated_ и Temotoloraia за тестирование раунда! Также спасибо моим дорогим друзьям Ивану BledDest Андросову, Роману Roms Глазову и Михаилу awoo Пикляеву за помощь с подготовкой раунда!

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

UPD3:

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

Место Участник Задач решено Штраф
1 Yushen 6 235
2 IMRED 6 293
3 BudiArb 6 345
4 xenoframium 6 350
5 njchung93 6 439

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

Место Участник Число взломов
1 nikolapesic2802 69:-15
2 stefdasca 42:-11
3 dorijanlendvaj 15:-11
4 interestingLSY 5:-1
5 orz_liuwei 10:-11
Было сделано 170 успешных и 236 неудачных взломов.

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

Задача Участник Штраф
A riz_1_ 0:02
B _ekaterina_dudina 0:04
C BudiArb 0:05
D hxylalala 0:18
E csts.21 0:17
F njchung93 0:32

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

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

It will be a great contest... Best of Luck to all...

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

Div3 Contest == vovuh

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

ITS INDIA VS AUSTRALIA IN THE CRICKET WORLD CUP ....#TIMECLASH

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

I think that "copy-pasted part" is just a dead meme, let it go

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

Love div3!

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

Let me think :

$$$ Div.3 \Leftarrow \Rightarrow Div.(1+2) $$$

so why not rated for someone whose rating is more than 1600

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

cheer up

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

Wish everyone have fun!

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

I just want to say I appreciate the Slay the Spire problem.

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

What is the solution for F? I can't understand why my dp solution didn't work. I had dp[i][j] that means maximum cost for the first i rounds if the count of the total cards we use is j modulo 10.

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

    I had the same idea and it got AC https://ideone.com/rRrMmW

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

      Well I still don't get it my solution is wrong. I almost did the same things as you. Can someone please check my code?

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

        I think the cause of the problem is this code: int t; if (j % 10 != 0) t = 1; else t = 2;
        Check, for example, this test case:

        4
        3
        1 1
        1 1
        1 1
        3
        1 1
        1 1
        1 1
        3
        1 1
        1 1
        1 1
        3
        1 1
        1 1
        1 1
        

        The answer is 13 while you program prints 12

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

          Ah, shit. Thanks for you help, the problem was the case when new 10'th is created. Now I fixed it T_T

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

    My solution had the same idea also and it fails on testcase 2. Did you take into consideration that you can reorder the cards of each round however you want?

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

    I've got accepted with this idea.

    int dp[2][10]; /// cur/prev, cards count modulo => max damage
    

    55365600

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

    This is the solution for F, maybe you made mistake in considering the different cases.

    1. Choose only one three cost card (if exists)

    2. Choose one two cost card and one, one cost card (if exists)

    3. Choose one two cost card (if exists)

    4. Choose 1-3, one cost card (if exist)

    5. Choose no card.

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

      Instead of considering multiple cases we can do the following:

      1. Store at most three cards that give most damage for each cost
      2. Iterate through all possible combinations of amounts of cards for each cost. So we can take $$$(0,1,2,3)$$$ of cost $$$1$$$, $$$(0,1,2,3)$$$ of cost $$$2$$$ and $$$(0,1,2,3)$$$ of cost $$$3$$$. In total $$$4^3 = 64$$$ possible combinations (not of them are valid, of course, but we can check it manually for each combination)
      3. For each combination check that total cost of all taken cards is less than $$$3$$$
      4. List all damages of taken cards in common list and sort it
      5. Now we can easily get the amount of damages with doubled card and without doubled card and update our DP with these results
»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Why is this TLE?

TLE

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

    There can be up to $$$2*10^5$$$ test cases in the problem with graph containing only one edge (1, 2). Your solution creates so many arrays of size $$$2*10^5$$$ each, and it leads to quadratic complexity of the solution. Replace all arrays with vectors of size $$$n$$$ instead of $$$2*10^5$$$.

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

      Same happened with me. But vovuh I have declared a global array fo all test cases. Why does this give TLE? Shouldn't the memory allocation be just once for all test cases as I have used a global adjacency list??

      55377706

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

        In your case the problem is in the adjacency lists. Where do you clear them between test cases? I think your bfs works too long overall. I don't know how it passed the first test lol.

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

I was completely surprised by how hard these Div3 tasks were..

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

Can you hack my randomized solution for E? 55348371

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

I was not able to solve a single problem in this contest. Any direction to improve this. I was stuck in question number one itself for more than 1.30 hrs. in the last minute I got a correct solution for the test cases but forgot how to take input from multiple newline.

Any direction would be helpful.

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

    Whats number of the taks?

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

    The best and straightforward answer is just solve more problems. I've started CF 2-3 months ago, and I'm better now than I was then purely because I've simply solved more problems.

    I managed to only solve A in this contest when I usually do ABC in Div3, but that attributes to me mostly not solving enough problems that are similar to this.

    All other advice pale in reference to the first I provided you, but its also nice to know that Div3 ABC and Div2 ABC can almost always be solved greedily (they just require implementation/data structures and not complex algorithms like graphs or dynamical programming).

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

    In fact, A was not as easy as it should be. I solved it by trying in which order the three operations should be applied. But I still dont know why the one I finally submitted works, and others do not. B was less problem for me than A. As a suggestion, try to keep calm if it does not work out as expected.

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

How do I delete a comment

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

Why is this approach wrong for the problem E:

For every edge, if a vertex is not taken and is not visited by a previously taken vertex then I will take this vertex. Any sample case to prove that I might take more than n/2 vertices.

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

    Example from awoo:

    Picture

    If you'll start coloring from the vertex $$$5$$$, you cannot take less than $$$3$$$ vertices to cover all vertices (vertices can be reordered so the vertex $$$5$$$ will be vertex $$$1$$$ or something like this).

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

    Consider a chain of length 3. If you start from one end, you will need to color 2 vertices which is more than 1.

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

      If both nodes are unvisited I was taking one with a greater degree so this case was being covered but the example from vovuh is what I was missing.

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

    maybe smth like 1 -- 2 -- 3 -- 4 -- 5, you get 1,3 and 5?

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

getting runtime error in problem D but working fine on local ide.

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

For D, you need to sort the array and then look at the largest number, say L. If its kth prime, then L can't be part of original array, so we add k as one of the elements of original array. We remove L and k after this from array and repeat. If L were composite, then it definitely gets added to original array and we remove L and its highest divisor from the array. The highest divisor can be found easily if you store for every number what is the smallest prime that divides it. Use seive smartly.

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

For E, just color the graph with alternating white and black colors. I know it may not be bipartite but its okay. Then if white nodes are more than N/2, we chose black nodes.

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

What is wrong with this approach for E : I will consider all the nodes which has only 1 adjacent node and take that one adjacent node into the answer set(not the node which has only 1 adjacent node).Then go for the the existing nodes one by one and if not adjacent to any node that i picked already I will take that too.

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

Testcase 6 in problem C ?

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

Number theory and Graph theory? it seems really difficult for div3

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

Can anyone tell why I am getting TLE in Problem C at TC:7 https://codeforces.com/contest/1176/submission/55371060

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

What is wrong with this solution 55346608 of B?

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

What is the hacking test case for Solution E ??

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

    Is it legal for codeforces? If so, it seems to me unfair

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

    In my case: My solution got Hacked because of using memset(visited,0,sizeof(visited)); for each test case. The size of visited array in my soln was 2e5. So if the number of test case is 2e5, it will give TLE. :/

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

This is really strange behaviour I have observed. My solution is absolutely correct but still giving tle. can someone look into this. Thanks in advance.

My solution

It is really annoying to see people with the same approach pass the solution. where as my solution fails.

Soulution with similiar Approach that passed

Aonther Such Solution

And here one more

I kindly request community to help me figure out the issue. Correct solution being hacked due to some disgusting silly tight time constraint is really frustrating..

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

    you use memset T times

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

    Using memset T times: giving TLE. Even my solution got hacked due to same reason :/

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

      I guess that's really awful. getting tle for absolutely correct solution. what say?? Such silly tight time constraints shouldn't be entertained. Even if one puts up correct solution, getting unsuccessful verdict for this is really not done.

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

        Well, I think that we should have been more careful about it. It was clearly written that the number of test case are till 2e5. We could've done without using memset. Check my latest submission.

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

        I don't see anything awful. Maybe you see this for first time. But doing something unnecessary should not be entertained and that's what problem author has done! When you don't need $$$2\times 10^5$$$ nodes in each test case then why using memset? You should know about the functions before using them.

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

Will an unsuccesful hacking attempt affect my ranking?

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

Can you explain me why is it working as it is working?

55375918 this solution gets OK

55375854 this solution get TL

But the problem is, the asymptotic is the same.

The difference is that in first submission we check from 2 to x-1

and in second from x-1 to 2.

Am I missing something?

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

    The number 1530169 = 1237 * 1237 is not a prime, so in the first program you will iterate from 2 to 1237, but in the second program you will iterate from 1530168 to 1237.

    • In the worse case the first program will iterate from 2 to sqrt(x).
    • In the worse case the second program will iterate from x-1 to sqrt(x).
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Will an unsuccesful hacking attempt affect my rank?

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

I am curious about how to do for minimum number of vertices in question E, anybody can help?

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

When you get WA on C.

PS: Those who have watched Lost will relate.

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

When you get WA on submitting C.

PS: Those who have watched Lost will relate.

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

WTF !!!

Memset gave me TLE in E.

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

    I think it's because you use memset in the beginning of each test case. Which is around 1e5 test cases, and you use memset for an array with a size of around 1e5, so its basically a TLE.

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

is using memset inside the test cases loop making E questions wrong ?? Hard Luck to those who have not taken care of it.

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

How to solve problem E ?

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

    You can DFS or BFS start from node 1 to build a tree of the graph. Now if the number of nodes which have odd degree is <= n / 2 then the answer is all of them, otherwise the anwser is all the nodes which have even degree.

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

    Notice that this problem can be solved on a tree this way:

    1. paint a tree in two colors (black / white), this way each edge will connect vertices of different color and it will guarantee us that each white vertex is connected with at least one black and vice versa
    2. splitting vertices into two groups guarantees us that one of these groups will not be greater than $$$\lfloor \frac{n}{2} \rfloor$$$ (application of Pigeonhole principle)
    3. We can select any group of vertices to solve the original problem, so we need to select smaller group of vertices

    Now, we can notice that removing edges from our graph without breaking it into multiple connectivity components does not affect the solution correctness (if we satisty all conditions with less amount of edges, we still satisfy it for any additional edges). This allows us to delete some edges from our graph without breaking connectivity. So, we can delete all edges and only leave a spanning tree of our graph (we can do it with DFS) and solve problem on a tree.

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

      understood ! thank you very much.

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

      how i can get a tree by delete some edge?i do not understand you

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

        We can find an edge that does not break a graph connectivity and delete it from our graph. If we will repeat this operation until there is no edge left that can be removed from the graph without breaking conectivity the graph will become a tree. This happens because we can only delete an edge that is included in some cycle in a graph and when we will eliminate all cycles in given graph it will becaome a tree. Such tree is called spanning tree of our graph.

        But in practice it is not efficient to build spanning tree of a graph by iterativety deleting edges and checking connectivity after this. We can utilize some graph traversal algorithm here, such as DFS or BFS. These algoriithms have an important property: they visit each vertex only once. So, we can track the edge that was used to come to each vertex for the first time (except for the starting vertex). Obviously there will be no cycles in choosen edges, so we will get a tree that connects every vertex that can be reached from the starting vertex. So, we get a spanning tree of our graph.

        These trees are also called DFS-tree or BFS-tree and have some additional useful properties along with being a spanning trees of a given graph.

        Hope this explanation helps.

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

if anyone wants to hack plz hack my solution of E i want to know whether it is correct ??

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

Bop it!

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

Hey guys, I have made a new app Coding List which contains all live, upcoming programming competitions from hackerearth, kaggle, codechef, codeforces, topcoder, aigaming, hackster, codinggame, hackerrank, projecteuler, atcoder and many more.

A must have app for programmers. Please rate and review it. Try it here https://play.google.com/store/apps/details?id=io.github.vikasgola.coding_list

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

ss

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

Can anyone please tell why am I getting TLE in Problem E: 55381696 Thank you..

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

Did C using recursion(dfs style). But I guess many did in iterative way. Anyways complexity comes out to be $$$O(n)$$$.

Here is the Code

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

Hey guys, can anyone tell me what's wrong with my solution for C (https://codeforces.com/contest/1176/submission/55357077) ? I fail test 7 and I don't see why. Maybe someone can tell me a counterexample for my approach.

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

    i don't know if that is the main problem or not .. but test like this

     14
     4 8 15 16 23 23 42 4 8 42 15 16 23 42
    

    fails in your code .. you pop from the queue whenever you enter the function even if the sequence isn't right so you affect the following sequences.

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

Can someone tell me why this TLE plz? Thanks! Code

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

Editorials?

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

did it rating?

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

The writer of F( Destroy it!) must be a Slay the Spire player !

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

Can someone check my code in Problem D? I have no idea about why it got Memory limit exceeded on test 5.

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

    your bug is in finding maxD. actually you're finding greatest prime factor! and cause of this you may erase something which is not in multiset(st.end()) from it and you get memory limit in this case

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

    I think you're incorrect fill maxD. maxD at your logic is max prime divisor while you need there to just max divisor.

    You can fix it, if replace maxD with minD and try to find p / minD[p] instead of maxD[p].

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

Good contest with less number of hacks :)

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

Can someone help me? Problem C, my code I am getting answer 65 in test case 65 instead of 64.

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

I suggest you read my_solution for problem F(Destroy it!). I have dp[N][10] that dp[i][j] is maximum sum if we have get x cards from first i round and x mod 10 = j. and it's easy to see that in each round we may use only 3 strongest card that cost 1, strongest card cost 2 and strongest card cost 3 so by a mask on these(at most 5)cards you can update dp easily. if you have shorter solution please tell me

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

    I think this is intended solution. I have something similar but I didn't debug yet. And I really doubt there is something shorter

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

In problem E why an output of:

2

4 5

wrong for the test case:

5 8

2 5

2 1

5 1

4 5

1 4

2 4

3 4

3 5

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

    For this test case your output is correct. But in test#2 there are 40057 testcases. You just wrong output in some other testcase.

    P.S. Your solution is incorrect for graph-chain. Lets imagine graph 1-2-3-4-5-6. There are 6 vertexes. And you output n / 2 vertexes with smallest degrees. There you can output vertexes 1, 6, 2. And vertex 4 remain unconnected.

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

    your solution isn't correct let's try this:

    1

    7 6

    1 2

    1 3

    1 4

    2 5

    3 6

    4 7

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

Sorry if this question is trivial but I don't relly get the solution of C. I think that we just need to find the number of subsequences that can be formed from the given array by finding the minimum frequency of 4, 8, 15, 16, 23 and 42, right. But that solution fails at test 6, which I don't understand why because clearly we can have 13 subsequences in this case.

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

    Your solution doesn't respect order of numbers.
    As said in task:

    "Examples of bad arrays:

    [4,8,15,16,42,23] (the order of elements should be exactly 4,8,15,16,23,42);..."

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

Can someone please have a look at my code for problem D. I can't understand why it is giving WA on test case 20. Thanks

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

Editorial please

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

Can somebody help me out here? This submission for problem A where i used map to store results gets TLE whereas this one which uses brute force doesn't. Shouldn't the former just reduce complexity?

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

    First solution does three recursive calls, second always does only one.

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

      Oops, I didn't even notice that i used if instead of else if there, this was quite stupid to even ask, Btw Thanks mate.

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

for problem A why do you choose this order of operation 4*n/5 , 2*n/3 , n / 2 ?

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

    I don't think the order matters in this question, as the number of steps depends on the prime factors of the number itself. Let's take 60 for example, here 60 = 3 * 5 * 2 * 2 ; so it will always require 2 operation 1, 1 operation 2 and 1 operation 3 and as second and third operation multiplies 2 and 4(2 * 2) respectively, we would need to apply first operation 3 more times. Hence, the answer would be 1 + 1 + 2 + 3 = 7 irrespective of the order of operations applied.

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

      let's take n = 10 and order /2 , 4/5 ,2/3 then n is 10 , 5 , 4 this outputs -1 so order does matter if u do it this type of operations but i think you to wanted to get its factors so you do /2 , ans ++ , /5 , ans+= 3 , /3 ,ans+= 2 ,

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

        Dude, for 10 if you apply 1st operation first then it would go like this 10 -> 5 -> 4 -> 2 -> 1 (applying 1st operation two more times when n was transformed into 4). if you apply 2nd operation first then it would go like this, 10 -> 8 -> 4 -> 2 -> 1. Number of operations remains same irrespective of order (in this case it is 4). And this should hold for every number as number of operation depends solely on the factors of that number.

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

Getting WA in problem D. My logic:

First, I sorted the given array in descending order. If a number is composite, I printed it and removed this number and it's highest divisor. Finally, The array contained only prime numbers and printed lowest half of prime numbers. My submission.

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

Can you please make an editorial for this contest?

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

Editorials?

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

Div.1⇐⇒Div.(2−3+3-1)

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

Hello, I have no idea how a girl @hdude0164 managed to copy my solution during the contest. I don't know her by any chance whatsoever. I don't use any online IDEs, I use dev cpp on my laptop and submit the solutions on codeforces. I don't know what else could be provided as proof to prove my innocence. I had submitted the solution 15 minutes prior to her. Plus i did some research, her original account is @chhavij and this is surely some fake account. Please look into it.

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

Are there editorials?

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

Also, can someone explain why is C a binary search problem?

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

When will the editorials be published?vovuh

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

Никто не знает когда разбор? Хотелось бы узнать решение задачи F. Я дальше алгоритма укладки рюкзака не придумал(ва2)

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

    По сути там и есть рюкзак.
    dp[n][i] — максимальный урон после n ходов, если использовалось кол-во карт, остаток которого на 10 равно i.
    На каждом ходу есть всего 5 возможностей выбрать карты. А дальше все тот же рюкзак.

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

Hi

I saw you need editorial so i wrote this my self i hope it's useful for you

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

In problem E how can we find the minimum number of nodes to be chosen to satisfy the given condition

»
5 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
  1. Запустил всю нужную аппаратуру за 20 минут до начала.
  2. 20 минут спустя.
  3. 20 минут спустя забыл о раунде.
  4. Вспомнил спустя 2 часа.
  5. Мораль такова:Ждите 20 минут не уходя с сайта.
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

https://codeforces.com/contest/1176/submission/55406758 Can someone explain me why is it failing?

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

Why is this solution right solution ? 55421378

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

Best of Luck for your first contest as a problemsetter.