Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

vovuh's blog

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

Hello!

Codeforces Round 490 (Div. 3) will start on June 21 (Thursday) at 14:35 (UTC). You will be offered 6 problems 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 problems and 2 hours to solve them.

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 Mikhail awoo Piklyaev, Maksim Neon Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round.

Good luck!

UPD: Also great thanks to step_by_step, kevinsogo and nhho for help in round preparation and testing the round.

UPD2: The results table!

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 EricHuang2003 6 150
2 JerryKFC 6 151
3 Lovely_qgq 6 170
4 Meroeht 6 181
5 MYTH_vs_REALiTY 6 209

Congratulations to the best hackers:

Rank Competitor Hack Count
1 djm03178 30:-2
2 2014CAIS01 13:-3
3 quailty 5:-2
4 Harmonium_Wale 4:-2
5 kimden 2

110 successful hacks and 226 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A jh05013 0:01
B JerryKFC 0:02
C GrayGlobe 0:03
D T______________T 0:21
E NamikazeBoruto 0:11
F Counting_Stars 0:20

UPD3: Editorial

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

Comments Comments (240)
| Write comment?
»
6 years ago, # |
  Vote: I like it +24 Vote: I do not like it

Thanks for conducting another div3 round!! Looking forward for participation :)

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

    I love it when people downvote comments for no apparent reason. The community of codeforces is great :)

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

      You know sometimes I downvote some users comments even before reading the comment, I just cant stand those users :3

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

Why it's not in the homepage?

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

Can't be there some provision that people with rating(1600-1899 or maybe some lower) can also participate in div3(rated for them too) rounds with a totally different rank list i.e no cushioning for them and ensuring that ratings don't cross past 1899.

And as stated during announcement of div3 rounds problems will be easy for participants in the range 1600-1899,so it will be matter of just time.

OR

Maintaining a different rating graph can also be a way.

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

    I don't understand what the point of something like this would be. Maintaining two different rating graphs would be an enormous pain with very little payoff imo. If you really want to see how fast you can do it, just participate unofficially, it's not a big deal. Div 2 contestants get enough rated contests as it is.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it 
Div-3 rocks. I think you will add some critical test cases.
→ Reply
»
6 years ago, # |
  Vote: I like it -8 Vote: I do not like it

i do not like ACM_STYLE

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

I have doubt on using 20-min WA penalty for all ACM-ICPC style contests. Usually, the contests on Codeforces are length of around 2 hours and have 5-7 problems. But in ACM-ICPC contests, there are usually much more problems (10+) and they have long contest time (3+ hours).

Taking this mathmetically, let's say if a contestant A needs 5 more minutes than B to solve each problem. If they solve only 5 problems, A will get 75 more penalty than B, because every time you spent on the previous problems will affect the later solved problems' penalty. But when there are 10 problems, it becomes 275. In other words, it's proportional to the square of the number of problems. On the other hand, the penalty from the WAs would only increase linearly, as each wrong submissions have fixed penalty.

I'm not the only one thinking this way as I saw similar opinions on previous Div. 3 or Educational rounds too. I'm much like for having just 10-minute WA penalty for 2-hour contests, especially in a Div. 3 round, considering the accuracy of the official contestants would be quite low. How do you think about it?

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

    Strongly agree. It is really painful when get so many WAs in an educational round. Your rank will drop significantly. Codeforces can't just use ACM-ICPC rules without changing them according to their contests.

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

    MikeMirzayanov, you might wanna check this comment and tell us what you think about it :)

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

    Ya even codechef changed their cook off penalty to 10 min for same reason.

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

I tried to make strong tests

I smelled FST :(

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

I like the term Hacked other than Failed System Test

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

2 hours to solve, 12 hours to hack... That's why I love CF... And then you get a "time limit" on the main test... :|

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

Looking for more frequent div3 contests such that beginners like me can learn! :) Best of luck everyone.

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

Rated or not? Maybe a silly question for others:(

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

IIR?

(Abbreviation of Is It Rated? :P)
→ Reply
»
6 years ago, # |
  Vote: I like it -16 Vote: I do not like it
  1. Open Codeforces
  2. See a contest
  3. Checks contest starting time (worries might clash with Argentina's match)
  4. Checks contest length
  5. Gives contest peacefully.

PS- Thanks for not clashing it with Argentina Vs Croatia match.

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

A contest right after the senior high school entrance examination in China. Hope I will win the scores I lost these two days back as ratings.

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

    Make the most of yourself. You are still new and promising, no worries ;)

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

    Or rather, a contest right before we can see our scores.

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

my first div-3 contest. feeling excited!

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

Does hacking solutions increases points of the hacker?

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

the predictor isn't working !

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

What is the test case 4 of problem E

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

How to solve Problem E? I was using DSU + DFS, but was getting WA!!

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

    I did BFS + greedy

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

    I am just finding all connected components and print number of connected components-1 but keep getting WA on TC 4

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

    2 DFSs — keeping track of finish time.

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

      but what is wrong with my approach why is it not going to give correct answer

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

        3 1 1

        2 3

        Your answer = 2 (1 -> 2, 1 -> 3)

        Correct answer = 1 (1 -> 2)

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

    My idea : First, run dfs on capital vertex. While running dfs, make every path as bi-directional. Now build Strongly Connected Commponents. Count number of vertices which has 0 indegree expect the one containing capital vertex.

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

      I applied your method. Its giving wrong answer at test case #3.

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

        ummm :| I think you should read this

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

          Ok, I ran Dfs on capital vertex. While running DFS, i made bi-directional edge. (Thus every point reachable by capital can reach back to capital). Now i built strongly connected components.....(Correct me if i am wrong until this point). After that, my idea is to count all nodes with either indegree=0 or all strongly connected graphs with connected nodes more than 1.

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

            (Correct me if i am wrong until this point)

            As long as you use correct algorithm, (like tarjan's SCC or something) I think it would be fine.

            count all nodes with either indegree=0 or all strongly connected graphs with connected nodes more than 1.

            You can just count number of SCC vertices which has 0 indegree, but when counting, exclude a SCC vertex which contains the capital vertex.

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

    Kosaraju I think

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

      I used a similar idea but I didn't find the strongly connected components that Kosaraju does.

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

        What was your approach then?

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

          You run two DFSs. The first time you keep track of all the finishing times of the DFSs. Then run a DFS starting from the capital city. Then, while some cities are unvisited, keep starting a DFS from the unvisited city with the highest finish time, adding one each time we do.

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

          Its Kosaraju :P

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

            There's no transposing of the graph.

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

Last three problems were a little difficult for div3

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

That was a lot of fun! Thanks vovuh

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

What is wrong with test case 8 in D. Any strong test case?

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

how to solve E?

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

    I did it as follows : 1.)Mark all vertices that can be visited from s(by simple DFS). 2.)For rest of the vertices run DFS and count the number of nodes that can be visited by each of them.Sort according to the number of nodes visited by a particular vertex. 3.)Now run DFS from the last node in the sorted list and count the number of components left.

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

Was it only me who was facing problem to submit in the last 45 min?

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

For E, I removed all vertices that are reachable from s (excluding s itself), and then found the condensation of the new graph. The number of SCC's with indegree 0 (excluding the possible SCC that contains s and has indegree 0) is the answer. Is there a simpler way to do it?

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

    Is this approach wrong? 1. Find out the topological sort of the graph 2. run dfs for given s mark all visited 3. In the order of the toposort, run dfs and count components. 4. answer is components-1.

    Btw, if u find anything wrong, u are free to hack!!

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

      What about cycles in graph ?

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

        I'm marking visited, so cycles won't be a problem. Provide a test case if u find anything fishy

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

          I mean , how are you doing topological sort if the graph has cycles

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

          which algo you are using for topological sort kahns or ... because kahns need atleast one vertice with indegree=0 in starting

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

            I'm marking visited, and then not visiting a vertex if its already visited. Cycles will be handled automatically I guess. Sorry that I'm not able to comprehend what u are trying to say, so u may look at the code:-

            999E

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

              I had a similar idea. But I cannot convince myself that this approach works. Can you please help me?

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

                Topological sorting gives you an order of vertices along which if you run dfs, you will get connected components in a directed graph. Thereafter, the answer is simply numComponents — 1

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

    if you don't mind can you please elaborate this : "The number of SCC's with indegree 0(excluding the possible SCC that contains s and has indegree 0) is the answer"?

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

      Each vertex in the condensation graph corresponds to an SCC in the original graph. Look at the vertices in the condensation graph that have indegree 0: clearly they are not reachable from s. The other vertices, ones with indegree > 0 are reachable from some vertex with indegree 0. Therefore, we can add edges from s to the vertices with indegree 0, and then the entire graph is reachable from s.

      However, there is one corner case: when the vertex (in the condensation graph) containing s has indegree 0, we don't want to count it since a vertex is certainly reachable from itself. The second example input corresponds to this case.

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

        thanks for the reply !

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

        What about the case when all the SCC's(excluding the vertex s) form a cycle(i.e none of them have indegree 0) and the vertex s is disconnected from the whole graph ?

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

          In that case, the cycle will actually just be 1 SCC. And since s is not a part of the cycle, the answer will be 1.

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

    Let a[i] be equal to 1, if we need edge (s, i) in optimal answer. Then instead of SCC after removing all nodes reachable from s, launch dfs from every non-used node v and assign a[i] to 0 for all reachable nodes from v. After that assign a[v] to 1. We can do it, because instead of any edge (s, i) we can place edge (s, v) if i is reachable from v.

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

    For every vertex count the number of vertices that can be visited from there. Use dfs from start and then you can iterate through every of these vertices in decreasing order and just use dfs once again.

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

    Can you please share your code ? I am not able to view your submission for problem E.

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

how to solve D ?

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

    first put all the remainders with counts less than n/m in a set and then iterate on each index with value greater than n/m and for each of them find the closest element in the set and add the required value.

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

      Can you please explain a little more what you did. What do you mean by "and for each of them find the closest element in the set and add the required value."

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

        yes, sure. First put all the remainders with counts less than (n/m) into a set and then iterate over each remainder which have value greater than (n/m) (let's suppose we are currently at 'i') and notice one thing we have to only move forward so, the best we can do is to conver current 'i' to it's nearest remainder having value less than (n/m) and so just do a binary search for that and find that index.(set's lower_bound will help you). Now, it may happen that we are at 'i' and there are no index in range [i, m-1] having value less than (n/m) so, in that case we have to search for the same from front.

        Hope it helps!

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

          Yes, Your comment made it very clear. Thank you :)

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

          Why should we convert "i" to the nearest remainder having value less than (n/m)? Can't we covert it to any remainder having value less than (n/m)?

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

            because it may happen that some of the remainders before it (nearer to the current one) has a value greater than (n/m) and so, if we convert that then we have to pay less.

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

              Anyway, all remainders have to be filled equally. So if we convert "i" to its nearest one, then there may be some "j" which needs to travel farther and satisfy the next remainder. Else, if "i" already travelled farther and satisfied the second remainder, then "j" will just have to satisfy the nearest (first) encountered remainder. Both ways seem the same to me. Am I going wrong somewhere? If yes, please explain with a small counter case.

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

                you forget that we can only move right!

                let's aarray be 3 1 4 1 1 and we have to make all 2's.

                Then if we add 3's 1 to the 4th position (instead of nearest 2nd) then we have to take the 4's 1 to the 2nd position in which we have a total cost of (3 + 2 + 4) instead of the optimal cost which is (1 + 1 + 2).

                Hope it makes your doubt clear.

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

      i thought abt it..but don't u thnk it's complexity will be O(n*n/4)??

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

        see there are atmost 'n — m' elements that are greater than n/m and similarly 'n-m' indexes are there which have less than value n/m. So, we are inserting 'n — m' elements and for each of 'n-m' element we are doing a binary search. so, O(NlogN)

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

    Consider every reminder c[i] a container that can hold at max n/m numbers. As you read the input you put a[i] in the container c[ a[i] % m ], if it's full: you put it in the next available container and add to a[i] the number of steps. To do it quickly the next available container is registered in another array.

    Let me know if that makes sense.

    EDIT: An array to store the next available container isn't good enough, a set is needed.

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

      Hey there! I am also very stuck on this problem and your solution is not making sense to me. I have some questions, hope you will answer.

      -- If C[ a[] % m ] is full, how do you decide the next bucket in the container? Why do you add a[i] number of steps?

      -- At the end how do you track what the final array is?

      Thanks

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

        This is the code if you couldn't find it 39498091.

        -I decide the next bucket by lower_bound(a[i] % m) in a set of buckets, every time a bucket is full I erase it

        -I add to a[i] the difference between the buckets, which is how many times I have to increase it

        -The final array is the original one that I changed every time

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

How to solve F?

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

    Consider any single number of card. Now the problem is 'For given N cards and M people, each person can have at most k cards. What is the maximum score?'

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

      orange4glace, Sorry, I didn't get. Can you please elaborate more, what's the intuition behind solving problem F with an example?

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

        Since h is strictly increasing, it is optimal to distribute as much as favorite cards to each peraon. eg. Let 3 people likes card 1 and each person has 2 cards. If number of card 1 is greater than or equal to 3×2, just distribute 2 cards for each and leftovers are 'dont care'(any other will have it and it has no effect to score) Else if the number of cards is less than 3×2, now the problem is distribute m cards to 3 people while maximum the score

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

can anyone help me how to solve problem D????

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

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

Help on E appreciated, please let me know what's wrong with this approach (which fails pretest 4):

  • Mark all vertices that are reachable from the capital (via DFS);
  • For any vertices not reachable from the capital, count (via DFS) the number of child vertices that are still not reachable from the capital, and put them in a priority queue sorted in decreasing number of children;
  • Greedily add an edge from the capital to the first vertex in the priority queue, and mark (via DFS) vertices that are now reachable from the capital, removing them from the priority queue;
  • Repeat the previous step until the priority queue is empty.

Thanks a lot for any insight!

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

    When you remove the first element of the priority queue along with all of its childs it is possible that you change the degrees of some of the vertices that are still going to stay in the queue.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    check this test
8 7 1
2 3
2 4
2 5
2 6
7 4
7 5
8 7

the answer is 2
in your approach the answer will be 3 as i think ,is it ?
    → Reply
»
6 years ago, # |
  Vote: I like it +27 Vote: I do not like it

I don't think it's OK to have contests in which almost all participants solve the first X problems, but then only a small percentage of them solve the (X + 1)th problem. The difficulty distribution seemed a little off for this round.

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

    As usual for Div.3 rounds

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

    Totally agree. There are about 2000 participants (ranked ~#500-#2500) solved exactly 3 problems.

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

    I dont think its optimal but I dont think its unacceptable either.

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

Any miniature version of test 4 of E?

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

    This test is just a complete directed graph with a 71 vertices and n * (n — 1) edges.

    UPD: Woops, the fifth test was a complete graph. I was wrong. The fourth test is a just random directed graph with an 5000 vertices and 5000 edges.

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

      vovuh Can you please tell will there be editorials for this round. They are not on home page.

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

        The editorial will be available in few minutes =) Sorry for delay, i was on the exam today

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

Can someone tell why 39491266 gives WA but 39491559 gives RE for problem D.

I only changed all "int" to "long long".

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

    maybe something overflowed and when you took the remainder you got a negative value, which then caused you to look at a negative entry of an array?

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

I had been debugging my solution D(39490746) for half an hour. When the contest is over and I saw the test case, I realized the result is long long. So it(39494662)passed...

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

I rage quited after 3WA's in E and D
After the contest I checked my E again and Saw this:

""Diagnostics detected issues [cpp.clang++-diagnose]: p71.cpp:92:12: runtime error: index 5000 out of bounds for type 'int [5000]'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior p71.cpp:92:12 in""

I wish I would have checked my array sizes rather than rage quieting cf after 3WA's
and also wish codeforces will give RTE verdict rather than WA for these :p

Nice Problems Overall :D

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

Contest was not beautiful as its id.

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

How MYTH_vs_REALiTY solved all tasks in an hour ?

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

So, this was my first contest on Codeforces and I can't seem to find any ROOM link on the top menu bar nor can I find a way to lock my submissions so that I can participate in hacking. Do first time users don't have this privilege of hacking or am I missing something?

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

Thank vovuh for your contest, it was more difficult than last div 3 round.

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

    Funny, it seemed simpler to me! BTW, I found the last div 3 round more difficult than some div 2 (not that I have much experience, however)

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

I solved only 4 problems and its my first constest, my rank will go up or down?

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

Why My code for D getting runtime error on test 8 ?

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

In problem D i used a queue to store the number remainders . If the size of the remainders > n/m then we move one by one to the next container with the value (previous + 1). And keep doing that until everything is equal to n/m (only 1 needed 1 for) and traces and etc, why am i getting TLE ? and how can i fix this or maybe another approach ? Code : https://ideone.com/Z6Y8I5

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

    It seems to me like you have nested for loops. Oouter loops iterates until m and inner loop iterates until trace[i], which (at least at first glance) seems like it could be O(n). So overall complexity would be O(n^2)?

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

      ah okay i think i get it, so is there anyway to optimize it because i cant find a way to trace the answer

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

        You can use something like dsu (I don't know the name for this technique) so every remainder >= n/m won't be visited again

        http://mirror.codeforces.com/contest/999/submission/39476990

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

          Correct me if I am wrong but I think your solution has quadratic complexity as well. If n = m, then the only stop condition of your cari function is that val[x] is 0. So For a case like:

          200000 200000
200000 199999 199998 199997 ...

          When processing the first number you'll take 1 step, when processing the 2nd number you'll take 2 steps etc. So overalall you'll take N*(N+1)/2 steps.

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

            Isn't the answer for that tc is 0 change? My val[x] is only incremented after I found the valid position for current number, so cari will only be called once for each number (Because val[x] is still 0)

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

              Sorry, I didn't notice you actually modify the nex array (also the test I wanted to type was an array full of zeroes, but it doesn't matter anyway).

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

          Nice technique bro thanks, i finally understand your code!

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

can someone help me to find out why the first solution was not accepted but second got accepted for problem B

http://mirror.codeforces.com/contest/999/submission/39483346

http://mirror.codeforces.com/contest/999/submission/39486399

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

    It is not advisable to insert characters in C++ string like this s[i]=ch. You are allowed to do this in character array string.

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

      Really? So... how did you do it in your solution?

      Are both of you joking?

      Maybe I miss something but...isn't the problem with s1[r--] operation? These parts of code aren't the same, of course:

      s1[r--]=s[i];

      compare with

      s1[r] = s[i];
r--;

      Doing something with s1[-1] and s1[0] aren't the same.

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

        changing s1[r--]=s[i] to s1[r]=s[i] doesn't make any difference. Still runtime error in testcase 8.

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

          Oh, sorry. I was a little tired yesterday. aditya10 is right. Little more: string is an object. When you initialise "string s1;" constructor make it s1 = "".

          So, when you write "s1[r] = s[i]" you just change the element with address s.begin() + r (not s1). And... we don't no, what the rubbish is there. When you are trying to change it, you can get an error.

          When you print the s1 itself (cout << s1), you see that it doesn't change. s1 = "".

          So...just initialize "s1 = s;". Now it has got the same number of elements as s, and all will be ok.

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

        Doing s1[r--]=s[i]; and s1[r]=s[i];r--; are actually same. In post decrement value is decremented after being initialized.

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

Regarding question D

I wrote the code using lower_bound(st.begin(), st.end(), t) and got TLE but when i wrote the same code using st.lower_bound(t) it got AC. Why this happened???

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

A, B, C was too easy and C, D, E was too hard. So the standings will probably depend on penalties.

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

    ""A, B, C was too easy and C, D, E"" i geuss you meant F D E and thats actually true , they are harder than most B's in div 2

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

I just realized I really need to practice to be a better coder.. I got the idea of d but struggled alot coding it and didn't have the time to solve it because of some annoying coding mistakes :(

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

Why my solution for problem C is exceeding the time limit in testcase#5 despite having linear complexity? here is the link: http://mirror.codeforces.com/contest/999/submission/39496135

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

    I assume that anss=s[n-1-i]+anss; may be O(N).

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

    Because it doesn't have linear complexity :)

    The + operator for strings (from line anss=s[n-1-i]+anss;) is not constant time, but linear (see documentation). Considering the outer for loop as well, it results in quadratic time complexity.

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

Hello! Can someone help me with Problem D? I saw the comment, but I do not understand it. Will appreciate if someone can explain the idea and how you reached it.

For Problem D, I did a BFS from the initial array until one array suceeds. This I feel is correct, but I had a memory limit exceeded within test 5.

Thanks

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

Hack for Problem C?

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

Can D be solved using two pointers ?

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

    I think its possible if you first sort the entries of the array in increasing value of the remainder mod m.

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

What is the effect on rating after hacking others solution in this round?

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

    Hacking that take place after contest have no effect on rank (for hacker). So no effect on rating.

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

can someone explain the idea of F?

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

    For a fixed type of cards you have x cards and c players that them likes this type, so compute the dp[i][j](maximum value that you can get) where i is the number of remaining players and j is the number of remaining cards initially dp[c][x]=0 and the answer will be in dp[0][0..x] I leave the link to my solution for a better understand of this idea: 39504913

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

Can someone explain question F to me? I've read it thrice but I do not understand.

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

My solution for D: 39490456.

I believe my answer is just a permutation of the correct answer ( 4 2 1 6 11 12 ). Should this not get accepted considering any array satisfying the required condition is correct?

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

    The only operation you can do is incrementing an array element, changing order is not allowed.

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

vovuh please check my submission for B it is not showing output on codeforces while the same is giving correct answer in my ide. This took my 40 mins. here is the code-!! :( Anyone having idea of this? Thanks for your insight!

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

    You can't use scanf/printf with ios_base::sync_with_stdio(false); You can read this blog (look for comments)

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

      Thank You! :)

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

      Actually, that's only half true. What you shouldn't do is MIXING either scanf/cin or printf/cout in the same code (since different streams aren't synchronized, there's no guarantee what will be read or written first). Otherwise, using only one from each pair is usually safe.

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

        U mean scanf and cout or printf and cin? Right?

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

Problems A, B, C vs problems D, E, F

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

    But really why was it like this? 100 participants with a full mark and almost all others with only three questions... Then the one who just codes faster, gets a better result. Is it a marathon or a contest???

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

Newbie here! Can anyone explain why I got TLE on problem C?? Problem C submission

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

    The time complexity of your solution is O(n^3). It can be solved with much better time complexity. Link : My solution

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

My solution for D: http://mirror.codeforces.com/contest/999/submission/39505442. I think it's O(n) ?

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

    can you please explain your approach?

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

    Last two for loops where each runs m times, contain a while loop. Can you explain how its complexity is still O(max(n,m)).

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

      each for loop runs m times, each while loop runs maximum n / m times => I think total complexity is O(m * n / m) = O(n) ?

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

        If we look at while loop independently, it will run the number of times equal to number of elements not "in place". So say all elements have same reminder, the while loop might run, roughly speaking, O(n*n/2) times. Still I am not sure, what do you think about it?

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

          int d = n / m;

          int need = d — v[i].size();

          => need <= d

          => need <= n / m

          while(need--) => each while loop runs atmost need times or n / m times.

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

Can anyone figure out the mistake in this solution for E? LINK

For tc #4, it is computing 1818 as the answer instead of 1817.

Approach : Run a dfs from source and mark all reachable nodes. Now, run a dfs from every unreachable node and mark all the ones that are being traversed from some parent. Suppose, we're running dfs from 2, we will mark every node reachable from 2 as visited, but we'll keep 2 as unvisited. This way, we will know the nodes(and components) which require a path from source.

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

    What if while running the second DFS you reach a node marked by the first DFS. What do you do?

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

      I'm ignoring it, because the nodes which can be reached from this node would've already been marked.

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

      I am facing the same problem. And does it matter that after running second dfs if we come across the visited nodes from the first dfs,as they are already visited and reachable from s.

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

    Check for this test case 5 4 5 1 2 2 3 3 1 4 3

    Correct Output: 1

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

Why is this http://mirror.codeforces.com/contest/999/submission/39505722 submission of mine for A giving WA on this case: 6 6 7 1 1 1 1 1 The answer is actually 5, but in cf it is showing 4. But in ideone compiler it is giving right answer. Link: https://ideone.com/je07LC

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

why rating is not updated yet?

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

did all the testcases are run or some testcases are yet to be judged during system testing

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

Is the system testing done? If not, when?

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

Can't believe that i have solved 5 problems!

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

For some reason 999F reminds me of game theory/mechanism design about auctions, when I first look at the joy level constraint I thought "oh this is a gross substitute valuation" instead of "oh it's strictly increasing"... Weird.

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

System testing has started now.

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

.

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

It would be great if someone can put editorial's link here. Thanks in advance.

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

I got TLE in Java for problem C and I got very confused about my logic. But then I researched a little more and I wrote this for Java programmers:

https://letsdocp.wordpress.com/2018/06/22/java-in-competitive-programming/

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

I am getting MLE in problem-D test-5 here. I have made vector and map of linear order.Anyone help ?

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

    I guess vectors do not release memory after popping up the elements. I used stack in your code hereinstead of vector and it shows TLE. The underlying approach is wrong.

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

all those who got stuck on test 4 of problem E can try this test case no 47: 8 8 1 3 2 3 4 4 5 5 3 6 4 6 7 7 8 8 6 ans:1 you might be getting 2...

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

UPD: I got the mistake

In E, for test case 20, I get answer as 11, whereas the solution ans is 12. I even added the edges and put asserts to check that every node is indeed reachable from s, however I did not get any assert failures. Someone please point out what's going wrong with my solution, thanks! 39515068

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

    i think you were first doing dfs of capital node and then for every non visited node ,finding all other nodes from where you can reach to that node ,by backtracking the reverse adjacent vector and doing dfs on all back nodes....

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

      I'm not sure about that. The mistake here was I added edges as bidirectional from input, but it actually has way more issues :P

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

    How to solve E?

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

      First check for every vertex 'a' how much vertices can go to 'a'. Then sort vertexes by sizes of groups. Notice that for every group you only need to add one road for all vertices in group to be connected to root. Iterate groups from biggest to lowest, check if road exist before you add one. If you add one road, notice that you made all vertices that belongs to the group connect to root. If they are connected, you shouldn't build roads because they're already connected.

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

      If you have for example root: 1 2->3 2->1 4->3 First sort groups (3 will be first, then 1 and 4)

      You add one road (3->1) and then 4 becomes connected. Next up is 4, but 4 is connected trough 3 so we move on. Next up is 2, but 2 is also connected to root.

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

I need help, even though my solution for test 1 was right, it gives WA on problem D. Here's the submission. Mine code outputs: 3 0 2 3 8 10 13 their answer: 3 0 2 3 7 10 14

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

    Input:

    6 3
3 2 0 6 10 12

    Your Answer:

    3
13 8 0 3 10 2

    You can just increase elements by 1, you can't change the order.

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

I am getting WA at test# 4.

I tried Solving E: 1. Did the DFS on s, marked nodes visited. 2. initialized c = 0(counter: for counting connected components in Graph), then started running DFS on every node except S, forwardly(means when in the edges direction) and then took a step backwards(means run the loop to iterate over all the node which is pointing towards current node, for, eg, if 2 is current node and there is an edge 4->2, then I went back to 4.) and obviously marked the nodes visited. 3. then counted all the connected components.

here is my link: http://mirror.codeforces.com/contest/999/submission/39517716

Actually, my idea was simply to have the no of connected components fo graph. can someone please point out the mistake??

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

    Your Solution Will have no of Connected Components in Undirected Graph But in The Problem The Graph is Directed.

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

Since the system testing is done and my solution for E passed the tests,though i still don't know if its correct.

My solution:Find all the cities not reachable from capital and add a directed edge from capital to it.Now for all newly added edges just remove that edge and check if its possible to reach all cities from capital.If yes, then just remove that edge and continue checking for other edges,else add that edge back and continue checking.

I don't know how to prove that this gives the optimal answer.Can someone prove it or give some counter test for this?

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

    We know that an optimal solution is given by the following algorithm: for every SCC with in-degree zero, add an edge from the capital to some arbitrary node from that SCC.

    It is obvious that the edges your solution provides includes a set of edges that can be generated by the algorithm above (in other words, your solution does add an edge from the capital to every SCC with in-degree zero).

    What's left to prove is that your solution does not add any extra edges. Let's suppose via reductio ad absurdum that such an edge is added. Since it is an "extra" edge, it can fall into one of the following two categories:

    1) An edge from the capital to some SCC with non-zero in-degree. 2) An edge from the capital to some SCC where such an edge was already added.

    For case 1, that SCC is still reachable without this edge, so by definition your algorithm will have removed it, therefore it is impossible to have this kind of edge in the end.

    For case 2, since an edge was already added to this SCC, it means that its in-degree is now non-zero, therefore it can be reduced to case 1.

    We can conclude that your algorithm can not produce any extra edges, therefore your solution is optimal.

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

What is the solution of problem D????

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

    For every a[i] (if number of a[i]%m is greater than n/m) find nearest x (0<=x<m) which is greater a[i]%m and number of x in array a[] is less than n/m and increment a[i] by (x-a[i]%m)

    check my solution for more details

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

I got WA test 8 problem D, I used set and binary search but I still don't know what is going wrong? Here is my code

EDIT: Oops, fixed it!.

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

editorial?

→ Reply