Please read the new rule regarding the restriction on the use of AI tools. ×

RobinFromTheHood's blog

By RobinFromTheHood, history, 3 weeks ago, In English

Thank you all for participating in the round! We hope you had fun, as we did thinking of the problems. We would like to again thank our coordinator Vladosiya who made many suggestions for improving all problems here, and rejecting others.

2014A - Robin Helps

Author: RobinFromTheHood

solution
code python
code cpp

2014B - Robin Hood and the Major Oak

Author: ChairmanFMao; Developer: Filikec, RobinFromTheHood

solution
code python
code cpp

2014C - Robin Hood in Town

Author: RobinFromTheHood; Developer: Filikec, RobinFromTheHood

solution
code python
code cpp

2014D - Robert Hood and Mrs Hood

Author: RobinFromTheHood; Developer: ChairmanFMao; RobinFromTheHood

solution
code python
code cpp

2014E - Rendez-vous de Marian et Robin

Author: RobinFromTheHood; Developer: Filikec, RobinFromTheHood

solution
code python
code cpp

2014F - Sheriff's Defense

Author: Filikec; Developer: Filikec

solution
code python
code cpp

2014G - Milky Days

Author: RobinFromTheHood; Developer: Filikec, RobinFromTheHood

solution
code python
code cpp

2014H - Robin Hood Archery

Author: Filikec; Developer: Filikec

solution
code python
code cpp
»
3 weeks ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

gigafast editorial 😬 btw for problem H, isn't checking (r — l) odd and number of uniq element is sufficient to answer query? I received WA2 with that approach

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

    the number of unique elements can be greater than 1 and yet the array is not losing.

    Here is an example:

    [3, 3, 1, 1]

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

    If by number of uniq element you mean printing YES iff the number of unique elements is 1, this misses other cases where its possible.

    Consider the following test case:

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

    the only check you need is whether any element appears an odd amount of times. if yes then the answer is no, and otherwise the answer is yes

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

Lightning fast editorial

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

Wow , problem G is so simple. Solid Problemset!

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

Problems are good, except for H which is a bit too common (but still educational :)). Fast editorial!

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

    I have never seen the H idea before, so it's appreciated

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

gonna hate myself for the rest of my life for messing up C.... i was sooooo closeeee

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

    Same as you, I used binary search to solve C ,and I was deeply annoyed by the edge situations mentioned in editorials … A so simple problem costs more than 1 hours

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

      I solved C in 19 minutes but wrote r=1e6 unstead of 1e18. It took me until 1h30 to solve it T-T

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

H should be placed before F imo

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

    We were discussing placing H differently but ended up placing it here as it needs specific algorithms. G could be solved with nothing advanced.

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

    I guess despite the fact that H turned out to be a famous problem, F didn't require any advanced algorithms knowledge. So it has a better chance to be solved by lower rated people

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

For problem C I used binary search on the possible values of x. When I made the upper bound of x = n*max_element+1 it gave WA but when I gave it as 1e18 it was accepted. Can someone explain this?

EDIT: originally wrote 2*max_element+1 . Updated to n*max_element+1 which is the upper bound that gave WA instead of 2*n*max_element

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

    I also encountered a similar issue when I solved the "C — Maximum Median" problem. I'd like to understand the story or concept behind this problem .

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

    maximum value of x can be (n * max_element + 1), in the case where all values are equal to max element

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

      Sorry, made a typo. I set the upper bound to n*max_element+1 in my solution but got WA before changing it to 1e18. What is wrong here? Is the division causing problem? Why is 2*n*max_elementthe correct upper bound?

      here is accepted 282332784

      and WA version 282330368

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

F is really nice. Consider a parent and child combination. If parent is not strengthened, then the answer remains unchanged. If the parent is strengthened then there are two cases:

  1. If child is not strengthened, then they lose c gold but it doesn't matter as it is not going to be counted anyway.

  2. If child is also strengthened, then it costs c from the parent, but now the deficit of c from the child also counts, so in total we get a[i] - 2*c in this case.

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

    thanks!

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

    This explanation of the key moment should have been included in the editorial for problrm F to be worth its purpose.

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

    Finally understand!thanks!

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

Glad we have proper anti-wrong-Dijkstra tests on E :)

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

    I'm happy you noticed :)

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

    wdym by "wrong-Dijkstra" ?

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

      Let me introduce this to you :)

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

        I have had this blog starred for weeks. Thanks for reminding me.

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

        its funny how you got hacked on E

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

          I made a few post-contest submissions to see if we have strong tests. It turned out the inf test wasn't as strict, so hacked them with the largest inf tests. My contest submission survived though.

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

Why do we need random numbers for the xor solution in H? Wouldn't the xor always be 0 if every element in a range occurred an even # of times?

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

    If you xor the original numbers instead of random ones, some of them may emit a zero even if not every element occurs $$$2k$$$ times. E.g. 1 2 3

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

      Idk why I didn't think of that lol ty

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

      But it is still possible that the random numbers generated could emit a zero too, even if they don't appear 2k times.

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

        Yes, so the algorithm is not deterministically correct. But we assume that the probability of this situation is very small.

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

          because of that reason, I solved it using segment tree. https://mirror.codeforces.com/contest/2014/submission/282578178

          please can you elaborate how probability works on the advanced problems!!

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

            There is a tutorial of xor hashing: link. And in the blog is the detailed elucidation about the probability of hash collision.

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

              thanks a lot!!

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

              hey can you help me with this problem, here are my submissions for the same without map and with map only the without map one got accepted but I used a single prime num to generate hashes so I am afraid that on vast testcases, this might fail due to collision, also I want to solve it by hashing

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

    yes but the XOR can also be zero even though the range has some elements occuring odd number of times.

    for example:

    [1, 2, 3]

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

still i didn't understand E :)

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

    it's a famous algorithm called dijikstra

    try to learn about it first

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

A job between days li and ri would overlap with the visit if the start day x satisfies li−d+1 ≤ x ≤ ri

I didn't get this statement. Can somebody explain this?

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

    We can rearrange $$$l_i - d + 1 \le x$$$ to get $$$l_i \le x + d - 1$$$. If a visit starts on Day $$$x$$$ and spans $$$d$$$ days, Day $$$x + d - 1$$$ is exactly the last day of the visit. So $$$l_i \le x + d - 1$$$ means the job starts earlier than or exactly when the visit ends.

    Likewise, $$$x \le r_i$$$ means that the job ends later than or exactly when the visit starts.

    More intuitively, they overlap when there is at least one day where you would have to do some job while visited by your mother/brother.

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

I don't understand dijkstra probably. How does it get the correct shortest paths from source 1 for the sample test 5.

3 2 1
2
1 2 4
1 3 16

How does it go to $$$2$$$ and take the horse and come back ? Since d[source=1] = 0, I assume it(the source) would not (and should never ?)get relaxed by $$$2$$$. Also, there isn't any edge $$$E(2,3)$$$.

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

    You have to calculate two times for each vertex. The fastest time to get there without using a horse and the fastest time to get there using a horse. If you get on a horse at vertex v, then you continue traversing the graph, but you have to start updating the times for when you're on a horse.

    So in your example, you get on a horse at vertex 2 then go to vertex 1 since d_with_horse[1] = INF

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

      I see, thanks.

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

        You can define the "graph" as a pair of node, state and do dijkstra on this modified graph. Here, for a node u, the elements in the modified graph are (u, 0) for no horse and (u, 1) for a horse. Sometimes this state can have more values, be bitwise flag etc. as well.

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

Can someone provide a solution in python for problem B without using import sys, I am getting Time Limit Exceeded error

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

    It is an observation problem. First print sum of i ** i for low range. Then notice the odd-even pattern.

    t = int(input())
    for _ in range(t):
        n, k = map(int, input().split())
        a = (n % 4) in {0, 3}
        b = ((n - k) % 4) in {0, 3}
        if a == b:
            print('yes')
        else:
            print('no')
    
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I used same logic in C but still got WA. Can anyone tell my why? Thank you in advance. I did 2 different code but same logic. Still can't understand why it wasn't accepted.

282360605 282336672

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

    Both a[lastman] and n are ints, so a[lastman]*2*n can overflow when these are large.

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

      Sorry if this is a dumb question, but ansis long long. So it shouldn't be a problem?

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

        It doesn't matter whether you're assigning the result to a long long. You should note that every operation is done with types, and a[lastman]*2*n is a series of operations that is done only with int types. The overflow occurs right here, and assining is done after this overflow already happened. Once the overflow happens, there is no way to fix it back — its value is already broken (to be precise, it is already an undefined behavior.)

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

E can also be solved with a different approach Also. My idea is related to binary search the answer

Comment link of Solution : https://mirror.codeforces.com/blog/entry/134087?#comment-1200754

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

how is editorial even published 4 days ago?!

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

    The blog was private and made public after contest.

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

      OMG round developer's first reply on my comment... happy to see... BTW Can D be solved with the same kind of logic for CSES Movie Festival ?!

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

Why my solution is getting WA in problem H

Submission: https://mirror.codeforces.com/contest/2014/submission/282384796

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

    The array a has 1e6 + 5 elements, combined with T testcases, that yields a solution with a T * (1e6 + 5) time complexity for that alone, which in itself can exceed 1e10

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

      Yea, just figured it out from a while.

      Thanks for help

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

I'm not sure if this was luck or actually correct

can someone try hacking this code for B

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

(Edit: having collision doesn't directly lead the solution to fail with high chance, see below comment for details.) For using hash for problem H, one need to use at least 64-bit hash or dual-hash.

Recall the probability for hash collision is $$$1-exp\left(-\frac{n(n-1)}{2d}\right)$$$, where $$$n$$$ is the number of elements and $$$d$$$ is the hash space.

if $$$n=1e6, d=2^{32}$$$, $$$1-exp\left(-\frac{n(n-1)}{2d}\right)\approx 1$$$ and it can be hacked

if $$$n=1e6, d=2^{64}$$$, $$$1-exp\left(-\frac{n(n-1)}{2d}\right)\approx 2.71e-08$$$

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

    Oh no, I woke up after sleeping and found out that my H had been hacked. I just realized that mt19937 only generates integers within int, so mt19937_64 should be used. But I'm still very curious about how you hacked me, constantly submitting random data?

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

      I didn't hack in this round. I originally thought the hacks use collisions, when I read some of the hack generators (and found them interesting!) I realized they are generating adversarial test targeting any deterministic hash functions. Yes time(0) as seed is deterministic in the context because one can generate hundreds of tests and the hack will be valid for a few minutes. Should use something less predictable like chrono::system_clock::now().time_since_epoch().count() (nanosecond)

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

    While this estimate is safer in general, you should notice that the solution for H this times only made n comparisons of hashes. Making it (1-2^32)^n, which is not that bad. This would fail with probability of about 0.00005. If were to go against 100 max tests, then there is a non-negligible chance that it fails, (0.5% roughly), but hardly a common thing.

    If the error estimate is indeed as bad as you claim, that it should have gotten a wrong answer on literally any random test.

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

the problem F can be solved by greedy??

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

Solved H just after the contest ended. QwQ

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

can resolve test case limitations!

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

In F, if instead of taking coins from only the neighbours we take coins from all the nodes, then how would we solve the problem?

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

    then xringe ah unworthy prblem, onli save till negative

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

      skibidi kinda fellow...

      ig pulling from all breaks down the tree structure and we can just iterate from the back of the sorted array and take elements based on that. This function is also monotonic but that unnecessary.

      What I meant that if the influence reaches to more than one level eg. neighbours at a distance <= k will also be reduced by c, then how to solve.

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

        just use dp of size n*k, pls dont waste others' time here asking these simple questions. Thanks.

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

ngl i dont know why i do a O(10^6) G lol

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

Can anyone figure out what's wrong with my approach?

Submission: 282417933

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

    your handling of withhorse and found separately seems inappropriate. As if a horse is found once and we decide to sit on it, then we will be sitting on it for the rest of the journey itself.

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

Guys, can someone tell me why does my submission for D(282372366) get TL?

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

E was a nice problem. Loved the modified Dijkstra algorithm!

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

For B ,why (n-k+1)+n)*k/2 can't accept,WA in test3;(n-k+1)+n)*k//2 is right,I don't know!Who can help me?

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

    due to float handling, as during calculation of [(n-k+1)+n]*k ; and then dividing it by 2 can lead to a deviation from the actual answer (always an integer btw), and this very small deviation, will return a false when checked for divisibility with 2 without first converting it to a proper integer which it should be(as this small error will also be taken into account).

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

Nice Contest ! , RobinFromTheHood Orz .

Though this is my feedback :

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

    Problem B can simply be reduced to counting the amount of odd numbers in [n-k+1,n], if it is odd, its NO, otherwise, its yes

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

Can anybody help me, this is giving TLE for E problem


#include <bits/stdc++.h> using namespace std; #define inf LLONG_MAX typedef pair<int, int> pii; typedef long long ll; int ini() { int x; cin >> x; return x; } void pl(ll x) { cout << x << endl; } vector<ll> paths(int n, int start, vector<vector<pii>>& path, set<int>& horses) { vector<ll> ans(n + 1, inf); set<pair<int, int>> visited; ans[start] = 0; priority_queue<vector<ll>, vector<vector<ll>>, greater<vector<ll>>> pq; if (horses.count(start)) { pq.push({0, start, 0}); visited.insert({start, 0}); } else { pq.push({0, start, 1}); visited.insert({start, 1}); } while (!pq.empty()) { vector<ll> data = pq.top(); pq.pop(); ll dist = data[0]; int node = (int)data[1]; int horse = (int)data[2]; visited.insert({node, horse}); if (horses.count(node)) horse = 0; for (pii p : path[node]) { int src = p.first; int dis = p.second; if (visited.count({src, horse})) continue; if (horse == 0) { pq.push({dist + dis / 2, src, horse}); ans[src] = min(ans[src], dist + dis / 2); } else { pq.push({dist + dis, src, horse}); ans[src] = min(ans[src], dist + dis); } } } return ans; } void solve() { int n = ini(); int m = ini(); int h = ini(); set<int> horses; for (int i = 0; i < h; i++) { int l = ini(); horses.insert(l); } vector<vector<pii>> path(n + 1); for (int i = 0; i < m; i++) { int u = ini(); int v = ini(); int dis = ini(); path[u].push_back({v, dis}); path[v].push_back({u, dis}); } vector<ll> p1 = paths(n, 1, path, horses); vector<ll> p2 = paths(n, n, path, horses); if (p1[n] == inf) { pl(-1); return; } ll ans = inf; for (int i = 1; i <= n; i++) { ans = min(ans, max(p1[i], p2[i])); } pl(ans); } int main() { ios::sync_with_stdio(false); cin.tie(0); int t = 1; t = ini(); while (t--) solve(); return 0; }
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Because the total time complexity is $$$O(n\ log^2\ n)$$$

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

      i tried changing the set to unordered set still didnt work there shdnt be any collisions for 1e5 right ?

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

        I'm not sure, haven't used unordered set before.

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

    I have commented out your code.
    changes :
    1. used vector horses instead of set horses
    2. used vector<array<ll,2>> visited instead of set<pair<int,int>> visited;
    3. changed the position where you were checking visited node. Your code was pushing the same node more than once.
    optional : you may use priority_queue<array<ll,3>, vector<array<ll,3>>, greater<array<ll,3>>> pq; to reduce overhead. I will improve the code performance.

    My Code
»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

https://mirror.codeforces.com/contest/2014/submission/282262350

This man managed to add comments and neatly format his code while solving the problem in 4 minutes. truly impressive

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

    All of this while averaging ~10k rank in previous contests. Truly marvelous.

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

    A : ~3 min B : ~6 minutes, C & D & E: ~4 minutes (A-E in ~21 minutes) crazy

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

Can someone tell me what is wrong with this code and which testcase it will fail. Thanks!!

#include<bits/stdc++.h>
using namespace std;
int main() {
    int t;
    cin>>t;
    while(t--){
        int n,k;
        int count_zero=0;
        int count_sum=0;
        cin>>n>>k;
        vector<int>arr(n);
        for(int i=0;i<n;i++){
            cin>>arr[i];
            if(arr[i]==0) count_zero++;
            else if (arr[i]>=k){
                count_sum+=arr[i];
            }  
        }
        int result=min(count_zero,count_sum);
        cout<<result<<endl;
    }
    return 0;
}
  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    You need to think again for the logic. Robing goes from 1 to N in order, we are not allowed to rearrage the array. Robin can only help if he has amount > 0.

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

      suppose this case — 1 2 3 0 0 0 0 0 0 0 where n=10 and k=4 in this- result(0, 7) -> result = 0 . Are you talking about this case where robin had zero gold??

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

        this case — 0 0 0 0 0 0 0 5 5 5 where n=10 and k=4
        you code will output 7 but answer is 0

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

WTF is this code, can someone tell me — 282251367 edit — MikeMirzayanov

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

    This is called obfuscation and it is forbidden by rules.

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

      Should we report the user or What ?? He had use this to gain +497 rating.. in last contest

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

        Yes, this one should be reported as contest rules violator.

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

    I think they did it to avoid plag but anyways hiding solutions is not allowed

    rules

    "It is forbidden to obfuscate the solution code as well as create obstacles for its reading and understanding. That is, it is forbidden to use any special techniques aimed at making the code difficult to read and understand the principle of its work."

    MikeMirzayanov RobinFromTheHood

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

Just found out, c++ version can affect the hashing solution. I am used to c++17, but the editorial solution actually fails for c++17, submission: https://mirror.codeforces.com/contest/2014/submission/282483545.

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

Problem E was really good! I never thought Dijkstra's algorithm could be used in this way.

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

is it possible to solve D with lazy segtree? I overkilled it straight for 20 mins but I couldn't solve it during contest. If someone knows please tell

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

    Technically the range sum updates in D (as said in editorial) can be mimicked by lazy segtree; i.e. they do the exact work. Though I don't know why you would rely on segtree as your first option...

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

      with range sum updates, how will we identify the distinct overlaps? I wanna know how to solve it with lazy segtree for educational purposes

      Edit: I'm not talking about editorial solution in particular. Just if there's one

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

        I think I said bogus just now... now I can't think of any way to explain without clunking up the solution.

        Like, what I have in mind is a simple solution, doable in segtree but it just adds unnecessary extra steps.

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

        Thinking again, when writing a slightly related comment just below, I realize you can do segtree if you want to store the numbers of jobs for each range.

        Now, index $$$i$$$ in segtree will correlate to range ending at day $$$i$$$. Loop $$$i$$$ in range $$$[d, n]$$$ again:

        • "Add $$$s_i$$$ to $$$v$$$" correlates to "add $$$s_i$$$ to range $$$[i, n]$$$".
        • "Remove $$$e_{i-d+1}$$$ from $$$v$$$" correlates to "add $$$-e_{i-d+1}$$$ to range $$$[i+1, n]$$$".

        Of course, the last part means you'd just query a single index for all index in range $$$[1, n]$$$ just to get the min and max you wanted. Pretty tedious there...

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

IN Problem D

What will be the approach if 1<= l,r <=10^9?

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

Very hacky solution for D without prefix sum:

Count the number of jobs with the same start dates and end dates, separately. We'll call $$$s_i$$$ as the number of jobs start at date $$$i$$$, and $$$e_i$$$ as the number of jobs ends at date $$$i$$$.

Set a temporal value $$$v = 0$$$, now loop all end dates $$$1 \le i \le n$$$:

  • Add $$$s_i$$$ to $$$v$$$.
  • Now, $$$v$$$ is the number of job in range $$$[i-d+1, i]$$$. If the range is valid (a.k.a. $$$i-d+1 \ge 1$$$), update the optimal answer for both personnels.
  • Remove $$$e_{i-d+1}$$$ from $$$v$$$.

Submission: 282518960

I think this can extend to solve D with arbitrarily large $$$n$$$ with compression and a bit of extra tricks, but I'm not too certain.

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

For problem H, why isn't XORing from l -> r and checking non-zero a sufficient condition? I'm getting WA on test 3...

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

    One easy countertest: a range with elements $$$[1, 2, 3]$$$. You'll see the xor sum being $$$0$$$ but it isn't completely made of pairs of numbers.

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

Can anyone please help to find why is my solution for problem-C giving integer overflow?

solution

I have used ll as long long and it is giving overflow for val, which will at max be n*2*(max(a[i])) = 2*(2e5)*1e6 = 4e11 which should not give overflow for long long, like I get that there is no need for this long binary search but still I could not find why it is giving overflow

Thanks in advance

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

    Your m can be pretty large (1e18 / 2) and you add it to some array element and then multiply by n causing overflow.

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

I really like problem E!

I practiced a 2D dijkstra before so I am glad I can catch the idea really quick.

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

my submissionwhy am I getting tle in problem c ? pls help.

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

This is my code for Problem H

Spoiler

Why my code is getting WA on test 3 282785052 .

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

I was trying H, but getting WA on 75th TC. When I changed compiler to G++ 23 (from 17), it got AC. Does this happen usually in in these qns? I also tested locally but locally (with g++ 13), i was getting the right ans. Following submisison got AC by changing compiler, guidance appreciated on what to do in a contest setting. 282807018

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

can anyone tell why am i getting a tle in problem E 282462349

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

Hello everybody, i try to solve E so hard, but i get WA and don't understand why. May be some chads can help me?

282818149

P.S. Sorry for this large and bad code. I am ready for criticism and advice!

  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yo, as we have two states in the graph, our previous nodes which were once only 1, 2, 3, .., n

    But now we have 2d Nodes, {i, 0} or {i, 1}

    You haven't used the priority queue correctly Just think in 1d codes you have had priority queue as {dist, node} right So in 2d it should be a tuple as {dist, {node, 0 or 1}}

    Also remember this is actually like dynamic programming itself its just that in DP the state space graph is a DAG (acyclic) so we have to let the transition decide the {node, 0 or 1} in your code you have yourself initialized and transitions are also a bit incorrect

    General Tip this is State space modelling question so you need to think in DP manner to solve it efficiently

    For a good idea on State space modelling look into this Blog about Dijkstra and State Space Modeling

    • »
      »
      »
      8 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Here is My approach — use state space formulation

      total Time Complexity = O( N LOG(N) ) multiplied by 2 as i am using dijkstra a 2 times;

      (node, 0) represents we don't have a horse (node, 1) we have the horse

      if( node has a horse in it and you are in the state node, 0 ) go to state (node, 1) with 0 cost as mentioned in the question

      if we are at (node, 1) then we can only go to (child, 1) with cost edgeWeight / 2

      if we are at (node, 0) then we can only go to (child, 0) with cost edgeWeight

      run this dijkstra from node number 1 and node number n for all nodes maximise the minimum distance from each node

      then for all nodes minimise the distance and find the minimum

      Submission Link quite self explanatory 283107392

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

in Problem E, why have we used comparator lambda function: make_pair(distance[a.first][a.second], a) <make_pair(distance[b.first][b.second],b) and not the distances of a and b states: d[a.first][a.second] < d[b.first][b.second];.
Is it because incase of two states having same distances, it will consider them equivalent? and if so, what difference will it make. would appreciate some help here, thanks!

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

    I think it's because when you have two distances that are the same, for example in the input example of the problem test case 5, when maria starts doing dijkstra, she will have two options that has the same distance value; 4. this causes the set to assume that they are the same value thus not inserting it into the set when we actually want it to be inserted.

    CMIIW

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

I have a doubt regarding problem H in this contest. My submission

// ll random_address() { char *p = new char; delete p; return uint64_t(p); } // ll splitmix64(ll x) {

// x += 0x9e3779b97f4a7c15; // x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; // x = (x ^ (x >> 27)) * 0x94d049bb133111eb; // return x ^ (x >> 31); // } // const ll FIXED_RANDOM = splitmix64(chrono::steady_clock::now().time_since_epoch().count() * (random_address() | 1)); why we have to use uint_64, i am not able to use ll as long long in the first line , when i am using ll it gives me error , why so could anyone explain please. and also explain how to write this function which randomly generate numbers because in the blog suggested by crystal it is difficult to understand so could you please explain here as i have write above code with the help of code submitted by neal , and actually i myself use some other technique to generate numbers in this solution and the code accepted and i was suprised because i used some random things, so could you please tell me some mathematics behind this that how it is working , and i also submitted two codes ,in one i was increasing x by 1e5 and in another one i was increasing by 1e8, and suprisingly the code with 1e5 accepted and with 1e8 it was giving wrong answer on test 5 . both code links are With x+=1e5 and with x+=1e8. and I have one more doubt when i was using M = 1e9+7 the code with x+=1e5 accepted and in same code i was using M = 999999937 in the code it is giving WA on test 5. So it is humble request to crystaI and RobinFromTheHood and other cf community coders to clear my doubt.

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

    please help me to understand this

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

    jb koi bta nhi rha tujhe to yaha pe chutiya doubt kyo puch rha he bsdk

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

    Mindeveloped and AkiLotus, please help to clear this doubt

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

      what???

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

        I have a doubt regarding problem H in this contest. My submission

        // ll random_address() { char *p = new char; delete p; return uint64_t(p); } // ll splitmix64(ll x) {

        // x += 0x9e3779b97f4a7c15; // x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; // x = (x ^ (x >> 27)) * 0x94d049bb133111eb; // return x ^ (x >> 31); // } // const ll FIXED_RANDOM = splitmix64(chrono::steady_clock::now().time_since_epoch().count() * (random_address() | 1)); why we have to use uint_64, i am not able to use ll as long long in the first line , when i am using ll it gives me error , why so could anyone explain please. and also explain how to write this function which randomly generate numbers because in the blog suggested by crystal it is difficult to understand so could you please explain here as i have write above code with the help of code submitted by neal , and actually i myself use some other technique to generate numbers in this solution and the code accepted and i was suprised because i used some random things, so could you please tell me some mathematics behind this that how it is working , and i also submitted two codes ,in one i was increasing x by 1e5 and in another one i was increasing by 1e8, and suprisingly the code with 1e5 accepted and with 1e8 it was giving wrong answer on test 5 . both code links are With x+=1e5 and with x+=1e8. and I have one more doubt when i was using M = 1e9+7 the code with x+=1e5 accepted and in same code i was using M = 999999937 in the code it is giving WA on test 5.

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

        i have asked in above mentioned comment

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

I mean to crystaI mistakenly same user name of both ids

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

Why is this giving TLE I have used Dijkstra Algo total states are 2 * N and number of edges are also of order N i.e M <= N

My approach use state space formulation


total Time Complexity = O( N LOG(N) ) multiplied by 2 as i am using dijkstra a 2 times; (node, 0) represents we don't have a horse (node, 1) we have the horse if( node has a horse in it and you are in the state node, 0 ) go to state (node, 1) with 0 cost as mentioned in the question if we are at (node, 1) then we can only go to (child, 1) with cost edgeWeight / 2 if we are at (node, 0) then we can only go to (child, 0) with cost edgeWeight run this dijkstra from node number 1 and node number n for all nodes maximise the minimum distance from each node then for all nodes minimise the distance and find the minimum

The approach seems correct as it is not giving WA, but fails to pass the time limit

here is the submission link Getting TLE on Test case 9 282838495

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

    Inefficient Dijkstra implementation — a same node tuple can exist in the PQ multiple times, and you need to skip the later ones instead of rerunning them as it could bloat the whole process into Bellman-Ford all over again.

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

      Damn lol I forgot to use the vis array which declared globally but i didn't use it in the dijkstra implementation

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

Problem H , Did anyone solve this with Divide and Conquer?

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

    hey, could you please help me to clear my doubt i mentioned above

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

I loved problem F

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

In D , Can someone explain the 5th test case, the job is from 2 to 8, so why my answer can't be 2(brother) and 1(mother) ?

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

In problem C, we can avoid sorting the input by using the nth_element function, thus giving a time complexity of $$$O(n)$$$.

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

would appreciate if u could just go through this post and address my querry related to problem E(https://mirror.codeforces.com/blog/entry/134511) .

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

what is wrong in my code it is giving TLE on test 2 solution E

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

Thanks ! I've harvest a lot from problem F.

»
16 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

We should drink the latest milk ~