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

tourist's blog

By tourist, 3 years ago, In English

Hope you enjoyed the round! Editorials for all problems are out now. Also check out ecnerwala's stream where we went through individual problems and discussed the contest as a whole: https://www.youtube.com/watch?v=5Q4tGWT7p7I.

Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Vote: I like it
  • +349
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
Rev. 3   Vote: I like it -11 Vote: I do not like it

The solution to Problem C : (driven by observations and stuff) quite similar to the editorial :122867887

the variables stagesa stands for mine(in problem) and stagesb stands for Iliya's stages( can be thought as pointers) !

Hope its helps !

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

    hey , can u plz tell me why this approach fails as i m not able to figure it out since yesterday. thanks in advance.Link to soln

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

      The answer is n_new - n_old which is the additional stages.

      Also I am not sure that s_b += b[s]; is correct!! why s is < n-1!

      EDIT: modified solution

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

    Can I ask why so many downvotes?

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

There are some other approaches to problem D:

Maintain a set of numbers from 1 to n. This set will contain the remaining elements which can be used.

First, place all the first occurring numbers to their corresponding indexes and mark them visited. For example, if array A is : {6,6,6,1,1,1} , then after the first step our B array should look like this : {6,0,0,1,0,0} , i.e., we placed the first occurring 2 and 1 at the same index for now. Since we placed 2 and 1 so remove it from the set. Set will contain {2,3,4,5}

Now traverse from left to right, when a particular index is not visited, then we have to place some value at that index. I will take out the first element from set (you can take out any remaining element, doesn't matter) and let that be val. Now if val != index then we can simply put that value at the current index and move forward. If val == index, then first look up the position of a[cur_id] and then place val at pos[a[cur_id]] and a[cur_id] will contain the correct or initial value.

In the given example, we will go to 2nd index (as its not visited), take out first element from set which is 2 ... index==2 so check for the expected value at index 2 which is 6 and we have placed 6 at index 1. So, swap these , i.e, place 2 at index 1 and 6 at index 2. Now move forward, index 3 is not visited. Take out first element from set which is 3 ... Expected value 6 .. position of 6 : 2nd index , so place 3 at 2nd index and 6 at index 3. Now we will go to index 5, Take out first element which is 4 . Index != 5 so place 5 at that index and move right.

Hope it helps
My AC Code : https://codeforces.com/contest/1530/submission/122867049

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

    I could not get AC during the contest as I was storing the positions of elements in a boolean vector :XD. I could not find this small bug :(

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

    I knew this and couldn't implement :( Can you tell me why it's working?

    Like in this approach why there won't be a case s.t. for last remaining element index==val ?

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

      I'll try to explain why it works. Let's consider two cases. Case 1 is when n is 1 and so no assignment is possible. Now n > 1. Let's say that in the end, you have an index for which b[i] = i. Now, observe that a[i] will always be different than i (Given in question that we cannot gift ourself). So, if b[i] is i and a[i] is not i then it means that a[i] != b[i].

      Now, a[i] != b[i]. Notice that a[i] has been placed already in the result (why? Because if a[i] was present only once, we would have picked it in earlier loop greedily.) So, we just bring a[i] here at this pos and send this value to where a[i] was chosen for. It will become clear from the example. Now, let's take the second test case (1-based indexing).

      Index     1 2 3 4 5 6 7
      a    =    6 4 6 2 4 5 6
      res  =    6 4 0 2 0 5 0  // Filling only if we encounter first time
      pos  =    0 4 0 2 6 1 0  // pos[i] denotes index where we placed i
      
      Now, keep one pointer at first 0 from start of pos and iterate on res. If res[i] = 0, place the pointer value there and increment pointer till we are at another 0.
      
      So, pointer is at 1 (in pos array).
      Let's iterate over res.
      index = 1, res[1] != 0, so move forward
      index = 2, res[2] != 0, so move forward
      index = 3, res[3] == 0, so assign res[3] as 1 (pointer points to 1) and move pointer along until we encounter another 0. So, now pointer points to 3.
      index = 4, res[4] != 0, so move forward
      index = 5, res[5] == 0, so assign res[5] as 3 and move pointer to 7.
      index = 6, res[6] != 0, so continue.
      index = 7, res[7] == 0, so assign res[7] as 7.
      

      But, the last one won't fit well.Since, res[7] = 7 is not allowed. So, see what was at index 7 in original array. a[7] was 6. So, make res[7] as 6 and wherever 6 was placed, place 7 there. I hope this is clear. If not, let me know.

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

    thanks for your approach it helped me.

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

    u rote "first occurring 2 and 1" instead of "6 and 1" at line 6 of ur comment. Update : also im getting runtime error on test 3(I have followed the same approach as yours). Pls check and tell me if u have time! https://codeforces.com/contest/1530/submission/130407870

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

Interesting problems, especially E.

Thanks for contest!

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

    can u pls explain the solution for E...pls

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

      I think that Editorial of E is pretty good, but I'll try to retell it with more explanations.

      In this problem, you do not need to know various complex algorithms, just analyze the problem statement and try to figure something out.

      So, first of all, we need to consider two simple but important cases (same as Editorial).

      1. When all characters are the same, it is senselessly to shuffle them, because $$$f(t)$$$ will always be equal to $$$|s| - 1$$$ (here and further $$$t$$$ is our final string).

      2. Let's try to figure out when $$$f(t) = 0$$$. We can achieve it only when $$$t[0]$$$ is unique. That's why let's find the lexicographically smallest character, which is unique in $$$s$$$, and put it on the first position of $$$t$$$. Then, we can complete $$$t$$$ with other characters of $$$s$$$ in lexicographic order. So $$$f(t) = 0$$$ and the string is lexicographically minimal.

      I hope previous part was simple for understanding, because now we will consider more interesting cases. But it is still a retelling of Editorial.

      We considered cases, when $$$f(t) = 0$$$ and $$$f(t) = |s| - 1$$$. Now I claim that $$$f(t)$$$ for other cases is equal $$$1$$$. Maybe it's hard to believe, but it's true. Let's try build $$$t$$$.

      Let's find the smallest character and call it $$$a$$$ (It may not be equal to 'a' like character, just convenient). $$$a$$$ will be first character of $$$t$$$. We need $$$f(t) = 1$$$ and lexicographically minimal $$$t$$$ so $$$a$$$ is the best option. Then we need to choose second character of $$$t$$$. And here some interesting cases:

      1. Lets consider if second character is also $$$a$$$. Now $$$t = aa + something$$$. And we can't have in "something" $$$aa$$$, because then $$$f(t) >= 2$$$. That's why we need to place $$$a$$$ through one: aa?a?a?a?a?a????? (here ? is some characters, which are not equal to $$$a$$$). It is easy to understand that in this case we need at least $$$cnt[a] - 2$$$ other characters ($$$cnt[a]$$$ is the number of $$$a$$$ in $$$s$$$). If we have it, everything is great, and the answer is lexicographically minimal. But else we can't have $$$t = aa + something$$$.

      2. Now, when $$$aa$$$ beginning is impossible, let's find other lexicographically smallest character and call it $$$b$$$ ($$$t = ab + something$$$). As in the previous paragraph we can't heve ab in "something". And here 2 cases (it's almost over, I promise).

        2.1. If we don't have any characters except $$$a$$$ and $$$b$$$, the only possible answer is t = abbbbbbaaa, because else we will have ab in "something": t = abaaaaaABbbbbb.

        2.2. If we have other character, everything is perfect because we can do this: t = abaaaaa?bbbbbbb??????. We just separated ab and $$$f(t) = 1$$$. But or course, ? shound be lexicographically sorted.

      I hope it was useful for you. I really tried my best.

      Here is my C++ solution with comments: 122932141

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

        thanks man, got it.

        the thing is as i read question in contest, i start a mathematical approach and don't try many cases, which makes a easier prob hard for me. If u have any thing to guide then pls share. :)

        thanks once again :}

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

    I am sorry but what exactly was interesting in problem E ?

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

      He found interesting the fact that this kinda C problem was so overrated and placed on Eth position) IMHO D was much better and maybe harder than just a case recognition like in Eth one.

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

        kinda C problem

        I am probably sure algo-police is on the way after you saying that :/

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

        So you solved the better and harder D but seem yet to recognize all cases in E, huh?

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

          Better means more interesting. And yes you're right lol)))) I didn't manage to solve E but not due to the the case recognition but because of a stupid mistake that I made in one of the cases. And yes, in my opinion "if else" in E is less interesting than a plain dfs like in D. But ok, the whole this discussion is strange so, idk)))

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

Another Solution for D : First, Place all the values of b[i]=a[i] where a[i] is chosen to given gift by only one member

Then, Those who are desired by more than one person give them any random person as it wont matter (Explained later).

Then, maintain of set of variables who have not yet received any gift from any person and start from index 0 and the person who hasn't chosen yet ,give him a gift not equal to itself i.e either beginning element of set and ending element of set.

Now comes the main part u should notice that there can be atmost one value equal to itself and and the person whom this index wished to give a gift must have atleast 2 person desiring him so simply just find another index with same value of a[i] and just swap the two and you will acheive the desirable state.

Solution Link

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

    Thanks man! yes,I had to go through a crazy implementation to do this, but smhow did it!

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

kuhn algorithm work for D in 250 ms.it is believed that asymptotics for kuhn is O(NM) howewer in practice it is quite close to liniar.

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

As I see in other contestants' code, most popular solution for F is some kind of DP.

I have just passed straightforward O($$$2^n \cdot n^2$$$) solution (brute force + OR-convolution).

Even with whole bunch of pragmas it 122869425 barely fits in TL :). Was it intended to catch TLE, or my implementation is bad?

UPD: I optimized brute-force part 122870796 , now it fits well, but I'm still interested if it was intended to pass or not.

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

    The intended complexity is $$$O(2^n \cdot n)$$$ with inclusion-exclusion. Distinguishing it from $$$O(2^n \cdot n^2)$$$ is quite hard though. The time limit was set with the intention to allow any $$$O(2^n \cdot n)$$$ solution and cut off most $$$O(2^n \cdot n^2)$$$ solutions.

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

      That's reasonable. Thanks for your reply.

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

      What was the reason for the strange modulo?

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

        I think the modulo was chosen so you can do everything in int, which might make certain solutions run faster considering how much modulo multiplication is involved.

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

          That's what I thought — but I resubmitted my solution with long long, and it actually ran slightly faster!

          Maybe C++ is smart enough to somehow know the numbers are small and use the faster int operations regardless?

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

            Another thing that a smaller modulo let's you use is the Barret Reduction to replace division operations in modulos with multiplication. 64 bit C++ automatically does modulo operations with multiplications (if modulo is constant) but this is helpful for languages such as Java.

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

        With modulo around $$$10^9$$$, submitting under 64-bit C++ compiler could give a 3-4x speed boost, and separating a 32-bit-compiled $$$O(2^n \cdot n)$$$ from a 64-bit-compiled $$$O(2^n \cdot n^2)$$$ was pretty much impossible.

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

For problem D, I was really glad to find a solution without using Graphs (since I am bad at Graph Theory). Hint: Try to satisfy as many wishes as you could (which is the number of different integers from the input). Then, we will have some people who do not have somebody to give a gift to. We can give them anybody who is not given yet. However, we should check if there is somebody who is matched with himself. It can be proven that in that case the optimal strategy is to satisfy the first "wish" of that person. Not really sure if you could fully understand me, tho. 122840888

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

    For persons getting matched to themselves I just exchanged their value to the person having the value that person wanted. I really can't see how its a graph problem.

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

Great Contest, thanks tourist. Highly appreciated

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

my solution to D.

It is a greedy approach and doesn't use graph. Hope it helps.

122817534

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

    Also can anybody link the problem variation where a person can have more than 1 wishes. I left it last time when I didn't know graphs. It would be a great help as I can't find it.

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

    swap(ans[b[a[i]]],ans[i]); explain this clearly

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

      here, see this solution, it's the same method as the guy, but I have added comments, which should hopefully help

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

Can somebody please explain to me why this code gets accepted, but during the contest I got on the same code WA? There is only one very small difference between those 2, the AC one has a forgotten cerr into it, you can check with a diff tool :)

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

Problem E really required careful case analysis. My solution got wrong answer on pretest 6 just because of missing a single -1. qwq

I think it is a nice problem to test participants' carefulness!

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

I really liked $$$D$$$. Construct directed graph $$$G$$$ with edge from $$$i$$$ to $$$j$$$ if $$$i$$$ wants to give a gift to $$$j$$$. Now store $$$2$$$ sets: $$$Unliked$$$ and $$$Popular$$$. A element $$$i$$$ is in $$$Unliked$$$ if $$$d_G^{-}(i) = 0$$$ and in $$$Popular$$$ if $$$d_G^{-}(i) > 1$$$. Now while $$$Unliked$$$ is non empty, take a Unliked person and a person who wants to give a gift to a Popular person and is not the same as the chosen Unliked person. Now just delete the edge from this person to the Popular person and add an edge from person to Unliked person. Remove this Unliked person from Unliked, and if the Popular person, is no longer Popular remove him from Popular set as well. An implementation is here: https://codeforces.com/contest/1530/submission/122822889

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

    great solution, I did it with randomization 122882331, it was very easy but couldn't do it during the contest... I was scared to see fewer submissions.

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

      Thanks, I'm still not sure why being random passes will look into it in some time I guess.

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

    Why are you adding an edge between the person and Unliked person?

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

      When we process elements of the Unliked set, we try to increase their indegree to $$$1$$$, by connecting them to people, whose connections are useless. Like the ones connected to Popular people. This is a greedy, straightforward solution that works. Hope you understand.

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

    Thank you !

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

ecnerwala Can you please upload the video the stream on youtube? Quality 1080p lags a lot with many of ours internet.

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

    Yes, will do tomorrow.

    Re 1080p: unfortunately, Twitch transcoding (quality conversion) is not guaranteed for Twitch affiliates, it's only priority, so whether there are lower quality options is out of my control. Hope it's available next time! I've heard it's prioritized by viewership, so it might be more likely since all of you showed up!

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

I did an overkill for C. I used an ordered_multiset. Though I feel a bit stupid, I think the template I used is pretty amazing : 122832592.
This would actually be useful in solving a more general problem: lets say instead of predicting in how many minimum moves we can win, the game continues with different scores being added to each and we need to find the move at which our score will be atleast the opponent's. In this case we would require (or atleast this is one way) order statistics on our multiset.

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

The promble E 1530E - 12 - Minimax, I got a wrong answer on test 2 with this checker log:

wrong answer 48th words differ — expected: 'ff', found: 'ff'

I don't know what is that means.

122886321

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

    can u pls explain E...pls

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

      sorry... I don't think I have words better than the editorial. And, I havn't pass yet. QAQ

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

    For the ff test case, you are printing an extra character with ASCII code 0 after ff. If you print t.size(), you will see that it is 3.

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

So I used the exact idea that the solution mentions, however I can't figure out (for literally hours) what is wrong with my code since everything I coded seems logical. Can anyone help me please, thanks in advance!

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

Sad to see that simply changing long long into int can make a huge difference to not only the result but also my current rating, though my solution has a complexity of 2^nn^2 (actually it is 2^{n+2}n^2!).

TLE : 122856541

AC : 122887934

btw how to type LaTeX in Codeforces?

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

    Put them into $$ symbol. For example, $$$2^{n+2} n^2$$$ will be $$$2^{n+2} n^2$$$ (only 1 is enough tho, the math engine rendered it 3 times somehow)

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

      Thank you very much.

      Well actually I did so, but there might be something wrong with my operation just now so that when I previewed the comment the symbol $$ didn't work.

      Now it works. $$$\mathcal{O}(2^{n+2}n^2)$$$

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

In problem D, my code is of order O(n) but still it took 1918ms (phew!). Can someone tell me why?

Algo

v stores the input. flag is 1 for the positions which are requested and it also stores who requested them. left stores the positions not requested by anyone. v1 stores the output. flag1 stores which numbers are used in real time.

If the requested number has not been used, then we use it. Else, we use the left array. If this number is equal to its position, we swap it with the position which has the number it requested.

Code: 122834097

PS: Sorry for such a trivial question. Just started learning STL.

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

My solution for problem D.

First of all we store each element's frequency in an array .

Then We traverse the array and each element that its frequency is 0 we store them in a deque (you will understand why deque in a bit).

Next We traverse the array (doesn't matter from left to right or from right to left) and we look for some cases:

  1. If the frequency of whom person i wants to gift is 1 , then we give him it , OR there is only 1 number left in the deque , and it equals to i , then we give i a[i] .

  2. if the above cases are not satisfied , then we look to the deque.

if the first element in the deque is equal to i , then We give him the last element , else we give him the first element .

Finally the answer is the number of elements in the array (n) minus the number of elements from 1 to n that there frequency is 0 .

CODE

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

A solution for problem C. Simple and Easy to understand, Hope it helps ! Submission Link — 122895932

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

Just did D a little different so I thought I'd comment how out here (in the loving memory of my multiple wrong submissions prior to the AC UwU)

Do correct me if I'm wrong anywhere, and I apologize if it's a really inferior approach to be explaining and/or very poorly explained.

Okay so what we do know is that the numbers appearing more than once in the array need to be replaced with the ones between $$$1$$$ to $$$n$$$ that are not appearing at all (since everyone must get a gift). It is given that no employee initially is assigned to themselves as secret santa, so the only self assignments that can potentially be caused would be because of us replacing repeated numbers with the absent ones. This self assignment can be easily avoided as shall be discussed in the approach:

Intuition:

Let the given array be called $$$a$$$. Firstly we make a list of numbers that are absent in $$$a$$$ (let's name it $$$se$$$) and also maintain an array to count the number of appearances of the integers $$$1$$$ to $$$n$$$ in $$$a$$$ (say $$$b$$$). Now we traverse $$$a$$$ starting from index $$$0$$$ (iterator of $$$se$$$ starting also from the first element of $$$se$$$) and each time the number we encounter in $$$a$$$ has more than $$$1$$$ appearances indicated by $$$b$$$ we replace it with a number from $$$se$$$ and update its count in $$$b$$$ decrementing it by $$$1$$$ and moving the iterator of $$$se$$$ to the next unused number in it.

Carrying out the Replacement:

Since as has been explained in the editorial, the maximum fulfilled wishes will always be the equal to the number of different integers in the given array, the order of replacement is not of any consequence as long as we are cautious (while replacing repeated numbers with those form $$$se$$$) about not assigning the employee as his own secret santa, i.e. the number we choose from $$$se$$$ for the replacement must not be equal to number of the employee.

Among the numbers in $$$se$$$, there will at most only be one such number for each employee that could result in self assignment. Thus while iterating through $$$a$$$ (suppose we're at index $$$i$$$) and $$$se$$$ (suppose the iterator points to $$$j$$$-th element), if the number of appearances of $$$a_i$$$ are more than $$$1$$$ in $$$b$$$ we can encounter two possibilities:

  1. Employee number is equal to $$$j$$$-th element of $$$se$$$.

  2. Employee number is different than $$$j$$$-th element of $$$se$$$.

In case of the second possibility, we can replace $$$a_i$$$ with the $$$j$$$-th element of $$$se$$$ and increment $$$j$$$, thus eliminating the possibility of assigning the same number initially absent in $$$a$$$ to more than one employees. In case of the first possibility however, we replace $$$a_i$$$ with $$$j+1$$$-th element of $$$se$$$, since $$$j$$$-th element remains unused, we swap the $$$j$$$-th and $$$j+1$$$-th elements of $$$se$$$ and increment $$$j$$$. This results in the next element we encounter through the iterator of $$$se$$$ being the originally $$$j$$$-th element hence prevented from being skipped.

Code:

122890172 (my very unclean submission I suppose.)

Time Complexity:

It would take this $$$O(n)$$$ to reach an answer as the maximum number of runs the inner while loop performs is 2, a constant. (I sure do hope I'm not wrong)

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

Problem B simple explanation Putting Plates

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

Problem A Simple Explanation Problem A

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

Short code for B (Perl) — 122869086

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

Can some tell me what is wrong with my code I am getting a WA on C.

#include<bits/stdc++.h>
using namespace std;
#define     all(x)          x.begin(),x.end()
#define     rall(x)         x.rbegin(),x.rend()
#define     ll              long long
#define     ld              long double
#define     precise(x)      fixed<<setprecision(x)
#define     mb              make_pair
#define     pb              push_back
#define     ub              upper_bound
#define     lb              lower_bound
#define     t()             int t;cin>>t;
#define     pll             pair<ll,ll>
#define     vl              vector<ll>
#define     vll             vector< pll >  
#define     fast            ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define     ff              first
#define     ss              second
#define 	pf 				push_front
#define     pq              priority_queue
int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1}; 
int dy8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dx8[] = {0, -1, -1, -1, 0, 1, 1, 1};

string yes = "YES";
string no = "NO";
ll mod = 1000000007;
ll MAXN = 100001;

void print(vector<ll> &a)
{
	for(auto i:a)
		cout<<i<<" ";
	cout<<endl;
}

void print(vll &a)
{
	for(auto i:a)
		cout<<i.first<<" "<<i.second<<endl;
}

void print(vector<vl> &a)
{
	ll n = a.size();
	ll m = a[0].size();
	for(ll i=0; i<n; i++)
		{
			for(ll j=0; j<m; j++)
			{
				cout<<a[i][j]<<" ";
			}
			cout<<endl;
		}
}

bool isprime(ll x)
{
	for(ll i=2; i*i<=x; i++)
	{
		if(x%i == 0)
			return false;
	}
	return true;
}

void factor(vl &fac, ll n)
{
	ll temp = n;
	for(ll i=2; i*i<=temp; i++)
	{
		if(n%i == 0)
		{
			fac.pb(i);
			while(n%i == 0)
				n /= i;
		}
	}
	
	if(n>1)
		fac.pb(n);
}

void solve()
{
	ll n;
	cin>>n;
	
	vl a(n,0), b(n,0);
	ll sa = 0, sb = 0;
	
	for(int i=0; i<n; i++)cin>>a[i];
	for(int i=0; i<n; i++)cin>>b[i];
	
	sort(rall(a));
	sort(rall(b));
	
	int k = n-n/4;
	for(int i=0; i<k; i++)
	{
		sa += a[i];
		sb += b[i];
	}
	
	if(sa>sb)
		{
			cout<<"0"<<endl;
		}
	else
	{
		int temp = n-k;
		int index = k;
		int ans = 0;
		while(sa<sb)
		{
			sa += 100;
			if(temp>0)
			{
				sb += b[index];
				index++;
				temp--;
			}
			ans++;
		}
		cout<<ans<<endl;
	}
}

int main()
{
	fast;
	bool test_case = true;
	
	if(test_case)
	{
		ll t;
		cin>>t;
		
		for(ll i=1; i<=t; i++)
			{
				solve();
			}
	}
	else
		solve();
	
	return 0;
}
  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    you only add something to sb but sometimes sb should be decreased.

    counterexample :

    1

    7

    0 0 100 100 100 100 100

    100 100 100 100 100 100 100

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

    Please try to use spoiler tag before posting long codes.

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

      Even better, post a link to your submission, then we can see the failed tests.

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

    The number of values dropped should be $$$\left\lfloor \frac{n+ans}{4}\right\rfloor$$$ not $$$\left\lfloor \frac{n}{4}\right\rfloor$$$

    To implement this you need to treat every fourth step differently. When

    (n + ans)%4 = 0

    you shouldn't add to sb, but should subtract the smallest remaining value from sa (after adding 100 to it).

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

For problem C, it's also possible to do a binary search on how many exams are needed. It's O(n) complexity to answer "Take X more exams, if I can have a no-lower score or not"

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

Can anyone please help with problem C, what's wrong with my solution submission ?

I've tried many times, couldn't find the issue.

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

    It looks as if you are taking too few values from Ilya's results (array b). You are, in effect adding 100s to array a and 0s to array b. Ilya wants to count his best results so as the total number of stages increases the number of non-zero entries counted in array b should increase, but in your code it is decreasing.

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

My simple solution for D , without using any sort of graphs: First try to assign each person, his choice if that choice has not been assign yet, maintain a bool vector to store the gifts which have been assigned and index array to store indexes which have not been assigned any gifts yet. Now construct a set containing gifts which have not been assigned. Now iterate for each index, if that index has not been assigned gift,then,there are two cases (i) first element of set is not equal to current index ,then assign that gift and erase it from set. (ii) Its equal to current index , since atmost 1 gift can be equal to current index,then we will assign next gift to current index and erase it .Now if set contains only 1 element and its equal to current index ,then we will swap the gifts of current index and index which has been assigned the choice of the current index ,this will not affect the final answer

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

Actually we can brute force C: 122875589

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

tourist Any updates on the editorial for the problems F,G,H?

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

    i'm sure that he is working hard to catch up with it. be patient please

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

I have different solution for D:
First of all, lets construct bipartite graph with edges from i (left side) to a[i] (right side)
It is clear, that answer is maximum matching in this graph + some extra edges
Lets find maximum matching and fill $$$answer$$$ with it
Now we have some people, who doesn't give and who doesn't recieve gifts
Lets assign them to each other and if we got collision that $$$i$$$ should give to $$$i$$$, then just swap that $$$i$$$ gives to $$$a[i]$$$ and someone who gives to $$$a[i]$$$ gives to $$$i$$$
It works in $$$O(MaximumMatching) + O(n)$$$. My $$$O(nm)$$$ Khun implementation (based on this Burunduk1's article) works under 400ms: 122962186.

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

Please update editorial for problem F. Or can someone help me with it ?

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

    Try this:

    $$$ F(S)=\sum_{T\subseteq S,T\neq \emptyset } (-1)^{|T|-1}G(T) $$$

    where $$$F(s)$$$ means the probability that there exists a element in $$$s$$$ satisfies the conditions,$$$G(s)$$$means the probability that all elements in $$$s$$$ satisfy the conditions .

    This also right for:

    $$$ G(S)=\sum_{T\subseteq S,T\neq \emptyset } (-1)^{|T|-1}F(T) $$$
»
3 years ago, # |
Rev. 2   Vote: I like it -36 Vote: I do not like it

:3

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

Can anyone explain their DP solution for F ? The one which is $$$O(2^{n} n^{2})$$$

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

    I think it is 1 — P(no line is ok):

    $$$dp_{i,mask}$$$ means :consider the i-th row and the columns which have no failed cell is mask (mask also record whether the diagonal is ok).

    And do the "And convolution" is $$$O(2^nn)$$$ for one row .

    Totally in $$$O(2^nn^2)$$$

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

      Thnaks for your reply. Can you provide some resource on "and-convolution" ? Is this related to fft ?

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

        You can search "Fast Walsh Hadamard Transform". I only have Chinese resource : oi-wiki.

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

    After inspecting ecnerwala's solution I think he used this state:

    $$$dp[i][mask]$$$ = what is the probability that after having considered the first $$$i$$$ cells (using a snake index from left to right, top to bottom) the cols/diagonals that can still be winning are represented by $$$mask$$$, and we haven't won any of the rows so far.

    (but with space saving trick to reduce memory)

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

In problem F, to optimize the solution to $$$O(2^n \cdot n)$$$ using the first way described, how to actually achieve that complexity? Wouldn't updating the products and rolling back (in $$$O(n)$$$) for each possible state of $$$f(i, S)$$$ calculated recursively (for which there are $$$(n + 2) * 2^{(n + 2)}$$$ states) take $$$O(2^n \cdot n^2)$$$ in total?

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

    At level $$$i$$$, there are $$$2^{i-1}$$$ states, resulting in $$$2^0 + 2^1 + \ldots + 2^{n+2} = O(2^n)$$$ states in total.

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

Can anyone explain the thought process of reducing problem F from 2^(2n+2) to 2^(n+2) if one is following the basic inclusion-exclusion process?

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

does E really **** interesting ???

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

Greedy solution for problem D:

First, iterate through a[i] and greedily assign giftees. If a[i] is already taken, do nothing. Additionally, the maximum number of satisfied people is simply the number of unique elements, so we can calculate that here too.

This leaves a lot of people that still need to find a person to gift to. We can again greedily assign them using a 2 pointers method.

Now everyone should be paired up, but we run the risk of pairing someone up with themself. We will iterate through the current answer to find such scenarios. Let's call a person who gives a gift to himself x. If that occurs, we can simply swap him with the person who had originally taken his intended giftee. Let's call the person who took x's intended giftee y. This swap will always retain the optimal answer, because we are now satisfying x's requirement, and breaking y's so there is a net change of 0 requirements met. The construction of this candidate solution via the previous 2 steps also guarantees it contains no duplicate elements, so the swap also cannot make another self-match.

This process can continue until all self-matches are eliminated, and we are left with a valid, optimal answer.

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

Can anyone please explain the Proof for problem B.Not able to understand the proof from Editorial

  • »
    »
    5 months ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it
    • probably building strength in math might help you to understand editorials ? E is newB ? --
    • Building Inception thinking also might help Dream within Dream within Dream and so on.. 2-color board 3 color board and so on..
    • Moving a bit back and froth in your direcion is level 1
    • Taking is a diversion from your path is level 2
    • I dont know levels beyond it, never encounterd a problem while practising