vovuh's blog

By vovuh, history, 2 months ago, In English,

1296A - Array with Odd Sum

Idea: vovuh

Tutorial
Solution

1296B - Food Buying

Idea: vovuh

Tutorial
Solution

1296C - Yet Another Walking Robot

Idea: MikeMirzayanov

Tutorial
Solution

1296D - Fight with Monsters

Inspiration: 300iq, idea: vovuh

Tutorial
Solution

1296E1 - String Coloring (easy version)

Idea: MikeMirzayanov

Tutorial
Solution (dp)
Solution (greedy)

1296E2 - String Coloring (hard version)

Idea: MikeMirzayanov

Tutorial
Solution

1296F - Berland Beauty

Idea: MikeMirzayanov

Tutorial
Solution
 
 
 
 
  • Vote: I like it
  • +97
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it +39 Vote: I do not like it

It was really nice round. Wish everyone's rating to increase.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sorry I downvoted by mistake..... a good set of questions for a beginner waiting for the next div 3 contest

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

I can solve F like this: for every edge E find the maximum number that appears in the pathes that contain E and set that number for e. After all check if there is a contradiction the answer is -1, otherwise output the edge numbers. Its complexity is O(n*m). Does anybody has any better solution?

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

    I used a maximum matching algorithm between the queries (A set) and the edges of the original graph (B set). In the flow network there is an edge with capacity 1 between an element of the first set and the second set if the value of that query is greater or equal than the minimum value that an edge from the B set must have.

    After running the maximum matching algorithm, assign the values of the queries matched to the elements of the B set and check if the resulting graph doesn't have any contradiction.

    Using Hopcroft-Karp the complexity is around the same as you said.

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      What wrong with the community? Although the comment's approach may be (overly) complicated, it offers a new perspective to the problem. We should point out what makes this approach bad or what can be done to improve. Even you cannot understand it, you can ask for clarification. What's the point for just down-voting without making any comments?

      Wanna ask why your approach's complexity is around $$$O(nm)$$$. I assume you are building a flow network with $$$n \cdot m$$$ edges, and the complexity of running Hopcroft-Karp in your network should be $$$O(nm*\sqrt{n+m})$$$. Also, did you do anything to keep your constants low?

      IMO the observation 'the minimum value that an edge can have is a valid config if and only if there exists a valid config' is not that intuitive. The proof is not that straight forward either. What the comment writer did is to use maximum matching to construct an answer that would be 'more probably' to be correct. Anyway, for me personally, I would not code a flow for that, at least in a div 3 contest.

      Sorry for you getting so many downvotes. :C

      • »
        »
        »
        »
        7 weeks ago, # ^ |
        Rev. 2   Vote: I like it +5 Vote: I do not like it

        Oh... I mistook the square root on the edges not the nodes so I thought it was around the same complexity. Anyway, this solution uses a lot of memory, I had to reduce my variables to short to pass.

        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          I also thought that a match would not occur in two possible situations: when the query on set A is the result of a combination of other queries paths or when it's really impossible to set the edge as a value and not contradict other queries. So at the end I would check if all paths do not contradict which would also check if the queries that were combination are consistent with the values.

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

    Okay. At first set all edges to $$$10^6$$$ Let's iterate over paths in non-decreasing order of $$$g_i$$$. Now notice that we can simply set $$$g_i$$$ to all edges in the current path to make tree correct for the current path. After making this with all queries find the minimum on each path and compare it with the needed one. Now we have queries of 2 types:

    1. Set some value on the path

    2. Get minimum on path

    This can be done using Heavy-Light Decomposition and a segment tree in $$$O(mlog^2n)$$$ :D

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Great solution, can you pls tell me why should we go only in non-decreasing order of gi ?

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

        You notice that for every query, all of the edges on that query must be at least the number given. Therefore, when we go in non-decreasing order, we never violate any previously processed queries unless the whole path of the original query is covered. This allows us to process each query only once in O(log^2 n) with HLD + Segment Tree as mentioned above, giving a total complexity of O(mlog^2 n)

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

        If the explanation above isn't enough, you can read my explanation here

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you please explain how to check if there is a contradiction and what's the time complexity of it?

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Do you mean checking if the answer is $$$-1$$$? You have an information that the minimum on the path between $$$a_i$$$ and $$$b_i$$$ is $$$g_i$$$. Heavy-light decomposition can answer query $$$minimum$$$ $$$on$$$ $$$the$$$ $$$path$$$ in $$$O(nlog^2n)$$$ time using a segment tree. To check if our answer is correct just iterate over all given paths and check if the minimum on the $$$i$$$th path is equal to $$$g_i$$$. If not, the answer is $$$-1$$$

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        but the cfmaster guy said the complexity is $$$O(mn)$$$, so idk how he did it, or maybe he just made a mistake?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Now I get you

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i used this solution too, but i can't prove that true.

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

For F, Can anyone tell me any optimization in my code!

Time limit exceeded on test 268 :(

https://codeforces.com/contest/1296/submission/70317535

Thanks!!

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

    probably your solution runs in $$$O(n^2logn)$$$ which is a bit high if your constant factors in time complexity are large. Using unordered_map + a good hash function will pass the tests.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      actually my solutions has the complexity that you said and i didnt use unordered_map and it got AC !

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

      Yeah, I was using Maps for no reason while I could have used 2D array. I changed that and now its working.

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        To store the edges you could just store the edge that goes from v to i that v is parent of i as f[i]

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Thanks for this round! Waiting for another Div.3 rounds :)

»
2 months ago, # |
  Vote: I like it +33 Vote: I do not like it

We have a direct formula in B, that is (s-1)/9+s;.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    overwrite can you give a proof for this claim?

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

    can you explain the formula please?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it -14 Vote: I do not like it

    I solved it by doing (n/0.9). If n is 9 I have to subtract one.

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

Well this is a bit off-topic ; but is anyone else also experiencing some un-expected indentations in their codes in codeforces submissions ?

As for example : code 1 — https://codeforces.com/contest/1296/submission/70274974

code 2 — https://ideone.com/126Qo1

These are exact same codes ; just codeforces does some un-usual indentations

Example 2 : code 1 — https://codeforces.com/contest/1296/submission/70317304

code 2 — https://ideone.com/DtpiMq

Any take on this ? maybe MikeMirzayanov ?

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

    The problem is that the width of tabs on codeforces are 8 while on ideone are translated into 4, and your editor uses a mixture of spaces and tabs.

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

      But then if this is the case ; then I think this should have happened with every single code every single time. But actually this problem never occurred before. I am just seeing it now.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Do you know how to fix the problem?

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

        The key is consistency.

        You may either try to replace all occurences of $$$4$$$ consecutive spaces to tabs, which will look the same on ideone. On Codeforces it will look much wider (tabstop size = $$$8$$$).

        OR

        You may convert all tabs to $$$4$$$ consecutive spaces. It will look the same both on ideone and Codeforces.

        :)

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

Do basically in D, we could kill monsters in any order?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You must kill monsters in given order, but the final answer has nothing to do with the order. After the sort() you could know which monsters to kill(by using secret technique) to get the maximum answer, then you could kill them in the previous order and the answer will not change.

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I did not understand why the order doesn't play a role?

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It is because we can let our opponent kill the target we don't want to kill and kill only the ones which our greedy strategy provided......that's the reason why order doesn't matter because we can manipulate our opponent as we wish making him kill the unwanted enemies...cruel XD

        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          But it is mentioned in the question that after using technique 2 times on first monster, we could use technique only 1 time on the next monster, that is number of times technique is used is decreasing?

          • »
            »
            »
            »
            »
            »
            7 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I think it was made to trick us.

            "(for example, if there are two monsters and k=4, then you can use the technique 2 times on the first monster and 1 time on the second monster, but not 2 times on the first monster and 3 times on the second monster)"

            The reason why we can not use 3 times on the second one because of the constraint of k = 4 ( 2 + 3 > 4 ). It is not forbidden to use 2 on first and 2 on second.

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I used Bubble Sort to solve E1 ->70281553 and I wonder if it's correct.

By the way, What are A and L represent in E1's tutorial

Thanks qwq

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

Hello.I got WA with my C's submission and i don't even know what is the problem. Is there any body can help me indicate where i should fix? Please. 70292288

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

DSU solution for E1: https://codeforces.com/contest/1296/submission/70272613
If there exists i, j that $$$ s_i > s_j $$$ and $$$ i < j $$$, there must be $$$ c_i \neq c_j $$$ , in other words, $$$ c_{i, 0} $$$ always exists with $$$ c_{j, 1} $$$ and $$$ c_{i, 1} $$$ always exists with $$$ c_{j, 0} $$$. $$$ s_i $$$ is the i-th char. $$$ c_i $$$ is the color of the i-th char. We use dsu to union $$$ c_{i, 0} $$$ and $$$ c_{j, 1} $$$, $$$ c_{i, 1} $$$ and $$$ c_{j, 0} $$$. Before union if we find $$$ c_{i, 0} $$$ and $$$ c_{j, 1} $$$ is already united, we print "NO".
Then, we just color 0 or 1 for every char. We color i-th char into 0, and color any char united with i for every i-th. This can be implemented in O(n), although my submission is O(n^2).

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

E2 Hard Version I wonder if the solution it to calculate the longest decreasing subsequence? Not the least decreasing subsequence? Is it right?

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

There is an $$$O(1)$$$ per test case solution for B.

If $$$9$$$ is a factor of $$$s$$$, the answer is $$$\lfloor \frac{s}{9} \rfloor \times 10 +s\bmod 9-1$$$.

Otherwise, the answer is $$$\lfloor \frac{s}{9} \rfloor \times 10+s\bmod 9$$$.

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

Will there be any penalties for an unsuccessful attempt?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yes! if you submitted any correct solution after unsuccessful attempt that passes system test too.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      grg124 I mean a hacking attempt

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

        A hack attempt is also ignored if by the given moment the hacked solution is not the contestants' last verified solution of the problem. ... A contestant gets 100 points for a successful hack and a penalty of 50 points for an unsuccessful hack. see this link for more information https://codeforces.com/blog/entry/4088

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks!

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

            But this round was hosted by rules of educational rounds (extended ACM-ICPC). After the round, there will be a 12-hour phase of open hacks. That means, in this round, a unsuccessful hacking attempt will not get any penalty points.

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

for problem B Can any one explain how the solution in editorial works for number like 19 or 12345. I figure out that it is quite obvious for no which are only like power of 10 only..

»
2 months ago, # |
  Vote: I like it +6 Vote: I do not like it

I've found few Guys Rampantly Cheating during Contests. Can Anyone please guide me, how to take this forward and make sure that this is seen by MikeMirzayanov , and there accounts are banned!

Manthan_144

and

rajan_ladani

Here are the Submissions they did in Codeforces Round #617 (Div. 3), and it clearly Shows that they are Big Cheats!

The Submission Of E1/E2 is clearly copied, and several redundant while loops have been added in order to escape from the copy-checker mechanism!

Manthan_144 :: 70282306

rajan_ladani :: 70294414

Apart From this they have also copied A,B,C,D

Guys please dont be cheats, and respect the community!

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

[deleted]

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    70268224 Like this solution.

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

    [deleted]

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      This solution does not work because persistant segment tree couldn't do it either... Sorry for all my nonsense here.

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

        Just wondering, since all you need to do is set_max on a path, why not just use a straightforward LCT to do that.

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

In Easy version tutorial, it said, "Let's go from left to right and carry two sequences s1 and s2. If the current character is not less than the last character of s1 then let's append it to s1, otherwise, if this character is not less than the last character of s2 then append it to s2, otherwise the answer is "NO".

While in Hard version, I also see the solution like find the minimum position i which satisfies the current character is not less than the last character of s_i by binary search, and append it to s_i. If not found, create a new sequence s_cnt and append it to s_cnt. How to prove it with Dilworth theorem?

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

plz add java and python solution. Thanks.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    read editorial.most probably you will figure out. If you really need code then go to all accepted submission and see them in your language.

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

      Thanks monk. But see all accepted solution & find java and python code is too boring.

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

There is a O(1) solution for problem B:

if total money is divisible by 9 then answer is 10*(n/9)-1 else 10*(n/9)+(n%9)

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

In problem D, the number of secret technique needed can be simply calculated by (h-1)%(a+b)/a

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you please explain how did you arrive at this. Thank you!

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

      It's similar to the original editorial, the only difference is that I used (h-1). Here's the reason: if $$$1\leq h\leq a$$$, we don't need to use secret technique, but if $$$h=a$$$, $$$h\bmod a=1$$$, so if we use (h-1)%a, that issue gets fixed.

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Im having trouble understanding of editorials solution too :(. I wanted you to explain how does this formula work.

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

          Alright, so the module works because the the part of hp that greater than $$$a+b$$$ can be removed by attacks and it doesn't affect the result. Now the hp is $$$(h-1)\bmod (a+b)$$$ and we need attack (h-1)%(a+b)/a+1 times to kill the monster so we need to use secret technique (h-1)%(a+b)/a time.

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

In B we don't need a power of 10 — a multiple of 10 will do. And it is easier to calculate — s-s%10.

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

Could anyone see why I go TLE for my Problem C? (I use** set** to implement search instead) https://codeforces.com/contest/1296/submission/70331575

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

Hey, so for problem C, I have thought of an alternative solution where, I have made prefix arrays of l,r,u and d. Now, since the robot ends at the same location in a substring, I just need to see substrings of powers of 2(as only then he will be back at the same location) from 1 to 18(according to constraints) in the whole array. So if at any time, delta(l)==delta(r) and delta(u)==delta(d). Those indeces are my answer.

However, I am getting WA on a test case whereas I cant find any testcase to contradict. All the non-truncated test cases are passing. Please help: https://codeforces.com/contest/1296/submission/70330963

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Its possible that the optimal answer's length is not a power of 2. Consider RRUULULDDD

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh, okay! Didn't think if that! Thanks a lot! :)

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

For E1, there is a O(N) dp solution 70333509

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    please explain as well

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

      dp[i] = if I split a[0], a[1], ..., a[i] into two non-decreasing subarrays, what is the minimum possible value of last element of the subarray other than the one a[i] belongs to.

      pre[N] and pre1[N] are just recording how the dp transit for restoration.

      I hope that you can understand my poor English.

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

I still don't understand the parity stuff in A. Someone please help a noobie

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Let me tell you what i have done for A

    For NO: Two cases possible: 1)all numbers are even 2)all numbers are odd and there are even numbers In both cases sum is even and we also can't change the parity(even to odd) as all numbers in both cases have same parity.

    For YES: So now we have at least one even and one odd number(the case with all numbers are odd and they are odd in number has sum always odd) and we can change every odd number to even except one in this way we can get odd sum always.(one odd and remaining even)

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Well I am completely embarrassed, but i think that I did't understand the problem statement even now. I thought that the question was too simple like "YES" for odd sum and "NO" for even sum.

      Specially I didn't understand the this line of the problem

      "In one move, you can choose two indices 1≤i,j≤n such that i≠j and set ai:=aj. You can perform such moves any number of times (possibly, zero). You can choose different indices in different operations. The operation := is the operation of assignment (i.e. you choose i and j and replace ai with aj)."

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Well, the array has an odd sum of elements if the number of odd elements is odd. To know this we count them.

        If this count is not odd we would like to make it odd.

        To make it odd, we can "overwrite" an even element by an odd one (or vice versa), which is "one move". We can make such a move only if there exists an even element, and an odd one.

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

    If the sum of whole array is yes from the beginning, then the answer is yes, otherwise if the number of $$$**odd**$$$ or $$$**even**$$$ number of the array equals $$$n$$$, the answer is No otherwise the answer is yes (It won't be possible to transform the array by that.

»
2 months ago, # |
  Vote: I like it -8 Vote: I do not like it

I WANNA KNOW THE PROBLEM ABOUT THIS CODE; I THINK IT'S RIGHT.

include<stdio.h>

void main() { int t, i, n, j, a, t1=0; scanf("%d", &t); for (i = 0; i < t; i++) { t1 = 0; scanf("%d", &n); for (j = 0; j < n; j++) { scanf("%d", &a); if (a % 2 == 1) t1++; } if (t1 % 2 == 1) printf("YES\n"); else printf("NO\n");

}

} THANK YOU;

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

    Perhaps it is caused by "void main()" which usually is "int main()".

    It seems strange that you get the runtime error after printing the last result.

    Please note that is is usually more usefull to post the link to the submission instead of the code itself, like 70333640

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

      Thanks.Your suggest is truely right.

      But this code is wrong.In my first edition , the answer is right.

      I feel sorry about to post my code.I haven't expert how to post link.sorry

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

        On top of the edit area there are some symbols. Click them, they won't bite you ;)

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

It's OK to solve F in $$$\mathcal{O}(n\log^2 n)$$$ with Segment Tree Beats! (introduced here: https://codeforces.com/blog/entry/57319) and HLD. But it's rather long...

Maybe set or other DS can solve it, too.

My code: 70340529

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can iterate over paths offline in non-decreasing order of $$$g_i$$$, so the STB isn't needed ;)

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Well... I can't manage to process the situation when an edge is re-coloring without STB, would you please explain it more clearly? Many thanks.

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

        For what do you need STB? For each path, you do such thing: set all edges on this path to at least $$$g_i$$$. To do this, you use HLD + STB, am I right? What if we sort all paths in non-decreasing order of $$$g_i$$$? Now to set all edges to at least $$$g_i$$$ we can assign $$$g_i$$$ to each edge. Why? Let's take a look at 2 paths with numbers $$$i$$$ and $$$j$$$, $$$j < i$$$ and $$$g_j > g_i$$$. They have a path $$$l_1 - l_2$$$ in the intersection. Consider an edge $$$e$$$ in this intersection. After proceeding the path $$$j$$$, $$$f_e \geq g_j$$$. To make $$$f_e$$$ correct for the path $$$i$$$, we have to make $$$f_e := max(f_e, g_i)$$$. But what if we proceed path $$$i$$$ before path $$$j$$$? After the path $$$i$$$, $$$f_e \geq g_i$$$. $$$g_i < g_j$$$ so $$$f_e := max(f_e, g_j)$$$. If we sort all paths in non-decreasing order, for each $$$t$$$ ($$$t < j$$$), $$$g_t \leq g_j$$$. Thus $$$f_e := max(f_e, g_j)$$$ is equal to $$$f_e := g_j$$$, where $$$:=$$$ is an assignment operator. This leads us to a solution: assign $$$g_i$$$ to each edge for each path, iterating through paths in non-decreasing order of $$$g_i$$$. This is a HLD + standart Segment tree.

        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          As this example shows: the tree is a chain, let its length equals to 4.

          1<->2<->3<->4
          

          And the coloring order is:

          2 3 2
          1 4 3
          

          Firstly, we color the path 2 to 3 with 2. When we color the path 1 to 4, we can't color the path 2 to 3 with 3, but in HLD we can't iterate each edge on path. However we change the order we iterate, it can't avoid the problem. So it should use STB I think.

          Anyway, STB works seems quite fast (as fast as standard segment tree, though it's looooooong). Thanks for your reply :D

          • »
            »
            »
            »
            »
            »
            7 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Are you sure that your example's answer is not $$$-1$$$? My code will paint edge 2-3 with 3 after the second query. After all it will see, that our answer is not correct (min on the path 2-3 is equal to 3) and print $$$-1$$$

            • »
              »
              »
              »
              »
              »
              »
              7 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Oops sorry. I puts a wrong index.

              2 4 2
              1 4 3
              

              3, 2, 2 is a valid solution.

              When we color the path 1->4, we only color edge 1->2, but when doing HLD, we will color all the edge 1->4 with color 3.

              • »
                »
                »
                »
                »
                »
                »
                »
                7 weeks ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                3, 2, 2 is invalid :D. Minimum on the path 1-4 is 2, but not 3

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

                  Ahhhhh I'm almost dizzy...

                  I try to implement your idea, but met many problems and can't pass the sample 2... You can check my code here.

                  This one can't pass sample 3...

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Ethylene, you have to iterate over all queries once again to check if the ans is -1. Do not do this in the same for

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

                  70606132 passed.

                  Really thanks for your help :D

»
2 months ago, # |
Rev. 2   Vote: I like it -7 Vote: I do not like it

For E1/E2, I simply used the strategy that when we consider elements from left to right, we need to "sink" each element into the correct position, which requires the current element to be a different color than any previous elements that are greater than it. We then set this color in both the answer and in another array that indicates the maximum color used for each letter. Any subsequent letters less than this letter must be a new color.

This reduces the problem to range-maximum and point update for an array of size $$$AL$$$. If we had to sort integers instead of characters, a segment tree can be used instead, but due to the small size of the alphabet one can just do this naively on a plain array.

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

Can somebody tell me why my solution to problem 1296C - Yet Another Walking Robot is wrong? My solution: 70296424

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

    Did I call someone or say something indecent? I just asked what is wrong in my solution, why are you minus my comment?

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

For problem E2, there is a greedy solution :https://codeforces.com/contest/1296/submission/70332678 while read in a new alphabet, check all colors that have been chosen, if all colors are greater than it, choose a new color, then record its number to print.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Besides, in E2 tutorial, I think dp maybe mean the longest decrease but not the least.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I also solved it as a greedy solution and I think it is a better solution

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

There is also $$$O(n^2)$$$ solution for E1, basically find position of max element (if there's more than 1 pick rightmost), then we want to make suffix pattern from that position like this "100..000" so we can move it to the last element (if we can't then answer is NO) then bring that maximum element to the end and recurse to subproblem with string length n — 1.

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

In Problem D. when h%(a+b) is 0 , why we have to rollback. As the monster is killed by us and we got the point. Can you please explain.

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

    it's killed by opponent, because if h % (a + b) = 0, there is time when h equal a + b, after that we attack, now h equal a + b — a = b, then opponent attack, then monster die.

»
2 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Wow there are a lot of different solution to E1. Here is another one:

For all j < i, if s[j] > s[i], add an edge between i and j. The answer is the two coloring of the resulting graph, if it exists.

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

regarding the colouring strings question,If we simply just store maximum element in two colour after each i ,0<i<n,it would be enough.Let max of first colour be in a and second in b.We take condition such that b>=a. Initially assign them a=-1 and b=-1.Then if s[i]<a,spliting is not possible.If it is greater than o a but less than b it must replace a.Else it must replace b,which gives us our answer in o(n). below is the code I used

#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,a=-1,b=-1;
    string s,g="";
    cin>>n;cin>>s;
    for(int i=0;i<n;++i)
    {
        //if(a>b)swap(a,b);
        if(s[i]<a){cout<<"NO\n";return 0;}
        else if(s[i]>=b){b=s[i];g+='0';}
        else {a=s[i];g+='1';}
    }cout<<"YES\n";cout<<g;
    return 0;
}
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, what's wrong with my solution. It gets TLE, but works in O(n^2). https://codeforces.com/contest/1296/submission/70360668

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int cnt=0;
		int num;
		cin>>num;
		int rem=num;
		while(num-10>=0)
		{
			cnt++;
			num=num-10+1;
		}
		cout<<rem+cnt<<endl;
	}
	return 0;
}

In the above code for B why I am experiencing TLE on test 3

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    are u serious brooo..... u r just subracting 10 each time ... do u understand how many iterations would it take for a number of order 18....

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

why g pushback index i , i do not see connection

»
7 weeks ago, # |
  Vote: I like it -10 Vote: I do not like it

I got WA in C's submission and i don't even know where is the problem. can anyone help me ? Please.

include<bits/stdc++.h>

using namespace std;

define ll long long int

define N 100005

define mp make_pair

define pb push_back

define f first

define se second

int main() {

ll t,i; cin>>t; while(t--) {
pair<ll,ll> pi; map<pair<ll, ll>,ll> visitedPoints; ll n,min=1e9,ml,mr,l=1,r=0; cin>>n; string s; cin>>s; ll x=0,y=0; pi.first=0; pi.second=0; visitedPoints[pi] = 1; for(i=0;i<n;i++) { if(s[i]=='L') x--; else if(s[i]=='R') x++; else if(s[i]=='U') y++; else y--; pi.first=x; pi.second=y; if(!(visitedPoints.find(pi) != visitedPoints.end())) visitedPoints[pi] =i+2; else { r=i+1; if(min>(r-visitedPoints[pi]+1)) { min=r-visitedPoints[pi]+1; ml=visitedPoints[pi];mr=r;

}

    }
 }
 if(r==0)
    cout<<"-1"<<endl;
 else
{

    cout<<ml<<" "<<mr<<endl;
}

} }

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Could anyone explain what is the least decreasing subsequence in problem E2

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

Could someone please tell me what's wrong with my code for problem C?

https://codeforces.com/contest/1296/submission/70414626 Edit: nevermind got it.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain why in E1, the actual problem is to divide the string into two subsequences that both of them are non-decreasing? Thanks!

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Fighting With Monster:

h[i] = ((h[i] + a — 1) / a) — 1; Can anybody be kind enough to explain this line to me?

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

    ((h[i]+a-1/a))=ceil(h[i]/a)

    now code is

    h[i]=h[i]%(a+b) //it clears all extra moves

    if(h[i]==0){h[i]=h[i]=a+b;} /*if !=0 then we have some power left so we dont need to do so*/

    h[i]=ceil[h[i]/a]-1 // this counts the skips we want to make with opponent

    eg: h[i]=10,a=2,b=3 h[i]=10%(a+b)=0;

    h[i]=0+a+b=5;

    ceil[5/2]-1=3-1=2;

    now, 5-2=3 skip...1st 3-2=1 skip...2nd 1-2<0 hence a kills monster

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Another cool trick for Problem C avoiding maps with pairs as keys.

Let's replace all the L elements with -1, the Rs with +1.

Similarly, replace all the Us by -1,000,000 the D's by +1,000,000.

The problem is to find the shortest subarray with 0 sum.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the solution for Problem C??

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

    We want to remove the minimum-distanced subsequence that does not affect the path. That is, a sequence of letters starting from a position and ending at the same position — included in the whole path, AKA a Cycle. We want to store the starting index of the Cycle starting at any position. so while iterating over the letters, keep updating the current position and its starting index depending on the current letter. Initially the position is (0,0) and the starting index is 0. If the first 2 letters are "UD", In the first iteration the position will change to (0,1) and the starting index of (0,1) is 1 because you will continue the path from position (0,1) depending on the letters starting at index 1. In the second iteration the position will change to (0,0) and the starting index should be 2. Now, this is a Cycle. so maintain a visited map to know if the current position is previously visited. If it's visited, then that is a Cycle, Check if the length of the Cycle is less than any previous one, so maintain a res int which stores the min length of a Cycle — initially it can be infinity — INT_MAX, and when a Cycle is found just check if the distance is less than res, If it is, then set res to that distance and set l to the starting index of the current position which is the starting index of the Cycle and set r to i which is the ending index of the Cycle, if it's not visited, mark it as visited. Be sure to update the starting index depending on the position in both cases to guarantee a min-length Cycle. For example if the path is "URDLUD", "URDL" forms a Cycle of length 4, "UD" also forms a Cycle of length 2, so the second is minimum. if the starting index of position (0,0) is not updated after finding the first cycle, the second Cycle's length would be 6 rather than 4, and that is wrong. Finally if the distance is infinity, that means that no Cycles were found, so the answer is -1, else the answer is l r.

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks a lot for the explanation with starting index update. Overlooked that case and didn't get AC during the contest.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone please explain me the formula for getting the minimum numbers of secret techniques applied( in each test case) in question D?

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

Thanks for the nice set of problems. In problem 1296D - Fight with Monsters, it was understood implicitly that each player hit decreases the health points of the monster by the hitting power of this player. Nonetheless, it might have been worthwhile to mention this rule explicitly in the problem statement.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain me problem C(Walking Robot)? In simple words.

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

    We want to remove the minimum-distanced subsequence that does not affect the path. That is, a sequence of letters starting from a position and ending at the same position — included in the whole path, AKA a Cycle. We want to store the starting index of the Cycle starting at any position. so while iterating over the letters, keep updating the current position and its starting index depending on the current letter. Initially the position is (0,0) and the starting index is 0. If the first 2 letters are "UD", In the first iteration the position will change to (0,1) and the starting index of (0,1) is 1 because you will continue the path from position (0,1) depending on the letters starting at index 1. In the second iteration the position will change to (0,0) and the starting index should be 2. Now, this is a Cycle. so maintain a visited map to know if the current position is previously visited. If it's visited, then that is a Cycle, Check if the length of the Cycle is less than any previous one, so maintain a res int which stores the min length of a Cycle — initially it can be infinity — INT_MAX, and when a Cycle is found just check if the distance is less than res, If it is, then set res to that distance and set l to the starting index of the current position which is the starting index of the Cycle and set r to i which is the ending index of the Cycle, if it's not visited, mark it as visited. Be sure to update the starting index depending on the position in both cases to guarantee a min-length Cycle. For example if the path is "URDLUD", "URDL" forms a Cycle of length 4, "UD" also forms a Cycle of length 2, so the second is minimum. if the starting index of position (0,0) is not updated after finding the first cycle, the second Cycle's length would be 6 rather than 4, and that is wrong. Finally if the distance is infinity, that means that no Cycles were found, so the answer is -1, else the answer is l r.

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

problem e, any two neighboring (!!!) neighboring, is the key word for me, I've missed that word

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

E1 can also be solved using bubble sort because it's based on swapping successive elements. All elements that are swapped should have different colors.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone pls explain E2?

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone here suggest me how to solve questions like F.I can't do such type of questions(which include graphs and trees).Pls help!!!

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

The n^2 solution to F TLE on test case 271 in Java. I was able to have it just about pass by lazily computing the parent arrays instead of precomputing all of them.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Could anyone explain me how the formula h[i] = ((h[i] + a — 1) / a) — 1 came in Question D?

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If you want to calculate ceil(X/Y) then you do this: (X+Y-1)/Y, this works because division is rounded down if you cast the result to int

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why problems aren't rated yet?

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

В авторском решении мы сортируем монстров по значению секретной техники. Но в условии говорится, что бой идет от первого к последнему поочередно. Или я что то не так понял. Объясните кто нибудь. Спасибо.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We sort it to find out cheapest set (in terms of secret technique usage). We will kill monsters in original order but only on those which are in that set we will use secret technique.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it possible to solve F with BFS modified to get the shortest path? My solutions timeout.

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

Did anyone solve problem F in python? I'm getting exceed memory limit on test 148, mostly solution is same as in editorial. solution

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D, how did u get number of secret techniques to be ceil(h/a) — 1 ? Noobie here.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

There is a much more elegant solution to E2. Assume we are processing a certain character at an index say i. Also assume that the previous characters have been alloted best possible colors. Now in order to give this the best possible color we need to consider some possibilities such as the color given to it should not have been given to any character lexicographically greater than it. Now in order to achieve this we consider the mex or the minimum possible color that we could give it. To find the mex, we make sets consisting of : {z} , {z,y} , {z,y,x} and so on till {z,y,x,...,a}. We will put the minimum possible values that have not been given to any character in the specific set. Then if we have this info the color is easily found bu using the set {s[i] + 1 — 'a' , ... ,x,y,z} . Then comes update. It is pretty easy too. Increase all the sets before the current set if their value is lower than the current color. https://codeforces.com/contest/1296/submission/70695446 . If anyone has further queries they are more than welcome.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In the F problem isn't it colouring the graph nodes i.e finding the chromatic number of the graph which is np hard algorithm

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone please explain problem D solution? I understand that we need to sort the array based on the minimum number of secret techniques needed, I also understand that if H%(a + b) == 0 then the enemy is the one who ends up killing the monster; however, I'm having trouble understanding how to calculate the needed K moves for each monster.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

We can solve E2 by DP:

Solution
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

why my code is accepted (E2) Should it give time limit exceeded error.. void solve() { long long n,i,j,k,l; string arr; cin>>n>>arr; std::vector v; set st; char last[n]={'a'}; for(i=0;i<n;i++) { for(j=0;j<n;j++) { if(arr[i]>= last[j]) { v.push_back(j+1); last[j]=arr[i]; st.insert(j+1); break; } } } cout<<st.size()<<endl; for(i=0;i<v.size();i++) cout<<v[i]<<" "; return; }

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
  • So excited! for E2 i think i get a really easy way to solve.
  • the main idea which inspires me is MikeMirzayanov's tutorial in E1 Note that the actual problem is to divide the string into two subsequences that both of them are non-decreasing and the beautiful greedy solution.
  • for E2 we just need to divide the string into more parts, so why not we repeat and continue the E1's greedy work.
  • here is my submission
  • the key part is the double loop by which we can find the first character no bigger than s[i] in array k ,once we find ,the work is just the same as E1.
  • Also there is another important thing. Though it's a double loop, the time complexity actually is not n^2 thanks to the second loop variable j is within 26(so the size of k doesn't need 2*10^5). and this promise that it won't TLE.(you can rewrite it by a binary search if you like)
  • though i can't exactly explain why greedy still works .Hoping for someone to add.
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    well i find i'm not the only one to find this. never mind

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For E1,you can just connect the inverse counts(j<i and str[j]>str[i]) and see if this is bi-partitie graph

71648393

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In E1/E2 Can someone explain the proof that number of colors is equal to number of non decreaing subsequences?

»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain the solution of problem A. i am unable to internalize it . I can understand that even if i replace ai with aj the sum of the array will remain same . Therefore why i need to change the parity of some numbers? Why not just check the sum is odd or not?