When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

Monogon's blog

By Monogon, history, 3 years ago, In English

omg hi!

I will add implementations soon.

UPD: Implementations are added

1504A - Дежавю

Tutorial

Implementation

1504B - Меняем биты

Tutorial

Implementation

1504C - Сбалансируйте биты

Tutorial

Implementation

1504D - 3-раскраска

Tutorial

Implementation

1504E - Задача коммивояжёра

Tutorial

Implementation 1

Implementation 2

1504F - Переверните карты

Tutorial

Implementation

1503E - 2-раскраска

Tutorial

Implementation

1503F - Сбалансируйте карты

Tutorial

Implementation

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

| Write comment?
»
3 years ago, # |
  Vote: I like it +15 Vote: I do not like it

omg hi!

»
3 years ago, # |
  Vote: I like it -40 Vote: I do not like it

imagine figuring that C out

»
3 years ago, # |
  Vote: I like it -13 Vote: I do not like it

Is there a proof to solution of C?

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

    After adding brackets for positions where $$$s = 1$$$ you can observe that when you add a new pair of alternating brackets your balance will never be lower than zero after putting the first bracket and it will come back to the original balance after putting the second one.

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

      Yes, that 'balance' thing is really nice way to approach.
      But could you please explain the part where we fill first $$$\frac{k}{2}$$$ 1's with opening brackets and the rest with closing?

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

    Imagine a 2d plane where (x,y) = (no. of unclosed open brackets in first sequence, no. of unclosed open brackets in second sequence). We can then map the 4 possible moves:

    -> adding a '(' to first string when s[i]=1 => we go from x,y to x+1,y+1

    -> adding a '(' to first string when s[i]=0 => we go from x,y to x+1,y-1

    .. and similarly for adding ')' in both cases, we get opposite moves.

    We start at origin, and our objective is to return to the origin after n moves without crossing any of the axes. If you draw it out on paper or something, it will be clear that by following the given strategy, we either stay on the x = y line or x = y + 1 line, and dont cross any of the axes, unless the string begins or ends with a 0.

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

      Wow! This approach is really interesting. Thank You!

      Your explanation is truly fantastic, I tried to rebuild it on my own, and it's super amazing!

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

      Nice visualization. Helpful. Thanks!

»
3 years ago, # |
Rev. 2   Vote: I like it +184 Vote: I do not like it

Me : *trying to push monogon contribution to moon
Monogon : *making greedy problems that shove my rating into dirt

*sad cat noises

»
3 years ago, # |
  Vote: I like it -30 Vote: I do not like it

E is a good problem! I'm so close :(

»
3 years ago, # |
  Vote: I like it +65 Vote: I do not like it

Constructiveforces.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Sry,I went to the wrong place ,I come back to div3 immediately TAT

»
3 years ago, # |
  Vote: I like it -13 Vote: I do not like it

Wow!! Fast editorials really helps. Thanks.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In E's solution 1 why only need to add i-> j+1? (i.e. don't need i->j+2....)

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

    it's at least as cheap to go i->j+1->j+2 as i->j+2 because you get to subtract $$$c_{j+1}$$$. There's always a path from j+1 to j+2 because of either edge 3 or a combination of the edges from 1 and 2.

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

    It can be proved that $$$cost(i,j+2)\ge cost(i,j+1)+cost(j+1,j+2)$$$. The following is the proof. Since $$$a_i$$$ is increasing and $$$cost(i,j+1)=a_{j+1}-a_i-c_i$$$, therefore $$$cost(i,j+2)=a_{j+2}-a_i-c_i$$$. So $$$cost(i,j+2)-cost(i,j+1)=a_{j+2}-a_{j+1}\ge \max(0,a_{j+2}-a_{j+1}-c_{j+1})=cost(j+1,j+2)$$$. Therefore, $$$cost(i,j+2)\ge cost(i,j+1)+cost(j+1,j+2)$$$, so we needn't add $$$i\ \rightarrow j+2$$$.

»
3 years ago, # |
  Vote: I like it -13 Vote: I do not like it

omg hi cyan

»
3 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Can anyone proof solution of problem Div.2 D?

»
3 years ago, # |
  Vote: I like it -13 Vote: I do not like it

damn, I was correct for E. Just 10 min left to implement so couldn't implement in time. I wish I didn't cost much time at B

»
3 years ago, # |
  Vote: I like it -18 Vote: I do not like it
»
3 years ago, # |
  Vote: I like it -27 Vote: I do not like it

Pretest for div2B was very weak. Don't know why my O(n) solution exceeded the time limit 111887915

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

    Your code is O(n^2) in the worst case since you are doing string z = b + z

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

    You should probably look up what weak pretest means before commenting.

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

      Sorry for my bad statement. But my solution passed the pretest with O(n*n) approach. And then failed the system tests.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Great problem set!!! 1-gon orz

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Glad that Div2C, D, and E all passed in python3 even without pypy3!

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

one of the greatest contest i have ever partipicated in . thanks to the author. Waiting soon for ur next contest

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If anyone wants to see how I overkilled 1C with 2 segment trees and coordinate compression and then forgot to sort wrt $$$a[]$$$ and couldn't get AC in contest : 111939130

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

Sorry I am stupid but can you elaborate div1C solution 2's formula

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

    python: 111931953

    C++: 111890876

    Essentially each city must have an outgoing cost of its floor. Additionally, we're going to need to pay the cost max(a) — min(a). However, if we use a sequence of cities to go from min(a) to max(a), we can use the floors to "pay" for max(a) — min(a). In other words, we only need to pay for the parts of the segment from min(a) to max(a) that aren't already paid for by the floors of the cities along the way.

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

      I mean I can understand the dijkstra one and everything before, but I can't understand why the formula in solution 2 is true.

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

    I think its missing the sum of c , otherwise it should be correct . the summation in the editorial is counting how much extra cost we have to pay to reach i if we can jump from any city j with j<i which is $$$(a_{i} - a_{j}) - c_{j}$$$

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

    I didn't understand either. I think the wording is kind of confusing.

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

      The formula is $$$max(0,a_j-a_i-c_i)$$$. There are two cases. If $$$a_j>a_i+c_i$$$ then $$$a_j+c_j$$$ must update the greatest value. Otherwise $$$max(0,a_j-a_i-c_i)=0$$$ and it won't contribute to the answer.

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 5   Vote: I like it +75 Vote: I do not like it

      I think we actually need a detailed analysis to justify the formula. Maybe I am just not that good for having the intuition, though.

      Here is the analysis, consider constructing the path from a1:

      Lemma 1. Consider without max(0,), it is always beneficial for us to break one step into two steps.

      proof: two step cost is a[3]-a[2]-c[2] + a[2]-a[1]-c[1], one step cost is a[3]-a[1]-c[1], since c[2]>0 the two step cost is better.

      Now add max(0,) back, so sometimes breaking steps are useless (but never worse).

      Lemma 2. To reach the i-th block, the one step with minimum cost is from j with max a[j]+c[j] before.

      proof: I am not considering the steps before j but only this step, this should be trivial.

      Now let's call this maximum a[j]+c[j] "premax". (prefix max)

      Lemma 3. If we reach some i such that a[i]>premax, than a[i]+c[i] becomes new premax in the next iteration. Let's call such i "breakpoint". Also note that when reaching a breakpoint, the cost>0 so max(0,) is useless and thus we can apply Lemma 1 later.

      proof: Because c[i]>0. So a[i]+c[i]>a[i]>premax.

      Combine these all, we would obtain the strategy. Strategy:

      Suppose we are standing at some certain block, then we can keep going right and update premax with zero cost until we reach a breakpoint. Then because of Lemma 1 we should make a step to the breakpoint, and because of Lemma 2 we should go from the premax we've found. Because of Lemma 3, paths like this won't happen: i -> j -> i -> k (where a[i]+c[i] is the premax for both j and k) since j would be the premax for k. So we won't need to step on a premax twice, which allows us to reconstruct a Hamiltonian Cycle later. Thallium54 Although not rigorous, hope this helps.

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

        Lemma 1 is important. Thanks for the explanation.

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

      I think this is the reasoning behind the formula: we want to get from $$$a_1$$$ to $$$a_n$$$ in a number of steps, with the minimum cost. If these steps are $$$s_1, s_2, ... s_k$$$, with $$$s_1 < s_2 < ... < s_k$$$ ($$$s_1 = 1$$$ and $$$s_k = n$$$), then the path will be $$$a_{s_1}, a_{s_2}, a_{s_3}, ..., a_{s_k}$$$. So the $$$a_i$$$ not included in the step series will be the nodes on the path from $$$a_n$$$ to $$$a_1$$$.

      In the summation, I found it a bit easier to do it backwards (from $$$n$$$ to $$$1$$$, the final answer will remain the same): so, firstly, we want to see from which node $$$a_j$$$ we get the best cost from $$$a_j$$$ to $$$a_n$$$ and, as the editorial shows, it's the $$$j$$$ with the maximum $$$\max(a_j+c_j)$$$. So this $$$j$$$ will be the the step $$$s_{k-1}$$$. Then, when we have $$$i = j$$$, we update the $$$j$$$ index for the next best $$$\max(a_j+c_j)$$$ and this new $$$j$$$ will be $$$s_{k-2}$$$.

      We repeat this process until we reach $$$i = 1$$$, when we know for certain that we have calculated the whole step series (because then we just get that $$$s_1 = 1$$$, which we already knew). So basically we construct the path from $$$a_1$$$ to $$$a_n$$$ edge by edge, the only difference between my explanation and the editorial being the order in which we construct the step series. The $$$i$$$ indexes for which we have $$$a_i-\max_{j<i}(a_j+c_j) \leq{0}$$$ will belong to the path from $$$a_n$$$ to $$$a_1$$$.

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

      All the proofs above are extremely cool and clear up the whole idea. Colin's stream has also a similar proof. I got it from there. Folks can see there too if they are still unsure.

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

    I guess I'll also put my proof here, since I've been thinking about it for a while.

    The problem is the following: you are given a weighted directed graph with $$$n$$$ vertices (numbered from $$$1$$$ to $$$n$$$). The $$$i$$$th vertex has outgoing edges to all vertices $$$j < i$$$ with weight $$$0$$$, and outgoing edges to all vertices $$$j > i$$$ with weight $$$\max(0, a_j - a_i - c_i)$$$. What is the weight of the shortest path from vertex $$$1$$$ to $$$n$$$, plus $$$\sum c_i$$$?

    This problem is equivalent to the original problem, because any path from vertex $$$1$$$ to $$$n$$$ in this problem can be turned into a tour in the original problem with the same cost: simply follow the same cities along the shortest path from $$$1$$$ to $$$n$$$, and then visit all unvisited cities (plus city $$$1$$$ to complete the tour), in decreasing order. Furthermore, the weight of the shortest path from vertex $$$1$$$ to $$$n$$$ is a lower bound for the answer in the original problem, since some path from city $$$1$$$ to $$$n$$$ must exist in the tour.

    To find the weight of the shortest path from $$$1$$$ to $$$n$$$ in the new problem, define $$$dp[i] := \max(0, a_i - \max\limits_{j < i}(a_j + c_j))$$$ for $$$1 < i \leq n$$$ (same expression as in the editorial) and $$$dp[i] := 0$$$ for $$$i = 1$$$. Let's prove that the weight of the shortest path from $$$1$$$ to $$$n$$$ is equal to $$$\sum\limits_{i = 1}^{n} dp[i]$$$ using induction from $$$1$$$ to $$$n$$$.

    Our inductive hypothesis is the following: suppose we're at step $$$k$$$; then for all $$$1 \leq j \leq k$$$, the weight of the shortest path from vertex $$$1$$$ to $$$j$$$ in the subgraph containing the first $$$j$$$ vertices is equal to $$$\sum\limits_{i = 1}^{j} dp[i]$$$.

    This is true for $$$k = 1$$$, because the weight of the shortest path from vertex $$$1$$$ to $$$1$$$ in the subgraph containing one lonely vertex is $$$dp[1] = 0$$$.

    Now suppose we're at step $$$1 < k < n$$$ and that the inductive hypothesis is true for $$$k$$$; let's show that the inductive hypothesis is true for $$$k + 1$$$. There must exist some last directed edge $$$(u \rightarrow k + 1)$$$ in some shortest path from $$$1$$$ to $$$k + 1$$$.

    Firstly, let's show that all previous shortest paths don't change by adding vertex $$$k + 1$$$ to the subgraph. Suppose that there exists some $$$1 \leq j \leq k$$$ such that the shortest path from $$$1$$$ to $$$j$$$ decreases by adding this new vertex. Then one such new path must be a concatenation of some shortest path from $$$1$$$ to $$$u$$$ (in the subgraph containing the first $$$k$$$ vertices), plus the edge $$$(u \rightarrow k + 1)$$$, and then the edge $$$(k + 1 \rightarrow j)$$$. If $$$j \leq u$$$, then the previously computed shortest path from $$$1$$$ to $$$j$$$ must have been at least as good, since prefixes of $$$dp$$$ are monotonically increasing. If $$$j > u$$$, then the concatenation of the shortest path from $$$1$$$ to $$$u$$$, plus the edge $$$(u \rightarrow j)$$$, is at least as good, because the weight of the edge $$$(u \rightarrow j)$$$ is less than or equal to the weight of the edge $$$(u \rightarrow k + 1)$$$. Either way, there is a contradiction.

    Now let's show that the weight of the shortest path from $$$1$$$ to $$$k + 1$$$ in the subgraph containing the first $$$k + 1$$$ vertices is equal to $$$\sum\limits_{i = 1}^{k + 1} dp[i]$$$.

    Welp, my tablet pen clicked outside of the comment box, so I lost a bunch of work... Just gonna give up here... In short, the idea is the following: let $$$j$$$ be the greatest index such that $$$dp[j] > 0$$$, or $$$j := 1$$$ if no such index exists. Then it must be true that $$$u \geq j$$$. Since all prefixes past $$$j$$$ are the same, it doesn't matter from which one we transition from. So we can just choose the index $$$j \leq i \leq k$$$ with the maximum $$$a_i + c_i$$$ value, and transition from that. Turns out, the maximum $$$a_i + c_i$$$ value in general (for $$$i < k + 1$$$) must lie in that range.

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

    After reading the explanations here, I was able to understand a bit more about the formal-"why does it work", but I still had not intuitive-"why does is work". After sleeping and thinking and trying, what finally helped me understand it, in the editorial we have this implementation:

        sort(ve.begin(), ve.end());
        long long mx = ve[0].first + ve[0].second;
        for(int i = 1; i < n; i++) {
            ans += max(0LL, ve[i].first - mx);
            mx = max(mx, ve[i].first + ve[i].second);
        }
    

    I didn't get how this works, and why this works. I made another implementation for myself.

        sort(ve.begin(), ve.end());
        long long mx = ve[0].first + ve[0].second;
        for(int i = 1; i < n; i++) {
            if(ve[i].first + ve[i].second >= mx) {
                ans += max(0LL, ve[i].first - mx);
                mx = ve[i].first + ve[i].second;
            }
        }
    

    It is pretty much the same... I added an if-statement and removed the max(mx, ...) from calculating mx. But it changes one thing, which helped me understand this. The summation to sum is more explicit. We only add something, if we can improve our mx. This means we check each city from the ugliest city to the most beautiful one and always enter a city if we can improve our mx. The algorithm is 100% greedy now.

    It's also the same as in the editorial. ve[i].first - mx > 0 implies ve[i].first + ve[i]second > mx. So we also only add when we can improve mx.

    I have no prove why this works, but this helped me on the "intuition"-part, why it should work.

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

      You can see my comment for the proof. I agree that my explanation makes the solution not intuitive.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

B was so hard for me:( i'm solve it after 1 hour.

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

    How many hours do you code per day bro? Your graph is scary

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

Those who solved div2C,how do you guys think of that solution?

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

    This was my approach during the contest.

    The first and last char should be 1 because if it is 0 at any of these positions then the string can't be complete {i.e they will look like (...( and (...) }. For the answer to exist, the count of 1 and 0 should be even (self explanatory) and the prefix sum in both the string should be >=0 at any index, if we give +1 for character being '1' and -1 for being '0' and total sum should be 0. (just like we do in checking balanced parenthesis).

    For finding the strings: For index with val = 1, put '(' for half the times and ')' for other half. {Eg- If the string is 11100111, then both the strings will be initialized by (((00))) } For index with val = 0, start with ( and alter for rest of the indices for the 1st string and for obtaining the 2nd string, start with ) and then alter. {Eg — If the string is 1001000011, then x = 1()1()()11, y = 1)(1)()(11 and one can be substituted by the above method }

    If you carefully observe, this procedure basically leads to prefix sum >= 0 at every index.

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

    uh.. I am not satisfied with the solution.. probably because I couldn't come up with a convincing proof..

    To add on that I thought that perhaps the editorial would have some mention of proof (up to the part of even number of zeroes it is fine)

    but it seems the construction just works in favour over any other possible construction you can manage to do..

    So you can do some drawing on paper and see that you want to keep the stuff as close to 0 otherwise the bracket sequences will diverge and I guess that's closest to what can be called a proof.

    (What hasn't been mentioned though that the prefix sum criteria is usually followed with this construction i.e prefix sum >= 0 except for 1 — 2 cases, the only thing which needs to be taken care of is to get a final sum of 0 and this construction works in favour of it)

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

While I figured out the first two observations mentioned in C's editorial, how do I arrive at the idea to populate the first k/2 1's with '(' and the last k/2 1's with ')' and then alternate the 0-positions?

Does anyone have any advice on what I need to think about or ask myself, to reach this idea?

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

    Since the string must always end with a '1' and start with a '1', all '0's will be sandwiched by '1's, so it would look like ((( ()()() ))) and ((( )()()( ))). The net number of '('s is simply carried forward by the ()()() or )()()(. hope this tells you something new...

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

      I see, so the idea that the 0's in the input string will have zero long-term effect on the running sum if they're alternating, allows me to handle the 1's separately and then just fill in the 0's with alternate brackets.

      Had I thought of input strings like 110011 or 1111000011 then this may have struck me, but I got confused with imagining inputs which had alternating 1s and 0s.

      Anyway, thanks!

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

is there a proof for Div2C?

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

    Proof
    Standard parenthesis validity checker: counter++ for '(', counter-- for ')'. The sequence is valid is counter is always non-negative and hits zero at the end.

    Now, let's assume the string starts with '('. Counter = 1.
    Every time string A[i] = B[i], we have either a counter++ or counter-- at both places.
    So, it's safe to do the counter++ for the first half and the other for the second.

    For A[i] != B[i], every 2 0s, can reset counter to 0 in both the strings. If the number of 0s is odd, there's an unsymmetrical counter residue that cannot be cleared by the equality case (as the equal case adds the same number to both A and B).

    From these observations, there needs to be even number of 1s and 0s.
    First half of 1s should be open, 2nd half of 1s closed.
    Odd-even flip of paranthesis order for 0s.

»
3 years ago, # |
Rev. 2   Vote: I like it -14 Vote: I do not like it

Is it just me who lost problem D because the pretests didn't have the n=2 case?? I'm deeply saddened by this and it has affected my confidence. Was this a conspiracy against negligent coders like me?? (sobs profusely.)

Forgot to thank the creators for this amazing contest. The problems were really fun and they kept me at the edge of my seat!

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

    The very first pretest was n = 2 though...

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -16 Vote: I do not like it

      oh sorry, but i failed the 16th test case which had n=2, i must now proceed to quit codeforces, thanks for pointing out. bye. i will now delete all my comments

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I was just an '=' away from getting AC on B. Oh Man! This is such a drag.

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I don't understand why my n^4 solution passed in Div 2 D, here is link https://codeforces.com/contest/1504/submission/111924524

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

    $$$n$$$ is only $$$100$$$ and constant factor is pretty low and time limit is $$$3$$$ secs.

»
3 years ago, # |
  Vote: I like it -6 Vote: I do not like it

IMO only the ones that solved C will understand its editorial.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Alternative solution for 1504E - Задача коммивояжёра
Basic observation is similar. Cost for $$$i→j$$$ is $$$c_i + max(0, a_j - (a_i + c_i))$$$. There is another thing to look for. We can start from any city instead of city $$$1$$$ and still get same answer as our path is a cycle. That's how, we can just sort the cities based on $$$a_i$$$. Now, starting from the lowest $$$a_i$$$ city, we can go one by one and we can do transition from most optimal city to current city based on $$$(a_j + c_j)$$$ values.
Code — 111946687

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

    Proof?

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

    This is literally the second solution in the editorial.

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

      My bad, didn't understand what he meant at the 2nd solution, it looks like implementation is exactly same. Now I just noticed that sorting was mentioned in the very beginning.

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

        I couldn't understand either. Can you elaborate your solution?

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

          I am not entirely sure if this proof is correct, but this is how I convinced myself of this solution. Sort array a. So we have a1<=a2<=a3....<=an

          We start at a1. We want to greedily spend as little as possible. That is it would be locally preferable to have a 0 cost on going to the next city. Consider the set S of all cities having ai <= a1+c1. Obviously, S would be of the form {City 2, City 3...., City k} for some k.(City i has value (ai,ci). a is increasing after all:/).

          Now, simply go to city 2, There are two cases a2+c2 < a1+c1. In this case, having a1 in the front is better than having a2, since from a1 we can go to more cities free of cost. So we try rearranging the visiting pattern. We start from a2. Visit a1 free of cost since a2+c2>a1. Now, we have a1+c1 again at the front and we can visit other cities in S free of cost. In the other case, a2+c2 > a1+c1, in this case, don't change the ordering since a2+b2 in front would allow us to potentially visit even more vertices free of cost than those contained in S.

          This can be expanded to arbitrary lengths by induction. Say that you have observed {City 1, City 2, City 3,...., City k-1} and found a permutation such that the city with the maximum value of (ai+ci) observed so far (call it j) is in front. We prove that there exists an optimal ordering with this property. By Induction Hypothesis, assume this works for k-1. Then, The order of visit so far will then be {'Some other cities in some optimal order', City j} and this is the most optimal of all orderings possible with the available cities. Now the next city k can have 3 possibilities.

          Case 1: a_k > a_j + c_j In this case, there is no way to get 0 costs using any of the previously visited cities. Using aj+cj which is the maximum observed so far is the best choice in minimizing the current cost(a_k — (a_i+c_i)) for any i<k. In this case, the optimal order of visiting is {'Same order as before', City j, City k} and a_k + ck has the maximum value among all {a_i+c_i} observed so far! So the Induction Hypothesis holds here! We have expended minimum extra cost to add City k to what was already an optimal visiting order.

          Case 2: a_k <= a_j + c_j and a_k+c_k > a_j + c_j. Again keep the order as {'Same order as before',City j,City k}. This involves 0 cost and the front element (k) has the maximum { ai+ci } value observed so far. We have expended 0 extra cost here!.

          Case 3: a_k <= a_j + c_j and a_k+c_k <= a_j + c_j. This time we would like City j to be on the front and at the same time expend 0 extra costs for visiting City k. The solution is to simply visit City k first. The resulting order will be {City k,'Nothing changes in between', City j}.

          Proceeding this way, this strategy optimises the local value every step of the way and hence would give us the globally optimal solution.

          Please correct me if I am wrong.

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Can anyone provide a logical chain of Div2C? I understand how the answer is constructed but I am confused about how we come up with the idea from scratch and know its correctness.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help with the TLE error for div2B My solution

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

    This code is O(n^2).This line is actually c!=s1.length() O(n) in nature followed by for loop. U should use simulation starting from rightmost unmatching bit and using flips as a variable.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

traveling sales man problem is NP hard so how it's possible to solve problem DIV2 E or DIV 1 C for given constraints ?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there a way I could look at test case 60 and like that for a pretest. It is shown for the first few testcases like till 30 approx. . I wanted to know if I could download or view the complete test case file or at least the first test case where I made mistake . Is it possible ?

»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

omg hi !

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The solution described for C Div. 2 would give identical strings in case the input has only 1's. Is that the expected behavior or those should be different?

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

    Did you mean deterministically single answer for a fixed length?
    If so, yes, although there can be other valid answers.

    The strings being identical is the expected behavior.
    All 1s indicate that all positions are equal, which implies equal strings.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

To decompose an array into two decreasing subsequences, there is a standard greedy approach.

Can you share it please?

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

Greedyforces

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

    So many greedy problems! (I love greedy!)

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve 2F/1C for dp

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

YESorNOforces

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

Although I always lose rating in your contests, I really like your problems :)

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone please help me in C , Here is my submission 1504C

I have taken two characters from string at a time and created two brackets array according to them

(if first two chars are 10)

10 -

ch1+=()

ch2+=((

11 —

ch1+=()

ch2+=()

01 —

ch1+=()

ch2+=))

This is done iteratively and at last i checked both brackets array for balance using stack then accordingly printed "YES" or "NO"

I am not able to figure out why it is failing in test case 2 only .

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

    Consider the following case: 10010101

    Now as per your algo: a = ()()()() b = (()))))) And so you will print "NO". But it is possible to find valid bracket sequences and they are as follows: a = (()(())) b = ()(())()

    Hope this helps.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

111968151
For problem A, Insert 'a' into the symmetrical position of the first letter that is not equal to 'a', why it is wrong ?

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

    You should insert it into the position n-i, not n-i-1. For example, on the test case bab you output baab instead of baba.

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

      Thanks for reminding!
      I misunderstood the usage of insert

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

https://codeforces.com/contest/1504/submission/111914872 my code runs well if i use Sytsem.out.println. But when i append my ans on bufferWriter it does not show the String with extra 'a' in codeforces ide but when running on my eclipse ide it gives correct output. Why is it so?

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

    That isn't the only difference between your codes. You also changed i<n/2 (which causes the wrong answer) to i<=j(which is correct)

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

I think in the editorial of Problem E, it should be mentioned that it is always optimal to go from i to j+1 instead of j+2,j+3,j+4 etc....

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

111918468 Problem C, what's wrong with my answer? Input: 4 1111 Output: YES ()() ()() Checker: wrong answer a[i] = b[i] <=> s[i] = 1 broken at i = 1 Thank's for help)

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

People after submitting C : Well prob was easy , i can go to D now. . . . test-case 64 : You ain't going anywhere.

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

Could someone please explain why in the last part of the tutorial of Div1D "there is a unique way to decompose each segment"?

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

    Took me a while, but I think I figured it out. Suppose that we're trying to find a decomposition for some segment $$$[a, b]$$$ ($$$1 \leq a \leq b \leq n$$$). Let's maintain two subsequences $$$s_1$$$ and $$$s_2$$$, initially empty at the start of the segment. Without loss of generality, let's immediately add $$$f(a)$$$ to the end of $$$s_1$$$. Now let's greedily choose placements for all characters in the range $$$[a + 1, b - 1]$$$ (yes, this is intentional).

    Firstly, let's define $$$s(i) = \max\limits_{j > i} f(j)$$$ for $$$0 \leq i < n$$$ and $$$-1$$$ for $$$i = n$$$. Similarly, let's define $$$p(i) = \min\limits_{j \leq i} f(j)$$$.

    Suppose that we're currently choosing a placement for index $$$i$$$. Now, there's 2 cases: either $$$f(i) > s(i)$$$, or $$$f(i) < s(i)$$$.

    In the first case, since there's no divider between $$$i$$$ and $$$i + 1$$$, it must be true that $$$p(i) < s(i)$$$. Furthermore, $$$f(i) \neq p(i)$$$, since $$$f(i) > s(i)$$$ and $$$p(i) < s(i)$$$. Therefore, $$$p(i - 1) = p(i) < s(i)$$$. The key observation here is that $$$p(i - 1)$$$ must be equal to some $$$f(j)$$$ for $$$a \leq j < i$$$ (since either this segment was the first one, or there was a divider before this segment), and therefore must also be the value at the end of either $$$s_1$$$ or $$$s_2$$$. Since $$$f(i) > p(i - 1)$$$, it must be added to whichever subsequence doesn't end with $$$p(i - 1)$$$.

    In the second case, it must be true that $$$s(i - 1) = s(i)$$$. Since there's no divider between $$$i - 1$$$ and $$$i$$$, it must be true that $$$p(i - 1) < s(i - 1) = s(i)$$$. Once again, $$$p(i - 1)$$$ must be at the end of either $$$s_1$$$ or $$$s_2$$$. This time, we must add $$$f(i)$$$ to whichever subsequence has $$$p(i - 1)$$$ at the end of it, since otherwise we would have both subsequences ending in something less than $$$s(i)$$$, which is impossible.

    What's left is determining in which subsequence $$$f(b)$$$ should go (if $$$b = a$$$, then we're done). Suppose that $$$f(b) < s(b)$$$. Then $$$s(b - 1) = s(b)$$$. Since there's no divider between $$$b - 1$$$ and $$$b$$$, $$$p(b - 1) < s(b - 1) = s(b)$$$. However, this is a contradiction, since this implies $$$p(b) \leq p(b - 1) < s(b)$$$, which shouldn't be the case if either there is a divider between $$$b$$$ and $$$b + 1$$$, or $$$b = n$$$. Therefore, $$$f(b) > s(b)$$$. It follows that $$$p(b - 1) < s(b - 1) = f(b)$$$. Once again, since $$$p(b - 1)$$$ is at the end of either $$$s_1$$$ or $$$s_2$$$, $$$f(b)$$$ must be placed at the end of the other subsequence.

    In all cases, the choice of adding to the end of either $$$s_1$$$ or $$$s_2$$$ is deterministic. Note that if we began by adding $$$f(a)$$$ to the end of $$$s_2$$$ instead of $$$s_1$$$, all decisions would have been swapped due to symmetry, hence the only choice we have to make is which subsequence is which.

    lmk if I made any mistakes, I'm too tired to proofread :D

»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

How to solve D1D with 2-sat?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help me why my O(n) solutions: 112036570 and 111956392 both give TLE?

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

    You are creating array 'arr' many many times

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

      I moved the declaration above my while loop here: 112037826 and it still gives me TLE.

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

        I'm not sure but seems that scanf(" %s", &arr); is O(n) not O(the size of the string) so try to use string arr instead of char arr[300001];

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

          You can only create char arrays in C for strings.

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

            Use C++

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

              That doesn't solve my question and I've seen passed attempts in C that use scanf.

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

                Ok I'm really sorry I don't know C

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

        112208235

        I changed scanf(" %s", &arr) to scanf("%s", &arr) and got AC. I have also ever faced similiar bug, but I don't understand the cause as well. Maybe somebody else might be able to explain.

»
3 years ago, # |
Rev. 4   Vote: I like it +3 Vote: I do not like it

My approach for Problem div2C: Let us consider balance of a string as the difference of opening and closing brackets. So in order for the string to be perfectly balanced, the balance of the string should never be < 0 in any iteration and should be 0 at the end of all iteration.

bal1=balance of 1st string bal2=balance of 2nd string

the main approach here is that we want our balance to be as close to 0 as possible.

Notice that '1' always increases or decreases the balance of both string by 1 and '0' decreases the balance of one string and increases the balance of the other one.

Therefore we would greedily increase or decrease the balance of both the string so that their balance remains closer to 0.

There is also an edge case where bal1=1 and bal2=1 and the current position in string has '1' in it. in this case we have to check the next character of the string.

Why we have to check the edge case?

As because greedy solution will decrease both the balance by 1 and if the next character is '0' then balance of one of the string would become negative.

My solution:112041165

»
3 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

In Div1 D : "We can independently choose how to decompose each segment into two subsequences" Can anyone tell me how to decompose a single segment ?

»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Div1C/Div2E can also be solved using disjoint set union (similar to Kruskal's algorithm). My code

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the intuition behind solution 1 of Div1 C? I don't know how to come up with that implicit graph.

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

    The intuition is that we've reduced the problem to shortest path in a graph with $$$O(n^2)$$$ edges. We just have to think which edges are redundant (because the other edges create a better or equal cost between the same pair). If you remove enough redundant edges, you find that you only need $$$O(n)$$$ edges.

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

Can anyone help me in finding the mistake in Problem D Div 2? I am doing as per the editorial only. It is failing on Test Case 6. 111982213

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

In problem DIV2 F (flip the cards) , could someone explain the intuition behind splitting the array into segments based on condition that minimum to left of $$$i$$$ is greater than maximum of right to $$$i$$$. I didn't get why we are doing this.

What i understood is that it's necessary we need to split [f(1),f(2),f(3),...,f(n)] into 2 decreasing subsequences (where one can also be empty). If we minimize length of one of the subsequence then number of flips would be minimized . But how we splitting is helping us here ?

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

    Monogon could you please help here why we are splitting when minimum to left of $$$i$$$ is greater than maximum of right to $$$i$$$. I understand that finding $$$2$$$ decreasing subsequence directly might not give optimal solution . So how we justify that splitting it like that will help us find the optimal solution ?

    According to the editorial two subsequences will be unique if we split in that way. How to prove it ?

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

      could someone explain the intuition behind splitting the array into segments based on condition that minimum to left of i is greater than maximum of right to i.

      Suppose there is a place where the prefix min is greater than the suffix max. Then if we split here and decompose the two halves independently, they can be combined in any way, and it will still be a valid decomposition into decreasing subsequences. The fact that we can make independent choices is intuitively good, because we can now focus only on optimizing each individual choice.

      According to the editorial two subsequences will be unique if we split in that way. How to prove it ?

      We need to show that an array with no position such that prefix min > suffix max has a unique decomposition into two decreasing subsequences (up to naming the two subsequences). Consider the maximum element in the array, let's say it is in subsequence $$$1$$$. It cannot be the first position since it would violate the condition, so everything before it must be in subsequence $$$2$$$.

      Now we have the unique decomposition of the prefix. Now consider the maximum element of the remaining elements. We cannot place it in subsequence $$$2$$$, or it would violate our assumption. So we are forced to place it in subsequence $$$1$$$, and all unassigned elements before it must be in subsequence $$$2$$$. Keep repeating this process until all elements are assigned to subsequences. Every decision we made was forced except for naming one of the subsequences $$$1$$$ and the other $$$2$$$, so it is the unique decomposition.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

i write my solution in python, its a O(n) solution can someone tell me why i am getting this tle? https://codeforces.com/contest/1504/submission/112123685

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In Div1 problem F,how can I get the solution after doing operations? And how can I find the leftmost point? I found judge points by ai>0,bi>0 will get wrong. thanks :)

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

    You should find a point with $$$a_i>0$$$, $$$b_i > 0$$$, has an incoming $$$1$$$ edge, and has an outgoing $$$1$$$ edge. With these conditions, the choice doesn't matter.

    By doing operations, we represent the curve implicitly by a linked list of the points (besides the leftmost one) as they appear horizontally. Each point keeps the card ID, so in the end the solution is given precisely by the order of elements in the linked list.

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

      And how can I do operator 3?

      Should I keep the head,tail of the linked list,and the places of incoming edge and outgoing edge?

      I think it is a little troublesomely to merge two linked list,or maybe I lose some properties :(

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

        You can look at 111940018 for the list solution. (It's also solvable using treaps, relevant submission: 111939934, and both solutions use a similar interface for the curve structure).

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

        What a crazy problem with so many details...

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone give me the input string that failed my solution code?

My Solution

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

Statement in tutorial of Problem 1504F: "Also, there is a unique way to decompose each segment: the only choice is in which one we call the first subsequence". Why it is unique? Could someone give me a detailed explanation, thanks~

»
3 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Alternative (messier?) solution for 1503D - Переверните карты
Actually it turns out to be very similar to the solution in the editorial, but maybe the "path" to this solution is more intuitive.
Consider each card as a segment $$$[\min(a_i, b_i), \max(a_i, b_i)]$$$. Let's say that a segment has color $$$0$$$ if $$$a_i < b_i$$$, $$$1$$$ otherwise.
If two segments don't intersect, there is no solution. Two segments such that the biggest one contains entirely the smallest one can be colored in any way. In any other case, the two segments should have different colors.
Let's find a coloring of an interval of length $$$n$$$. Our goal is to construct a graph such that two segments connected by an edge have different colors. If there is a solution, the graph is bipartite: for every connected component, there are two possible colorings, and we have to choose the one that minimizes the number of flips. There are two cases:

  • There is a segment $$$[1, n]$$$. It can be discarded (since it makes a connected component of size $$$1$$$), and the problem can be solved recursively in the interval $$$[2, n-1]$$$.
  • There are two segments $$$[1, x]$$$ and $$$[y, n]$$$ (let's define them "special" segments). The other segments should be contained in at least one of the special segments (otherwise the graph is not bipartite, since it contains a cycle of length $$$3$$$).
    There are three types of segments: inside $$$[y, x]$$$, inside $$$[1, x]$$$ but not $$$[y, x]$$$, inside $$$[y, n]$$$ but not $$$[y, x]$$$. If two segments of type $$$2$$$ are connected by an edge, they also form a cycle of length $$$3$$$ with $$$[y, n]$$$. Hence, all the pairs of segments of type $$$2$$$ (and $$$3$$$) are such that the biggest one contains entirely the smallest one. Hence, the special segments and the segments of type $$$2$$$ and $$$3$$$ make a connected component, and any of them isn't connected to a segment of type $$$1$$$. Then, the problem can be solved recursively in the interval $$$[y, x]$$$.
    How to find all the connected components in $$$O(n)$$$? For each component, we can find the segments of type $$$2$$$ and $$$3$$$ in $$$O(\text{# of such segments})$$$. Let $$$[l_1, r_1]$$$, $$$[l_2, r_2]$$$ be the special segments. While there exists a segment $$$[l, r]$$$ with $$$l < l_2$$$ and $$$r < r_1$$$, replace $$$[l_1, r_1]$$$ with such $$$[l, r]$$$ with minimum $$$l$$$. Do the same for $$$[l_2, r_2]$$$, then again for $$$[l_1, r_1]$$$, etc., until no more segments can be found.
    112259448
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    nice solution i have some ideas of another graph model of the problem but ive didnt finished it maybe you can help me with it! my idea : if we consider 2n graph nodes which the node 2i is the i-th card normally and the 2i — 1 is the reverse of the i-th card and if we put a directed edge between node v, u(v -> u) it means that the representing card of u has bigger elements on both representing sides(like card v = {1, 5}, card u = {3, 6}) in this graph we dont have directed Cx(cycle with lengh x > 2) and we dont have even directed P3(v -> u -> z) if we have, the answer is -1 because in the answer there will be two of them in same side. so the graph is some directed stars but ive couldnt do any decomposition to get the answer do you have any idea?

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

      Directed edges don't seem to work (if I understand, they make a dag so they can't make cycles). If the edges are undirected, you can have cycles of even length and an answer $$$\neq -1$$$ (for example, $$$(1, 6) \leftrightarrow (3, 8) \leftrightarrow (2, 5) \leftrightarrow (4, 7) \leftrightarrow (1, 6)$$$). In your graph, there are edges between each pair of cards that in my solution is $$$(\text{card of type 2}, \text{card of type 3})$$$ in the same connected component. For example, in $$$(1, 6)$$$, $$$(2, 5)$$$, $$$(3, 8)$$$, $$$(4, 7)$$$, there is only one connected component, with

      • cards of type $$$2$$$: $$$(1, 6)$$$, $$$(2, 5)$$$
      • cards of type $$$3$$$: $$$(3, 8)$$$, $$$(4, 7)$$$
      • edges: $$$(1, 6) \leftrightarrow (3, 8)$$$, $$$(1, 6) \leftrightarrow (4, 7)$$$, $$$(2, 5) \leftrightarrow (3, 8)$$$, $$$(2, 5) \leftrightarrow (4, 7)$$$
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        well the directed graph has the star property because in your example the graph is kinda like this -> a -> c, b -> c, a -> d, b -> d. idk just and idea : ))

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

          Yes, every connected component is a complete bipartite graph. But there may be more than $$$1$$$ connected component, for example in $$$(1, 7)$$$, $$$(2, 8)$$$, $$$(3, 5)$$$, $$$(4, 6)$$$.

»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

[user:Mihir2422]hi

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem 2-Coloring, when you mention

a monotonically increasing path from (1,0) to (rA,c)

What exactly does it mean? For example, for the (x, y) mentioned, are the Ox and Oy the normal mathematical Ox (left to right) and Oy (down to top)? Or are they row (top to bottom) and column (left to right) axes?

Can you give a clearer example?

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

    Coordinates are (row, column). Here is a picture of the described situation.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Extremely elegant and fast solution for F: 123227611

»
9 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

FOR PROBLEM A CAN ANYONE PLEASE TELL WHY THE FOLLOWING CODE IS GIVING WRONG OUTPUT AT 2879 TEST CASE

include<bits/stdc++.h>

using namespace std; int main() { long long int t; cin>>t; while(t--) { long long int f=0,d=0; string s; cin>>s; long long int l=s.length(); long long int res=0; for(int i=0; i<l; i++) { while(i<l && s[i]==s[i+1]) { i++; } res++; } string c="a"; if(res==1 && s[0]=='a') { cout<<"NO"<<endl; continue; } cout<<"YES"<<endl; if(s[0]!='a') { cout<<s; cout<<c<<endl; continue; } if(s[0]=='a' && s[l-1]!='a') { cout<<c; cout<<c; for(int i=1; i<l; i++) { cout<<s[i]; } cout<<""<<endl; continue; } long long int h=0; long long int i=0,j=l-1; while(i<j) { if(s[i]==s[j]) { i++; j--; } else { break; } } if(i>j) { cout<<s; cout<<c<<endl; continue;

}
                else
                {
                    h=i;
                    for(int k=0; k<=h; k++)
                {
                    cout<<s[k];
                }
                cout<<c;
                for(int k=h+1; k<l; k++)
                {
                    cout<<s[k];
                }
                cout<<""<<endl;
                }
}
return 0;

}Monogon

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

CAN Monogon PLEASE TELL WHY THE FOLLOWING CODE IS GIVING WRONG OUTPUT IN TEST CASE 2789 IN PROBLEM A 209030972