By PikMike, history, 4 weeks ago, translation, In English,

Hello Codeforces!

On Nov/13/2019 17:35 (Moscow time) Educational Codeforces Round 76 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 7 problems and 2 hours to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir Vovuh Petrov, Ivan BledDest Androsov, Maksim Ne0n25 Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Our friends at Harbour.Space also have a message for you:

Attention Codeforces!

Calling on all tech disruptors, data specialists and computer science pioneers.
We are offering fully-funded international scholarships for exceptional tech specialists from around the world. Accelerate your career by becoming an industry expert capable of making key data-driven decisions that add value and drive innovation within tech industries.

Harbour.Space University has partnered with SCG, a leading business conglomerate in the ASEAN region, to offer exceptional tech specialists the opportunity to work and study in two of the most dynamic and vibrant cities in the world. Join our progressive two-year program based in Bangkok, with 6 of the 24 months in Barcelona, to develop the international mindset needed to accelerate your career and redefine how data drives the businesses of the future.

Codeforces and Harbour.Space

Tuition fee:

2 years | €45,800

Education:

3 hours of study per day | 15h per week

Work Experience:

4 hours of internship per day at SCG | 20h per week

Living Allowance:

€16,800 euros | €700 per month living allowance


APPLY HERE→

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 neal 7 182
2 kmjp 7 216
3 socketnaut 7 218
4 KrK 7 225
5 ivan100sic 7 244
5 pwild 7 244

Congratulations to the best hackers:

Rank Competitor Hack Count
1 Aaman007 39:-10
2 liouzhou_101 59:-58
3 dzhiblavi 15
4 Rian_5900 31:-40
5 Fyodor 10:-2
278 successful hacks and 501 unsuccessful hacks were made in total!

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

Problem Competitor Penalty
A rahulDugar 0:00
B Siberian 0:02
C ZwariowanyMarcin 0:03
D LJC00118 0:16
E jjang36524 0:23
F TripleM5da 0:19
G black_horse2014 0:19

UPD: Editorial is out

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

»
4 weeks ago, # |
Rev. 2   Vote: I like it +26 Vote: I do not like it

Hope to become expert in this contest......

»
4 weeks ago, # |
  Vote: I like it +36 Vote: I do not like it

Strange that there's only one comment in 14 hours. Anyway, it's a PikMike contest so I'm excited. Hope I can finally get candidate master lmao.

»
4 weeks ago, # |
  Vote: I like it -37 Vote: I do not like it

hope to become specialist in this contest.

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

Hope to become 1500+ this contest.

»
4 weeks ago, # |
  Vote: I like it +21 Vote: I do not like it

Good Contest.

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

Were Segment Trees necessary in D? I had to do some maximum queries on the monster array, was too scared to try my solution without the tree.

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

    Well, i did a sparse table

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

    we can take the suffix max after sort the hero on the basis of its power and then take lower_bound.

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

      I've done that. I said maximum queries on the monster array

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

    Not necessary, Although I thought about Segment Trees first

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

    Overkill segment trees was not needed at all.

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

    no

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

    I think if you sort heroes' by power, you can calculate the maximum endurance for each suffix in O(m)

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

    I did it without Segment tree. Solution. Just sort, binary search and array for suffix maximum endurance

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

    Not at all. Just sort the heroes by endurance O(MlogM), than in O(N+M) build an array that stored at element i what is the maximum power between heroes with at least i endurance. Then simply loop the monsters array O(N) and with a single lookup it can be found if the current monster could be beaten up during the same day or it is needed a new day

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

    I did not use a segment tree or sparse table for this problem. You can check my solution: http://codeforces.com/contest/1257/submission/64838220

»
4 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

How to solve C?_

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

    The answer is the minimal distance between two equal elements.

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

      why

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

        If you check the subarray that is the answer to the task, you will see that it's first and last elements are equal (because it is the most optimal). And all the elements between them are all different.

        Sorry for my poor (maybe) English.

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

        If you look at two equal elements in an array then the only case where it is not dominant is if there is at least another pair of two inside. The equal elements that have the minimum difference between them cannot contain another pair because that would contradict that the elements we found have the minimal difference.

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

        because when you take two elements with minimum distance then between these two other element appear at most one.

        1231 if there is repeated value between two 1 then distance between 1 can't be minimum.

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

        Consider you have two suquences

        1 4 3 2 4 1

        Now here, we can choose the first 2nd and last 2nd element in a segment. That will form the minimum.

        and other,

        1 4 3 3 4 1

        Now here, if we choose the same indexes as an upper example, it would be wrong. Because we can still minimize the segment to {3,3}.

        So we can conclude that all we needed to do is minimizing the difference between equal elements. Hope you understood.

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

          why result is 4, 5, 4 for 4 1 2 4 5 4 3 2 1 and not 4 4 for example

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

            Because choosing a subarray should be contiguous.

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

            ****The subarray of a is a contiguous part of the array a, i. e. the array ai,ai+1,…,aj for some 1≤i≤j≤n.****

            you missed this line.

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

      Wow, I feel dumb now jury-rigging a two-way multimap keeping track of element counts and number of elements with the maximum count

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

    you have to find minimum difference between two repeated value. save the last position you get for each value and when you get it again take difference and update position of last appearence. then take minimum of all diference.

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

    We note that, there is a answer if and only if some number is repeated otherwise ans is -1.

    The shortest such subarray will be |start of that number(x) — another instance of that number(x)| so just count how many repeated numbers are there and print the minimum distance b/w them

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

    Implementation works: link

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

    I used two pointers which I later realized to be difficult to solve that problem.

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

In question D, codeforces giving different output than other platforms like hackerrank, onlinegdb for the same code. Output on codeforces is coming as 0 and -1 for the 1st test case but it is correct on other platforms. Does someone know why is it so

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

    It's an undefined behavior. For example if you donn't fill a local array explicitly, it doesn't have to be filled with zeros, it may be filled with anything depending of compiler.

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

    See diagnostics in your submission: "Error: attempt to dereference a past-the-end iterator." I had a similar solution with the same bug. That lower_bound returns the end of the map when there's no heroes with energy day or more left.

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

      Thanks a lot bro. code worked after handling this case

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

Seems not sorted by difficulty...

RIP my rating.

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

    It seemed very sorted to me. I won't say they were easy though, I might get hacked when I least expect it

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

F is just btuteforce, LOL. 100e9 in 2 seconds))

UPD 1: Hacked.

UPD 2: Added set, Accepted.

UPD 3: Passed final tests in 2.5 seconds.

UPD 4: More stable program with a run time 1.9 seconds: Link.

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

    Can you elaborate a little more please?

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 3   Vote: I like it -19 Vote: I do not like it

      Just implement the dumb checking described in the statement with some optimizations (pragma`s, shuffle, set and popcount is enough). Code.

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

    Bruteforce way can be Hacked, test cases are weak.

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

Good test cases on F, I tried my best to make random solutions pass and failed.

»
4 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

How to solve D???

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

    Greedy.Every day,choose a hero who can beat most monsters.

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

      Can anyone please elaborate on this? How to choose the hero who can beat most monsters? I did something in my solution but I find that to be too messy.

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

        Binary search on the hero. Solution

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

          I saw people's submissions where they were obtaining the suffix maximums over the max. powers needed for a fixed endurance value. I find that idea to be much less on code. I'd like to know about that idea as I am still not able to think about it.

          UPD: I have mentioned the idea in one of my comments below.

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

        Just sort the {power, endurance} array. Then start with the first monster and check maximum power needed to defeat the dragon(Binary search), also I have maintained a suffix array that will store maximum endurance. If we can defeat the dragon then try to take one more dragon on the same day otherwise start with a new day. Link to my Solution

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

    I implemented O(m*n), and though in worst case scenario there is no way it passes TL, it somehow got accepted.

    I sorted heroes in descending of their stamina, and for each hero in this order I tried to find maximum of monsters he can beat if he enters now (i.e. iterate mosters one by one and increase counter if monster is weaker and hero's stamina is not exceeded). I break cycles if I find a hero with lower stamina than my current maximum.

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

      We still are in the hacking phase, someone might try to break your code so it gives TLE, hopefully not!

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

    My approach is, at first I sort all the heroes in basis on their power and then endurance in decreasing order. Then I try to find out maximum power for every endurance. It always proves that endurance[i]>=endurance[i+1]. Finally, at every step, I just try to pick the longest endurance(using binary search) which can able to kill all the monsters on that range.(I use segment to find out the maximum monster value on that range). If there is any monster whose value is greater than the maximum hero's power then the answer is -1.

    My solution -> https://codeforces.com/contest/1257/submission/64846739

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

    I finally managed to understand the easy way to solve the problem by going through people's submissions. I'll try to explain.

    First, if we are currently at the $$$i$$$th monster, we have to choose a hero that can kill the largest no. of monsters. The only tricky thing is choosing that hero. Let $$$cnt$$$ denote the current no. of monsters that we can kill from the $$$i$$$th position. Initially, $$$cnt = 0$$$. Now, $$$cnt$$$ can be extended to $$$1$$$ iff there exists some hero whose endurance $$$\ge 1$$$ and the power is more than the power of the $$$i$$$th monster. Using this logic, we'll be extending $$$cnt$$$ as much as we can. To extend $$$cnt$$$ by $$$1$$$, we have to check to see whether there exists a hero whose endurance is $$$\ge cnt + 1$$$ and whose power is $$$\ge$$$ power of all monsters within the range $$$[i, i+cnt]$$$. If there does exist one, we can extend $$$cnt$$$ to $$$cnt + 1$$$.

    To check this thing, we can have an array we store the maximum power of a hero whose endurance is $$$\ge i$$$. This can be computed by taking suffix maximums on an array where the $$$i$$$th element is the maximum power of a hero whose endurance is $$$i$$$.

    Also, since we are always extending $$$cnt$$$ by $$$1$$$, we can instead keep a running maximum of monster's powers instead of using a data structure to obtain the maximum within that range.

    Code

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

      Hey roll_no_1, I did a similar thing as well, but in the other direction, so just putting my strategy here as well

      Invariant: If there is a hero with more power and more endurance, he is always better than anyone with both of these lower.

      Steps: Create an array that has the best weapon for each endurance -> update bestHero[endurance] = max(bestHero[endurance], power) and then place the suffix max

      This step would mean that at every value of endurance, the best value of power that is greater than or equal to the power for the range having more endurance is taken. (Greedy choice)

      Move from the back and kill the current monster, if you can't kill the current monster, along with the suffix, add 1, else, keep expanding the array backwards updating the maximum.

      Overall an order of O(n+m)

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

      I did solve with the same concept but with binary searching. keeping a max suffix array is much more cleaner. Thanks for sharing, I learnt something cool.

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

    You can solve the problem without using segment tree or binary search. http://codeforces.com/contest/1257/submission/64838220 Just a map and lower_bound is required

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

    I did a greedy solution. 64832445

    Explanation — sort heros according to endurance and allocate each monster a hero starting from max endurance, than start making maximum group possible.

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

Given the huge TL, I imagine my solution for G is off, but is it something like finding number of solutions to $$$\sum_{i=1}^d x_i = k$$$, where $$$d$$$ is the number of distinct prime divisors and $$$k$$$ is the minimum power of one of the prime divisors?

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

    k is actually floor(n/2).

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

      Upon further thought, it makes sense that it shouldn't be the minimum power of the prime divisors, but it's not at all clear to me why floor(n/2) encodes the proper information. Can you elaborate?

      EDIT: Just tried to verify this on the samples. Unless I'm misunderstanding what you mean by n/2, this doesn't seem to work.

      EDIT2: My implementation was wrong, tried to use stars and bars where I couldn't. My bad.

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

        n is number of prime divisors given in the input.

        Lets say (p1,p2,..,pd) are the distinct prime factors and (a1,a2,...,ad) are the powers of prime factor. Now you can represent these tuple of powers (a1,a2,..,ad) for each divisor as a partially ordered set (poset).

        The goal is to find the longest antichain which is the width of the poset.

        You can notice that sum(ai) represents a distinct level.

        Lets say the number is 2^4*3^2.

        (4,2) represents level 6. (sum=6)

        (4,1), (3,2) represents level 5. (sum=5)

        (3,1), (4,0), (3,1), (2,2) represent level 4. (sum=4) and so on.

        Its kind of intuitive that the poset is symmetric about mid level (level=n/2) and that should have the maximum cardinality. I dont know a proof.

        Thus the answer to the problem is the number of solutions such that sum(ai) = floor(n/2).

        This can be solved by fft.

        My submission

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

          I see; thanks, that explanation makes a lot of sense!

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

Can E be solved using this idea:

1) Iterate from i=0 to n. i is the last problem of first-person.

2) Then do a ternary search for getting the answer among 2nd and 3rd person.

Is this idea correct?

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

    isnt binary search enough? I did not code it, I am a binary search code noob

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

    I don't think this solution is correct. As the cost of distribution between 2nd and 3rd is not necessarily unimodal.

    Example
»
4 weeks ago, # |
  Vote: I like it +152 Vote: I do not like it

I'm not sure if it was intentional, but E could be solved by ordering the three lists, concatenating them, and then running a very well known LIS (Longest Increasing Subsequence) algorithm.

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

    The answer was simply (K1+K2+K3) — N, where N is the length of the longest increasing subsequence.

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

    Can u help me prove it why is it LIS? The idea intuitively seems correct.

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

      LIS size is the most objects you can remain unchange

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

    But why it's working?

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

      Sort each array independently. Given this LIS size, you know maximum amount that are in place. The goal is to get whole array sorted, and each operation increases that number by 1 (place the element out of order to its position), so we will need that amount of operations. This is not a formal proof but an intuition of how I see it

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

      It's actually exactly COCI lista

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

    This is beyond my knowledge. Never knew LIS would be this powerful. This not only works for 3 arrays. The intuition is you want to maximize the amount of element to stay in its segment. What an elegant solution. to restore the steps of the answer, youll simply make the LIS related elements stay and move the rest greedily.

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

    It wasn't intended (model solution uses some math and prefix sums), but the solution is really cool nevertheless!

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

    Amazing solution!!

    this is a good source for people who dont know LIS to learn how it works.

»
4 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

How to solve G?

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +17 Vote: I do not like it
    Hint: It turns out 'finding' the subset is easy but 'counting' it is hard. Can you prove a certain subset must be maximal?
»
4 weeks ago, # |
  Vote: I like it +33 Vote: I do not like it

Why has CF started giving T test cases for every problem like codechef does?

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

    Now it's easy for us to run all the sample cases at once

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

      Yeah, but then i need to care about resetting global variables and arrays when problem has T test cases and it increases my chances of making a mistake.

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

        Wouldn't that be caught on the sample cases?

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

        You don't have to use global variables. They are evil.

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

    It's a common solution for ERs (and, it seems, div3) because it's too much burden for the system to check 20-30 tests (and 30 tests are not enough sometimes) per each submit especially on tasks like A, B, C.

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

    I highly prefer it this way. You get to have much better test coverage without insane queues.

»
4 weeks ago, # |
  Vote: I like it +80 Vote: I do not like it

Good Contest.

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

How to solve problem C?

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

    You just need to find the minimum difference of i and j, of same element. If no such i and j exist ans=-1;

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

English lesson: волшебная палочка — magic wand. :)

(Don't try to look it up on Google — you'l get the wrong idea. :)))

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

Finally gained some confidence, Thank you so much for the contest.

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

    What will you say when all your solutions are hacked? lol

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

only single line error in solution of problem D drop my dream of Expert.

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

    Don't worry. We hope you will expert very soon.

»
4 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

how to solve F?

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

    Use meet-in-the-middle, split x into first 15 bits and last 15 bits, and use map to check if there is second half.

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

      Does this fit in time limits?

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

        There will be like 2^15*100*30 operations if you use hashmap.

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

          Done!! thanks

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

          I wonder if it's possible to do a hash collision attack to force lots of deep equality checks if your hash function is deterministic

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

    Simplex!

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

      I also tried to solve the problem by constructing equations and inequations but didn't know how to solve the system. Can you please provide some useful resource to learn the simplex method and also to understand how to code it? Thanks.

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

Can anyone point out what the mistake could be for test-case 2 on problem D ?

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

    Try something like this: 2 6 1 2 3 3 3 3 3 3 3 6 1 1 6 (ans = 2) 6 6 1 2 3 4 5 3 3 3 6 1 1 6 (ans = 4). These tests helped me to find out my mistakes

»
4 weeks ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

i just have solved problem 1257C - Dominated Subarray — in Greedy solution in just O(n) ; why you did'nt include Greedy tag ! this is my submission : 64830934

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

    std::map works in O(log), not in O(1). So, your solution is O(nlogn)

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

      Didn't you notice that those 2 std::map's were never used? ;)

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

      IWMG my friend did you read my solution !!!?
      i never used std: map in it but just called it . i have used just one loop to read Input and an array to store last position for an element ! why it is O(n log n ) !

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

        Yeah, im sorry for it, i thought you use only maps. Then you're right, your solution works in O(n)

»
4 weeks ago, # |
  Vote: I like it -16 Vote: I do not like it

In problem D, we have to take input from the users which is O(n). So total TC would be minimum O(t*n) which is the order of 10^12. How is it passing?

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

    *Order of 10^10.

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

    It is guaranteed that the sum of n+m over all test cases does not exceed 2⋅10^5

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

I can only solved 2 problems... kinda have feeling my rating will be decreased again XD. I hope I can get better next time T_T. Gotta learn more frequent.

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

Any clue about the 18th sub-test of test case 2 in problem D ?

Edit: I was writing min in place of max in Sparse Table. XD

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

Who else, first, thought of Binary Search for C? xD

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

    :-/

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

    I thought and did it that way only.

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

      Yeah, but you applied binary search to get the index where a[i] occurs next. I was applying it to find the optimal length.

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

        Yes.

        Maybe.

        Submission

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

          Nice solution. I was checking if there exists a subarray of length exactly mid such that it is dominated, if no, I assumed that there will not be any dominated subarray with length less than or equal to mid, which clearly is wrong.

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

Whats the DP solution for E?

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

    dp[i][j]: I'm looking at element i, at group j.

    I can either start the next group -> dp[i][j]=dp[i][j+1]

    or add element i to existing group -> dp[i][j]=(i is not in group j) + dp[i+1][j]

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

For all of you that want something to uphack but can't: 64856439. This shit really shouldn't pass, it should get WA or TLE or both.

»
4 weeks ago, # |
Rev. 2   Vote: I like it +15 Vote: I do not like it

Try to hack my $$$O(n*2^{30})$$$ solution to F: Link

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

    How does this runs in less than 2 seconds?

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

      It does, my approach takes approx. 3 seconds on the judging server of CF(I used vectors and cins and stuff), yet it took forever to run on my own computer.

      However, I am getting WA 92 for some strange reasons, and since my logic is very similar to his, maybe he will get WA on the same tese(just my guess).

      I went through his judgement protocol and saw that he has only been tested with tests 1 to 83.

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

        Oh, somebody already put into the effort to tinker the constant and break it lol.

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

What on earth is test $$$92$$$ of problem F? I kept getting WA for it using the most naive brute-force algorithm.

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

    You remove duplicates from the vector a but still loop up to n, not to the size of a, accessing elements past its size. It doesn't necessarily segfault since the vector had size n+1 before, but It seems something problematic happens in that test.

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

      I don't think that causes WA though? Although he/she is reading elements out of bounds, no writes were performed so the data should not be corrupted, and more reads (albeit corrupted) could only cause more "bad" cases to show up, hence this issue should not lead to false positive.

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

        I also think so. I mean, well, I am not doing anything to the out-of-bound indexes, and changing it to a.size() causes TLE3

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

I will hack you!

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

Can D be solved using binary search ? If yes can anyone share their approach?

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

    Try greedily defeat more monsters, so we need to binary search how far we can reach.

    Suppose we need to defeat K monsters and the highest power among them is P, we need to have at least one hero with p>=P and s>=K, which could be precalculated, in such a form: maxp_i = the largest power among heros which has s>=i. Thus we could easily check whether maxp_K>=P.

    Binary search such K and get the answer, to find P, is a problem of RMQ,use ST.

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

    Yes, there is a way. First sort all the heroes by power. Then create an array of suffix endurances for the sorted array of heroes. Suppose you have to kill k monsters on a particular day. Then find the maximum of those monsters and do a binary search on sorted heroes to find the suffix which includes all the heroes that have sufficient power to defeat the k monsters. Now, look at the maximum endurance of that suffix which we already calculated. If this endurance is at least k then we can kill k monsters. So you can check for each k whether we can kill k monsters or not in log(N) time.

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

no systest?

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

How to sol D?? I need help..

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

Help needed in Problem E

My approach is getting WA on test case 6 and I don't know why. Please can someone tell me why it is coming wrong.

My Approach :

I will try to make all possible prefixes for A(first person) i.e. (from 0 to N) where N = k1+k2+k3. I have maintained a set of elements for all three of them. Now suppose prefix of A is "i", so I will remove all the elements less than equal "i" in the set of first, second and third person and for it, I am maintaining the count in a variable name "taken". Now the problem is to solve for B(second person) and C(third person), and this will be equal to the minimum of the count of (elements in C which smaller than the largest element in B) and (elements in B which bigger than the smallest element in C) this can be done using BIT(In which I delete the elements according to the prefix). Note that I don't have to give the remaining elements of A to B and C first and do the computation as we can assume that A was given to them in the correct order.

So the final answer for the prefix "i" = taken + "remaining element in A(as he has to give it to other)" + min(element B give to C, element C give to B). And the minimum of all the prefixes will be our answer.

My Submission

Thanks in advance!!!

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

    Hi, check this case:

    10 10 10
    10 29 14 28 18 9 20 7 23 22
    30 19 2 25 12 17 8 15 11 21
    6 13 5 1 4 16 3 24 26 27
    

    The answer should be 18. Hope it helps.

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

E can be solved using dp.But some people solved it using binarysearch,how to solve it using binarysearch?

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

    And also How to solve using segment tree because I have seen some has done by segmeent tree

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

    using dp mean using LIS or something else?

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

      dp[i][1] means the smallest cost which all [1,i] number return to its correct position and the i-th number(which is exactly i) belongs to the first Programmer.

      dp[i][2] means ... belongs to the second Programmer. dp[i][3] means ... belongs to the third Programmer.

      the ans is the smallest number among dp[n][1], dp[n][2] and dp[n][3].

      if id[i]==1 and you want to let it still belong to the first Programmer, it cost none. Otherwise you will cost 1 unit.

      int id[200005], dp[200005][4];
      
      int main() {
          int A, B, C;
          scanf("%d%d%d", &A, &B, &C);
          for(int i = 1, ai; i <= A; ++i) {
              scanf("%d", &ai);
              id[ai] = 1;
          }
          for(int i = 1, bi; i <= B; ++i) {
              scanf("%d", &bi);
              id[bi] = 2;
          }
          for(int i = 1, ci; i <= C; ++i) {
              scanf("%d", &ci);
              id[ci] = 3;
          }
      
          int n = A + B + C;
          for(int i = 1; i <= n; ++i) {
              if(id[i] == 1) {
                  dp[i][1] = dp[i - 1][1];
                  dp[i][2] = min(dp[i - 1][1], dp[i - 1][2]) + 1;
                  dp[i][3] = min(dp[i - 1][1], min(dp[i - 1][2], dp[i - 1][3])) + 1;
              } else if(id[i] == 2) {
                  dp[i][1] = dp[i - 1][1] + 1;
                  dp[i][2] = min(dp[i - 1][1], dp[i - 1][2]);
                  dp[i][3] = min(dp[i - 1][1], min(dp[i - 1][2], dp[i - 1][3])) + 1;
              } else {
                  dp[i][1] = dp[i - 1][1] + 1;
                  dp[i][2] = min(dp[i - 1][1], dp[i - 1][2]) + 1;
                  dp[i][3] = min(dp[i - 1][1], min(dp[i - 1][2], dp[i - 1][3]));
              }
          }
      
          printf("%d\n", min(dp[n][1], min(dp[n][2], dp[n][3])));
          return 0;
      }
      
      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you plz explain the transitions?

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

          dp[i][1]=dp[i-1][1]+cost(i,1); dp[i][2]=min(dp[i-1][1],dp[i-1][2])+cost(i,2); dp[i][3]=min(dp[i-1][1],dp[i-1][2],dp[i-1][3])+cost(i,3);

          cost(i,j) means the cost if let the i-th problem be solved by the j-th programmer. Easily to know that cost(i,j)=1-(id[i]==j).

          dp[i][1] from dp[i-1][1] means let [1,i] problems all be solved by programmer 1.

          dp[i][2] from dp[i-1][1] means let [1,i-1] problems all be solved by programmer 1, but the i-th problem start to become be solved by programmer 2.

          It means when you start to assign i-th problem to programmer 2, you cannot assign all j-th problem (j>i) to programmer 1.

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

Can anyone confirm whether my approach for D is correct.
Sort the soldiers with inc power. For every ith monster, do B.S and find the soldier whose power >= power of monster, let be at index idx, then I will choose the soldier with maximum strength from index idx to n (as all soldiers after idx have greater power than idx). Let's call this soldier as 'X'.
I will kill as much monsters with this soldier as I can. Now two case arise-
1. Number of monster killed by x becomes equal to its strength, i.e., x.killed == x.strength
2. It's power is less than current monster.

For the first case I will increase the count of day and again iterate as done in first step.
For the second case, I will B.S and find the soldier whose power >= power of monster, and has the most strength(among those having power greater than the monster), let's denote it by 'Y'.
Now 2 conditions arise,
1. x.killed < y.strength For this case I can safely say that instead of chosing X in the first place I could have chosen Y and killed more monsters than X, so I update my current soldier from X to Y (as X.power=Y.power, X.strength=Y.strength).
2. x.killed>=y.strength. For this case I increase count of day , udate my X and iterate forward(X.power=Y.power , X.strength=Y.strength, X.killed=1).
I am getting WA for 2nd test case.
Here is my solution : 64836864

»
4 weeks ago, # |
  Vote: I like it +41 Vote: I do not like it

The color of the name seems to be wrong

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

Does anybody have a $$$O(n)$$$ approach to solve D?

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

    I don't think an O(n) solution is possible for this problem. O(nlogn) is needed at least.

    UPD: oh there is a clever O(n) solution. watch roll_no_1 's comment.

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

    You are also Chinese, so you can see this.

    https://www.cnblogs.com/KisekiPurin2019/p/11854682.html

    You can use dp to get the highest power of heroes which has at least i endurance.

            scanf("%d", &m);
            for(int i = 1, pi, si; i <= m; ++i) {
                scanf("%d%d", &pi, &si);
                p[si] = max(p[si], pi);
            }
    
            for(int i = n - 1; i >= 1; --i)
                p[i] = max(p[i], p[i + 1]);
    

    p[i] is the highest power which can beat i monsters in just one day.

    and then you can use greedy, each day try to move as more as possible.

            int i = 0, j = 0, rmq = -1, ans = 1;
            while(j < n) {
                ++j;
                rmq = max(rmq, a[j]);
                if(p[j - i] < rmq) {
                    if(rmq > p[1]) {
                        ans = -1;
                        break;
                    } else {
                        i = j - 1;
                        ++ans;
                        rmq = a[j];
                    }
                }
            }
    

    It means you have already beaten i-th monster, and you want to beat the j-th monster, today you move j-i blocks so the highest power is p[j-i], if p[j-1] < a[j], you need to wait until tomorrow and use your highest power hero p[1] to try to beat it.

»
4 weeks ago, # |
  Vote: I like it +36 Vote: I do not like it

Does anyone know about this anomaly

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

When will be an editorial?

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

What was the approach for D apart from Segment Trees/Sparse Table ?

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

    Sort by endurance and find for every endurance suffix maximum instead of using segment tree, and just compare maximum of monsters with this suffix maximum

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

    you sort array of pairs <endurance, power>. Then you try to kill in one day as much as possible so you iterate through $$$a_i$$$, count the number of monsters you want to kill this day as $$$cnt$$$ and memorise the most powerful monster this day as $$$max\text{_}pow$$$. You go further and further until there is a hero with $$$s_j \ge cnt$$$ (it can be checked by $$$lower\text{_}bound$$$) and a hero with $$$p_j \ge max\text{_}pow$$$. To check the last condition you can look at max hero power on suffix $$$[j..m - 1]$$$ and you can do it in $$$O(1)$$$ by precalcing an array $$$max\text{_}suf$$$ where $$$max\text{_}suf_i$$$ is the maximum power of hero in suffix $$$[i..m - 1]$$$ in sorted array

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

    Why don't you read above there have been atleast 10 comments about D solution !!!

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

My Screencast for this round.

https://www.youtube.com/watch?v=g5n6eW7uwVY

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

Jesus! Where is the solution(

ok. i just want to know how to solve problem G

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

 UMMMMMM!!! OK XDD

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

I have a question about the problem D. In this question,a special example

Input:

1

5

1 2 3 4 5

3

1 10

2 10

5 1

for this example,the right answer should be 4,not 5.And I found that a lot of the output through the AC code was 5.Why?

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

Can anyone explain solution of F briefly? TIA

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

When will the editorials be available ?

PS:Hints on div 2 C,D,E,F,G please ... I am new:)

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

How to solve E?? I think in E many coders used different techniques to solve it..

Here are some in the comments.. more are welcome. https://codeforces.com/blog/entry/71362?#comment-557767

https://codeforces.com/blog/entry/71362?#comment-557863

Using LIS https://codeforces.com/blog/entry/71362?#comment-557658

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

Editorial?

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

When will the editorial of the problems be posted?

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

How about editorials???

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

Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).

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

Color display still not fixed ?

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

I can't see my friends standing of this contest. (It's not for sign in problem)

Let me know if I only facing this problem...

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

Why Difficulty of this round in Problemset is None

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

Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).

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

Please also include pwild as the 5th place winner, we had the same penalty.

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

    Whoops, sure. Funny enough my script got pwild into the rus version of the table and you in the eng one :D

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

      I was wondering why I got a message saying I was mentioned in some topic, but then not actually finding my name in the text.