awoo's blog

By awoo, history, 2 years ago, translation, In English

1598A - Computer Game

Idea: BledDest

Tutorial
Solution (BledDest)

1598B - Groups

Idea: fcspartakm

Tutorial
Solution (BledDest)

1598C - Delete Two Elements

Idea: fcspartakm

Tutorial
Solution (Neon)

1598D - Training Session

Idea: BledDest

Tutorial
Solution (Neon)

1598E - Staircases

Idea: BledDest

Tutorial
Solution (awoo)

1598F - RBS

Idea: BledDest

Tutorial
Solution (BledDest)

1598G - The Sum of Good Numbers

Idea: BledDest

Tutorial
Solution (Neon)
  • Vote: I like it
  • +114
  • Vote: I do not like it

| Write comment?
»
2 years ago, # |
Rev. 4   Vote: I like it +11 Vote: I do not like it

The easiest solution for C(in my opinion): 131432277

P.S. sum * (n-2) = (sum — a[i] — a[j]) * n => we can find for every a[i] all a[j] in O(n log n) using binary search

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

    If you simplify that equation, you would get (a[i] + a[j]) = (2 * sum) / n, so basically this is just a 2-sum problem where the target value is (2 * sum) / n,

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

      Yep, u r right (:

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

        Can you please check my soln. I have used 2-sum approach but it is giving me WA on test 2. 131563369

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

          ++

          I also tried the same way and getting wa on 78th in 2tc..hbarp can you pls tell me why it's wa.

          solution: 131653903

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

            I havent looked at the correctness of your algorithm but ans = ans + c * d; line has int overflow for sure.

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

              XD. Thanks, for mentioning this. now, after using it long it still showing wa on that tc. Can you please tell me why is it so?

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

                Changing ans = ans + c * d; to ans = 1LL*ans + c * d; doesn't fixes anything. ans is already long long int. Over flow is in multiplication of c*d, change this to ans = ans + c*1LL*d.

                Also ll val = (n * (n - 1)) / 2; has int overflow. Just having val of type long long int doesn't do anything. n and n-1 are still of int type. Change this to n*1LL*(n-1)/2.

                Also, next time just uses C++ 64 bit and long long everywhere.

                Also, if (st.size() == 1) is incorrect fix. You will still get WA on

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

sorry i forgot that x is a good number :-_

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

IDk why but my solution for C gives TLE on Test 17 even though it's the exact same solution as the tester's : https://codeforces.com/contest/1598/submission/131542518

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

Why using unordered_map gives TLE in this question... searching elements using hash map should be faster than the map which takes log(n) time to search instead.
131514464

Also I don't get it... how by adding just these 2 lines which where on a blog,
mp.reserve(1024);
mp.max_load_factor(0.25);
solves the problem of TLE and my soln gets accepted.
131524838

Then I tried a custom hash function rather than the built-in hash function. Which also got accepted. Also the same solution gets accepted in python using dictionaries which also uses hashmap.
Does this mean that the C++ built-in hash function is not good ?
131520347

I tried to find but didn't get some concrete answers when to use map or unordered_map ?
Or using custom hash is better not ?
Please if anyone can help it in.

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

    There are many hacks on unordered_map and I suppose we should avoid using it in Codeforces contests. Here a blog written by neal showing how it works.

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

    It's just because c++'s hash function is deterministic so people can hack on this. max_load_factor() basically increase the number of buckets which will break the malicious hacks.

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

    Note to self: ALWAYS use custom hash function when dealing with unordered map no matter how unnecesary in a codeforces contest

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

      The funny thing in this contest is sjcsjc 's template had custom_hash but still he got hacked for using c++ default hash. 131404435 After that he dropped from 4th rank to 87th rank among rated users.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it
    mp.reserve(1024);
    mp.max_load_factor(0.25);
    

    only changes the test that's required to hack the solution, it doesn't make it unhackable.

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

Nice solution for D!

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

I suppose that the time complexity of F should be $$$O(n2^n + A\log A)$$$ instead of $$$O(2^n + A\log A)$$$. (:

Could someone tell me if there are some mistakes?

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

    Can you tell me what is A in this time complexity? I understand where $$$N$$$ and $$$2^N$$$ comes from but I just can't find anything related to $$$A$$$.

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

    You are right, it's $$$n\cdot 2^n$$$ instead of $$$2^n$$$.

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

Any other solution for problem D?

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

In Problem D, I don't understand why the only bad triples are (xa,ya),(xb,ya),(xa,by). Isn't there a possibility of having three same topics, such (1, 1), (1, 2), (1, 3)? I've been looking at the explanation for so long but still can't figure it out :(

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

    but their difficulties are different so they aren't bad triples.

    The problem statement says "at least one of the conditions are met"

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

For D, can someone explain to me why there can't be a triple of the form [(Xa, Ya) , (Xb , Yb) , (Xa, Yb)] ? EDIT: I figured it out, it's actually the same thing except that the third pair is the central one, instead of the first.

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

For 1598C:

No, you don't have to use map in such a hacky way (or in another word, full of patches).

131572801

======================================

Instead of keeping a map of all elements, we keep a map for number of first i items ([0, i-1])

So the core logic can be much more easier:

in C#:

for (int i = 0; i < n; i++){
    // update the answer
    if (cnt.ContainsKey(target - data[i])) answer += cnt[target - data[i]];
    // update the cnt map, for (i + 1) to use.
    if (!cnt.ContainsKey(data[i])) cnt.Add(data[i], 0);
    cnt[data[i]]++;
}

or in C++:

for (int i = 0; i < n; i++){
    // update the answer
    answer += cnt[target - data[i]];
    // update the cnt map, for (i + 1) to use.
    cnt[data[i]]++;
}
»
2 years ago, # |
Rev. 12   Vote: I like it 0 Vote: I do not like it

i tried to add photo for my comment but the comment become empty any one can help me

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

In problem D can anyone please explain why we won't be overcounting in the editorial solution?

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

    problems and diff. are unique pair, no overlap when multiplication as in editorial

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

Alternative solution for 1598D - Training Session. I did see restriction that all problems pairs of parameters are different, but I had no idea how to use this fact. My solution doesn't rely on this fact at all. Solution turned out to be much harder so I wasted a lot of time to implement it during round.

Here is main idea. Think of how to calculate all triples with different topics.

There is easy way

Apply the same idea to problem's difficulties. We count something twice. What to do?

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

Detailed description how to implement 1598E - Staircases in $$$O((n + m + q) \log (n+m))$$$ time and space.

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

for que B https://codeforces.com/contest/1598/submission/131729850 can u check this once i don't which test i am missing so pls

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

    if(r>=n/2&&q>=n/2&&s==0)

    {

    cout<<"YES"<<endl;

    y=1; break;//you forget a break here

    }

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

A slightly different solution of 1598F - RBS.

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

in problem C why i am getting tle.. Pls tell[problem:1598C] https://codeforces.com/contest/1598/submission/131512968

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

    This is due to the use of unordered_map instead of map. Try map and you will get AC.

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

      even , i used unordered map earlier it also gave me tle but when i am using map it is not giving tle . can anyone explain why is it so ? please.

      • »
        »
        »
        »
        21 month(s) ago, # ^ |
        Rev. 4   Vote: I like it 0 Vote: I do not like it

        I think it may be because of special anti-hash testcases.

        Unordered map relies on hashing to determine where the value of a key is stored. When there are hash collisions, the the hash function makes the collided keys share the same position. This is done with a linked list, which needs to be linearly searched if you are looking for a key that has collided with other keys.

        Essentially, you can design testcases that abuse this workaround, causing unordered_map access complexity to approach O(n)

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

132438878 can anybody help me with this I'm getting tle even though the time complexity of my son is same as that of the solution :)

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

My solution for F fails at test 32. Can someone please look at the submission and point out the error?

I would be happy to explain what my code does if it is not clear. Thanks.

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

A Dp approach to problem E in $$$O(NM + Q*min(N,M))$$$

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

For problem D, is there anyway to find the number of triples that are different both in topic and in difficulty?

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem A can be solved using DFS like this: 161393885.

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

hey I have a doubt in ques C sorry if its too silly.. should not the ans+=min(freq of a[j] , freq of (2*sum/n a[j]). ie minimum of the counts should be added right? because if needed sum is 10 and freq of 7 is 4 and freq of 3 is 2 then pair with sum 10 should be only 2 right?

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

    the number of pair should 4 times 2 equals 8.

    You have four different ways to choose a 7 and two different ways to choose a 3.