vovuh's blog

Codeforces Round #565 (Div. 3)
By vovuh, history, 6 years ago, translation, In English

<almost-copy-pasted-part>

Hello! Codeforces Round 565 (Div. 3) will start at Jun/09/2019 17:35 (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 awoo Piklyaev, Maksim Neon 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.

</almost-copy-pasted-part>

UPD1: Big thanks to Um_nik, Rudy1444, nigus, _overrated_ and Temotoloraia for testing the round! And also big thanks to my dear friends Ivan BledDest Androsov, Roman Roms Glazov and Mikhail awoo Piklyaev for help with round preparation!

UPD2: Editorial is published!

UPD3:

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 Yushen 6 235
2 IMRED 6 293
3 BudiArb 6 345
4 xenoframium 6 350
5 njchung93 6 439

Congratulations to the best hackers:

Rank Competitor Hack Count
1 nikolapesic2802 69:-15
2 stefdasca 42:-11
3 dorijanlendvaj 15:-11
4 orz_liuwei 10:-11
5 interestingLSY 5:-1
170 successful hacks and 236 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
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

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

Comments Comments (185)
| Write comment?
»
6 years ago, # |
  Vote: I like it -11 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Div3 Contest == vovuh

→ Reply
»
6 years ago, # |
  Vote: I like it -44 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it -15 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    No! It's a tradition! It will forever be there!

    → Reply
»
6 years ago, # |
  Vote: I like it +35 Vote: I do not like it

Let me think :

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

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +79 Vote: I do not like it

    mathematics 100

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +36 Vote: I do not like it

    Let me rethink :

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

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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +59 Vote: I do not like it

      mathematics 2100

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +47 Vote: I do not like it

      A further thinking:

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

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

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      Div.3 participants are very lucky

      Div.3 ⇐⇒ Div.(2 + 3)

      Also can take a part in Div.2 contests

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +117 Vote: I do not like it

        lucky
        div. 3
        it is like saying "paralympians are lucky because they can participate at paralympiads"

        → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    the next prepare many DIVs for you,the div3 is for the rating lower than 1600

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    The trick is to get lucky, this is the second time I fall from expert to specialist and the next round is DIV3.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    haha

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

cheer up

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Wish everyone have fun!

→ Reply
»
6 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

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

          → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I've got accepted with this idea.

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

    55365600

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 4   Vote: I like it +3 Vote: I do not like it

      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
      → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Why is this TLE?

TLE

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    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$$$.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +12 Vote: I do not like it

        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.

        → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I dont know. As for me, it was not too hard. A,B — quite standard problems. C — binary search, D — Sieve of Eratosthenes, E — vertex paint. But maybe i'm wrong

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      C can be solved in O(n).

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      O(n): https://codeforces.net/contest/1176/submission/55357808

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You're not wrong at all, its my fault that I didn't get these, but the fact that on the previous Div2 contest I got ABC and I couldn't even get Div3 B now is stupid from me. Looking at the solutions, the solutions are pretty clear, but they didn't seem pretty clear to me when I was trying to create one by myself. I'm just venting because I've tried really hard to come up with a solution but I couldn't do it because of simple restrictions in the problems that I just couldn't overcome.

      → Reply
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Can you hack my randomized solution for E? 55348371

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Whats number of the taks?

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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).

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

How do I delete a comment

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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).

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

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.

→ Reply
»
6 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I am getting a runtime error in Problem E. Can someone help fixing it. Link to Code

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Logic: I do a BFS starting from the node having largest degree and proceed to add nodes in the answer which are present at odd levels with respect to the root.

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    https://codeforces.net/contest/1176/submission/55374222 i have done the same !! why it giving me tle ?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Memset color giving u tle, because if there are 2 nodes and 10^5 test cases that gives u 10^10, u need to clear color just size of n, also clear graph size of n

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Sir, I love your videos regarding competitive programming and always get motivated

    → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    We can find the distance of all nodes from root(1). (using simple DFS)

    Then we can select even or odd distance nodes which fulfill ( N/2 — condition) .

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Testcase 6 in problem C ?

→ Reply
»
6 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    maybe due to the use of remove function. I was doing the same at first attempt .

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

What is wrong with this solution 55346608 of B?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    rem[1] -= min(rem[1],rem[2]); rem[2] -= min(rem[1],rem[2]);

    when you subtract from rem [1], the result increases as the already subtracted rem [1] is subtracted from rem [2]

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    You are changing the value of res[1] before calculating min(res[1],res[2]). Store the value in some other variable and then u can use it later. I have corrected your code : https://codeforces.net/contest/1176/submission/55376346

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the hacking test case for Solution E ??

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I meant share hacking test with others

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        The contest is already over and I think any discussion about only seems useful

        → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      How is it unfair?

      Nobody is being awarded any marks for hacking other's submission.

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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. :/

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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..

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    you use memset T times

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 3   Vote: I like it +23 Vote: I do not like it

        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.

        → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 4   Vote: I like it +6 Vote: I do not like it

    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).
    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Will an unsuccesful hacking attempt affect my rank?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it -9 Vote: I do not like it

When you get WA on submitting C.

PS: Those who have watched Lost will relate.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    Indeed, this number sequence is the one used in "Lost".

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How come I am getting TLE? Problem E

https://codeforces.net/contest/1176/submission/55377412

→ Reply
»
6 years ago, # |
  Vote: I like it +7 Vote: I do not like it

WTF !!!

Memset gave me TLE in E.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem E ?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      understood ! thank you very much.

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Bop it!

→ Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

ss

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How come I am getting TLE? Problem E

https://codeforces.net/contest/1176/submission/55377412

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you define vector t times with size MAXN.

    → Reply
»
6 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Editorials?

→ Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

did it rating?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 3   Vote: I like it +13 Vote: I do not like it

      I get it. I should read the problem description closely. Thank you!

      → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +13 Vote: I do not like it

    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].

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Good contest with less number of hacks :)

→ Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +11 Vote: I do not like it

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

    1

    7 6

    1 2

    1 3

    1 4

    2 5

    3 6

    4 7

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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);..."

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -6 Vote: I do not like it

Editorial please

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      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 ,

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your algo is correct

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But, why getting WA ?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 2   Vote: I like it +9 Vote: I do not like it

        "The array contained only prime numbers and printed lowest half of prime numbers" — I think this is incorrect.

        3
        2 3 3 5 5 11

        Correct answer: 2 3 5
        Your answer: 2 3 3

        → Reply
»
6 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Can you please make an editorial for this contest?

→ Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Editorials?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply
»
6 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Are there editorials?

→ Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +7 Vote: I do not like it

When will the editorials be published?vovuh

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +24 Vote: I do not like it

Hi

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

→ Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it +19 Vote: I do not like it

    Wow such an amazing problem!

    But it seems to be NP hard cause I think if we can solve this we will solve that type of SAT that want minimum sum of variables.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is this solution right solution ? 55421378

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Best of Luck for your first contest as a problemsetter.

→ Reply