Tommyr7's blog

By Tommyr7, history, 12 days ago, In English,

Hi, all!

This is not Tommyr7, but the impostor behind the round (guess who I am? :P). The statements are written by me. The characters in the round feature, again, the Monogatari anime series, and to be more specific, Nisemonogatari: Fake Tale. The statements involve stories with fake things and oddities, but as per tradition, contain no spoilers. Thank you, everyone, and hope you've all enjoyed the round!

On a side note, special kudos to the best impostors of the round (except me, lol)!

Any feedback on problems and tutorials are welcome -- we look forward to doing even better in the future!

Here are hints for all problems and detailed tutorials!


Hints

Problem A
Problem B
Problem C
Problem D
Problem E

Tutorials

869A - The Artful Expedient

Author Tommyr7, cyand1317 / Preparation Tommyr7, cyand1317 / Tutorial cyand1317

Tutorial
Solution 1 (Tommyr7)
Solution 2 (cyand1317)

869B - The Eternal Immortality

Author Tommyr7 / Preparation Tommyr7 / Tutorial cyand1317

Tutorial
Model solution (Tommyr7)

869C - The Intriguing Obsession

Author Tommyr7 / Preparation Tommyr7 / Tutorial Tommyr7

Tutorial
Model solution (Tommyr7)

869D - The Overdosing Ubiquity

Author quailty / Preparation quailty / Tutorial quailty

Tutorial
Model solution (quailty)

869E - The Untended Antiquity

Author Tommyr7 / Preparation Tommyr7, cyand1317, visitWorld / Tutorial cyand1317

Tutorial
Solution 1 (visitWorld)
Solution 2 (Tommyr7)

Tommyr7: I do hope you all enjoyed yourselves during the contest. See you next time!

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

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

Maybe swap D and E will be better

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

    Maybe... It's my issue...

    (I firstly thought problem D is just difficult to code, but easy to get the right solution, but after the contest I found that I was wrong.)

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

      Yes, it's easy to figure out the solution for D, but i can not implement it in 1 hour. And i don't know why i forgot to put random in E :(

  • »
    »
    12 days ago, # ^ |
      Vote: I like it -15 Vote: I do not like it

    I agree with you.But I can't solve the C.The contest is always showing wrong answer

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

I know the answer is always Karen but could someone tell me how this gives a wrong answer? It seems super simple so this is driving me a tad bit insane

n = int(raw_input())
x = map(int,raw_input().split())
y = map(int,raw_input().split())

numbers = set(x+y)

count = 0
for i in range(n):
    for j in range(n):
        if x[i] ^ y[i] in numbers:
            count += 1

if count % 2 == 0:
    print "Karen"
else:
    print "Koyomi"
  • »
    »
    12 days ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    I saw a lot of that in the room after systest — I don't know how I missed that.

    You are doing x[i]^y[i], which is supposed to be x[i]^y[j]. Hope this helps.

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

      Goodness, I feel dumb. Thanks rkm!

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

        I made the exact same error. So don't feel bad. This can happen to everybody.

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

        rkm ? what does it mean?

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

          That's nickname of purple guy who helped him.

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

            oh , i see , but i want to know the full name ,Lol!

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

    Is y[j] not y[i], I made the same mistake too.

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

    Probaly because of this typo: x[i] ^ y[i]

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

    Same problem. Mine gave WA for a long time too until I changed it to the O(1) solution. :/

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

    I found that many people have made such a mistake, many of my friends are the same.

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

    What computer language is this? python? i guess...

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

why A div2 get TLE with map

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

    n*n = 4,000,000, plus the log(n) lookups in a map it should not pass, however with an unordered_map/set it passes. My submission

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

      but i dont use map.find() i write map[]>=1 which is in o(1)

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

        map[] is still and actually worse, because if the index doesn't exist, it will add one after the operation increasing the value of n after each query.

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

      n*n*logn should fit

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

    Use Can Use This Condition:

    if(mp.find(a[i]^b[j])!=mp.end())c++;

    instead of this condition:

    if(mp[a[i]^b[j]])c++;

    TLE: 31073258 AC: 31088664``

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

    that's why i used set, which has O(logN) finding complexity!

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

    use unordered_map

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

.....

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

For me, my solution in problem A is the shortest that I have ever done in Codeforces

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

Can someone please explain the following solution: http://codeforces.com/contest/869/submission/31075785

Is it some kind of range update on 2D BIT?

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

There is a tiny mistake in the editorial. For problem A, it is 2·106 instead of 2·105, so the size of array should be at least 221 = 2097152.

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

Regarding problem A: during contest several participants raised the doubt that the number of pairs in sample 2 should be 20 instead of 16. Would anyone mind explaining the reason? :)

Upd. Figured it out. When you write i ^ j instead of x[i] ^ y[j] you get the answer 20.

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

I want to know why A di2 TLE with map :(

  • »
    »
    12 days ago, # ^ |
    Rev. 3   Vote: I like it +9 Vote: I do not like it

    Does your code look like mp[x[i] ^ y[j]]? You should be careful, because only by calling operator[] with key on map, the corresponding value is constructed. This makes a really large map (up to 4000000) in this problem, which may result in TLE. Use mp.find(x[i] ^ y[j]) instead.

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

      I think you are right!

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

      yes i use the operator[] but this will result in n*n map size i know but n*n map size is okay as using mp[x[i] ^ y[j]] is in o(1) and n*n size wont cause MLE

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

        Nope, the time complexity of mp[x[i] ^ y[j]] is , where N is the size of the map. Also there are several issues that make your code slow. (For instance, long long.)

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

Anyone can tell me how you guys managed to use the idea of randomization for problem E? I can see a lot of submissions using this idea.

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

    Try to view the problem as building blocks with random heights on a platform.

    Then "Two points are connected" is equivalent to "Two points are on the same height".

    After that you can use Fenwick Tree to maintain the heights of all points.

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

The constraints given in problem A are wrong thats why my solution did not pass The constraints for xi and yi given are 1 — 2*1000000 whereas actually the constraints are 1-4*1000000. Please correct me if I am wrong. You can see my submissions for problem 'A' Previous submission with given constraints New submission with change in only size of array 'ha'

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

    Sorry it was my fault. Please ignore the comment

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

Please help me! For problem A, why did my solution give WA on test case 4? I though of the fact that if (x,y) satisfies the property, then so does (y,x). Hence for x!=y, the count will always be even. So I just calculated the count for all x=y cases. Here is my code: https://pastebin.com/XqRjHbBL

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

May somebody help me? For problem 'A': I've got WA in test 48, but couldn't find where I was wrong. Then i worked in CF Sandbox, added to my solution ' cout << ""; ' and got full score. Why?)

Code(that cout has commented):

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    int a[n], b[n], com[2*n];
    
    int t;
    for(int i=0; i<n; i++) {
        cin >> t;
        a[i] = t;
        com[i] = t;
    }
    for(int i=0; i<n; i++) {
        cin >> t;
        b[i] = t;
        com[i+n] = t;
    }
    sort(com, com+2*n);
    int k=0;
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            int r = (a[i] ^ b[j]);
            // cout << "";
            if(*lower_bound(com, com+2*n, r) == r)  
                k++;
        }
    }
    cout << (k % 2 == 1 ? "Koyomi" : "Karen");
    return 0;
}
»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it
»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Well because all the answers in the first question is "Karen". Completely wrong code also got A/C :p :p .31069801

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

Can anyone explain solution of the problem C?

  • »
    »
    12 days ago, # ^ |
    Rev. 5   Vote: I like it +30 Vote: I do not like it

    I will explain mine, but I am not sure that it is the expected solution.

    You can check my code here: 31079668

    For me, the most important piece of information from the statement (apart from constraints, heh) is the following:

    For any two islands of the same colour, either they shouldn't be reached from each other through bridges, or the shortest distance between them is at least 3

    Let's think about what this constraint is imposing and lets enumerate the impositions:

    1) There can be no edge between two islands of the same colour. Why? Because if there was an edge between two islands of the same colour, their shortest distance would be 1, which is less than 3. Good! this means that we only need to consider edges between islands of different colours. We even have an upper bound right now: 2ab × 2bc × 2ac (the product of all possible subsets of edges between islands of different colours). In fact, this is the very first formula I tried.

    2) There can be no pair of islands of the same colour ai, aj such that they both have an edge to the same city of different color bk. Why? because if they had, then the shortest distance between ai and aj would be 2, which is less than 3. This second fact is the cause that makes the previous formula to give an upper bound, but not the correct amount.

    So, with these observations we can conclude that there is no need to consider the three colours at the same time, it will be enough to compute the product of the number of possible edge configurations between all the possible pairs of colours. The problem is that the formula is not as direct as a power of two or something similar, so let's think about it.

    Let's try to build a function f(r, b) that tells us in how many ways we can connect r red islands with b black islands without violating constraints. The base case for me is f(0, b) = f(r, 0) = 1. The non-base case is f(r, b) = f(r - 1, b) + b × f(r - 1, b - 1). Why? f(r-1, b) is the number of ways that you get if you ignore the rth red island. If we want to connect the rth red island with some black island we have b choices, so we must add the amount b × f(r - 1, b - 1). Note that we only need to consider where we put a single edge, because more than one edge from the rth red island to the black cluster would imply a violation of constraint 2. Given that a, b, c ≤ 5000 we can compute this formula with dynamic programming. Also, we are ignoring intra-cluster edges, as they would violate constraint 1. I hope that this convinces you enough about the correctness of the formula.

    Once we have these values computed, we must output f(a, b) × f(a, c) × f(b, c).

    I am not very sure if this solution was the expected one given the time it takes to complete a single test case and the time limit. Even if it is in java, I am not 100% sure.

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

      how it is 2^(ab) × 2^(bc) × 2^(ac) in the first case

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

        Oop

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

        For two clusters having islands a and b, the number of bridges will be a*b. For all the pairs, the total number of bridges are a*b + b*c + a*c and every bridge has two possibility i.e. either to exist or not. So the upperbound is 2^(a*b + b*c + c*a)

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

      Correction. f(r-1, b) is the number of ways that you get if you ignore the rth red island.

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

      You dont need to use the recursion to calculate f(a, b). Let f(a, b) denotes total number of ways to connect two clusters with a and b islands respectively.
      f(a, b) will be .

      Final answer will f(a, b) * f(b, c) * f(a, c)

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

      nice explanation.

    • »
      »
      »
      12 days ago, # ^ |
      Rev. 9   Vote: I like it +6 Vote: I do not like it

      Here's an O(n) solution for calculating f(r, b)
      AC CODE

      f(r, b) = 0; r >= b for(i=0; i<=b; i++) f(r,b) += (P(r,i) * C(b,i)) % MOD

      where P(r, i) = permutations of i things out of r things = r!/(r-i)! ; C(b, i) = b choose i = b!/(i! * (b-i)!)

      Just precalculate factorials, inverse factorials and that would solve it O(n)

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

      Awesome

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

      "So, with these observations we can conclude that there is no need to consider the three colours at the same time" I didn't understand it ! why we are ignoring the three colours at a time? can't there be any bridges like 1->2->3->1 ?

      please correct me!

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

        You can indeed have 1>2>3>1 bridges, however, saying:

        "...there is no need to consider the three colours at the same time"

        doesn't imply that you won't consider the 1>2>3>1 cases for the solution, it just means that for the solution build process, you don't need to consider the three colour islands at the same time.

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

      I understood the first part of your formula on the right hand side should be f(r-1,b). But why is the second part b x f(r-1,b-1)? Specifically why b-1 ? Can you please explain? Thanks.

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

Did anyone actually used the solution for A that prints "Karen"?

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

    Yes, myself: 31068666

    I got an RTE previously with a naive solution because I did not allocate enough space for the first 2N numbers. I returned to the statement, read the words "ordered pair" and realized the trick.

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

    yup and it's totally correct soln, but what i did'nt get was the explanation of first testcase, Since it is mentioned in ques that he has to make pair of (x,y) but they are forming pairs within set of x and in that too they have considered (1,1) (3,3) but not (2,2). Can anyone explain why??

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

      They have considered (3,3). But (3,3) doesn't satisfy the constraint because 2 xor 5 is 7 which is not included in 2N numbers.

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

Is there any deterministic solution for E?

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

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

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

Where can I find more counting/combinatorial problems like C? I can never get the idea in-contest, and its hard to find more of them to practice

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

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

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

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

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

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

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

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

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

This is my first Codeforces contest and I have doubts regarding Tommyr7's solution to Problem C.

  1. Why is the value of Maxn 5007 (The constraint is 1 <= a,b,c <= 5000)? Souldn't it be 5000?

  2. Also, why taking %modp at every step is necessary?

  3. When dealing with factorials and combinations, is it a norm to store the values in advance for fast calculations? I am quite intrigued by the beauty of the code.

  • »
    »
    12 days ago, # ^ |
    Rev. 3   Vote: I like it +25 Vote: I do not like it

    Thanks for supporting my contest. Here are my answers: 1.Well, 1<=a,b,c<=5000 is true, but you know sometimes your program gets an RE if you just use array size of 5000 (if you have some operations like a[i+1]), it's a good habit to make the size of array a little bigger. (Just a little is needed) 2.It's unnecessary. But sometimes if the answer is too large, a multiplies b may get WA (two very large integers may get an answer less than 0). For example, (1e12)*(1e12) will get WA. So, talking %modp at every step is also one of my habits. (Of course, it's not necessary) 3.Actually, it's not necessary again. But, store the values in advance can make me clear what I should do next. I don't need to be careful about the combination values if I have stored them in advance. This can make me have more possibility to get Accepted or I can code it faster.

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

I think the problem D is actually the hardest one.

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

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

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

I want to learn about quad trees and also want to solve some good problems of quad trees. Please share the links of some good tutorial on quad tree, and the links to some good problems ! Thank you !

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

    quad tree is not good, it will be worst case O(N), where N is the length of the box, if your query is the upper line. That's why you can't solve any problems with it.

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

869B — The Eternal Immortality ,// the Tutorial of this question said "and it's not hard to prove a tighter upper bound of 5." hence my understanding is the maximum Output is 5? but i want to give a example ,such as ,if the Input is 0 3 ,then Output should be 6 ,but the tutorial said "a tighter upper bound of 5" so it exceed the bound 5..... my point of view...

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

    No, it means if you calculate (a + 1) × (a + 2) × ... and stop when the last digit becomes zero, you will stop before or at a + 5.

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

      seems to understand it! thanks! buddy!

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

i read solution of problems D, try to understand code.but i got no idea. can anyone explain it for me. thanks

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

a

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

    it means all the numbers are different! Note:these 2*n numbers all different ... cuz the statement says there doesn't exit “ xi=yj ” “xi=xj” “yi=yj” ,, In short, all the numbers are different! hope you can got it!

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

2 wrong hacks Ah!! anyone please provide me a cup of water to die :(

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

You have typo in word "Suppuse".

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

I probably misunderstood E, but why can't we use 2D segment tree in the next way: 1: set square [r1,r2]*[c1,c2] to unique value 2: set square [r1,r2]*[c1,c2] to same value as (r1-1, c1-1) 3: check if (r1, c1), (r2, c2) have the same value?

Thank you!

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

I was confused that problem E why has to be randomize? I try to replace

if (t==1)
     del.first=rand();
     del.second=rand();

with

if (t==1)
{
	del.first=i;//the iterate index
	del.second=i;

I submit this a little bit different solution and this pass 19 test,and fail in test 20. I think it may be different set of number has the same sum,but in this situation,the collission probility may be not 2-64.

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

In problem E for the BIT solution,why is probability of collision 2^-64 ? Suppose a certain cell belongs in region 1 and 2, and there is another cell that lies in region 3. If we were to query whether a path is possible between them, the output would be Yes even though it was supposed to be no, and there was no repetition in random number generation

Intuitively I feel that the probability of collision is still extremely low, but I am unable to prove it. Can anyone pls help me?

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

    Let's assume you assign 64-bit random value for each rectangle. If you want to check reachability for two points you can calculate xor of covering rectangles. If this values aren't equal — points aren't reachable for sure. Otherwise there can be a collision. Let's estimate its probability. One can observe that bits of values are in fact independent. For one bit: this bit will be equal in two calculated numbers with probability (xor of any non-empty set of bits is either 0 or 1 with equal probability, because and and we generate bits with equal probability too). So we obtain probability of collision.

»
7 days ago, # |
  Vote: I like it +5 Vote: I do not like it

The following is a GNU C++11 solution for problem 869E - The Untended Antiquity:

31224413

The solution uses a rectangle_tree class whose root node is the entire 2500 x 2500 area. The children of each node (u) in the rectangle_tree are the largest non-intersecting rectangles contained in (u). Insertions and deletions update the tree according to inserted/deleted rectangles. A walk query returns "Yes" if and only if the smallest rectangles containing the source and the target cells are the same.

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

A way can be there in total ways or not when there is no bridge among any islands?

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

what is meaning of -del in this statement udel=make_pair(-del.first,-del.second)