Google Code Jam 2021

4 years ago, # ^ |

+16

Yeah I didn't even know there was a greedy idea that worked only for positive weights till I opened the comments here.

→ Reply

PNVZarif

4 years ago, # ^ |

I didn't get a solution that works for the P2 but doesn't work for the hidden 1 point

→ Reply

kitchent

4 years ago, # ^ |

← Rev. 4 →

-117

Deleted

→ Reply

PNVZarif

4 years ago, # ^ |

+25

OMG, contest is still running, don't give any hint. Delete this reply now.

→ Reply

vrooooom

4 years ago, # ^ |

I thought the discussion of the qualification round was allowed?

Google Code Jam Rules state that

Sharing information with other contestants is permitted in the Qualification round only. Notwithstanding Section 7.1(E) of the Terms, you will not be disqualified for using information from or sharing information with others about problems during the Qualification Round of Code Jam.

→ Reply

Venti_chai

4 years ago, # ^ |

← Rev. 2 →

+20

It is permitted, but it sort of diminishes the fun of the contest imo.

→ Reply

oversolver

4 years ago, # |

← Rev. 2 →

→ Reply

arcanewizard37

4 years ago, # |

How many point do we need to qualify? Is it decided after?

→ Reply

practicener

4 years ago, # ^ |

30 points. It is mentioned in the rules and FAQ. You can have a look at that.

→ Reply

aeiou1

4 years ago, # |

I'm getting this error in interactive problem on my laptop: "judge: Case #71 failed: Couldn't read a valid line". I checked and it's actually EOFError. I submitted my solution anyway and it got 18 pts (as of right now), so I guess it's correct, more or less. So why such error?

→ Reply

ibrahim_habib

4 years ago, # |

+13

Are you sure that the start and end time for qualification round are correct?

The end time in the post is after ~15 hour. While Codejam page shows that the remaining time is only ~8 hours.

Please check this and update the post if there is an error. Some people may miss the round due to that.

→ Reply

fdironia

4 years ago, # ^ |

According to Code Jam Rules 3.1,

Code Jam will start with the online Qualification Round on Friday, March 26, 2021 at 13:00 UTC and run for thirty (30) hours, ending on Saturday, March 27, 2021 at 19:00 UTC.

So this post writes a wrong start and end time of qualification round.

By the way, schedule of other rounds are consistent with the rules and schedule page of Code Jam.

→ Reply

eatmore

4 years ago, # ^ |

+30

Google changed the schedule of the qualification round after this post was published. I updated the post.

→ Reply

hdude0164

4 years ago, # ^ |

-44

Sir, please extend the deadline for Google Codejam, I registered for the event and didn't got any mail and thus missed the round, now just 7 minutes left and I saw this post on Codeforces and then came to know that the round is almost over, please extend it now. Please

→ Reply

slim-shady

4 years ago, # ^ |

+14

Bruh, it doesn't work like that. It is the world's most prestigious competitive programming championship, not gully cricket.

→ Reply

Dan4Life

4 years ago, # ^ |

How did your extended Google Codejam round go? :P

→ Reply

4 years ago, # |

← Rev. 2 →

I think Google might need to apply a cheating detection algorithm to the Cheating Detection problem

→ Reply

4 years ago, # ^ |

To be fair, Cheating Detection is solvable by even someone with no competitive coding background if they think about the Math behind it for some time and just try out ideas that seem like they might work.

→ Reply

https://codingcompetitions.withgoogle.com/codejam/rulesandterms

4 years ago, # ^ |

I agree, however the pattern of submissions in the last 2-3 hours was pretty suspicious. Literally hundreds of new entrants submitting all 5 questions at the same time, in a very short time frame.

→ Reply

ecnerwala

4 years ago, # ^ |

+23

Note that discussing solutions is actually allowed for this round:

7.1 Qualification Round. Sharing information with other contestants is permitted in the Qualification round only. Notwithstanding Section 7.1(E) of the Terms, you will not be disqualified for using information from or sharing information with others about problems during the Qualification Round of Code Jam.

→ Reply

4 years ago, # ^ |

Very interesting! Thanks for sharing.

→ Reply

4 years ago, # |

← Rev. 4 →

+17

I've no proof to my solution of Cheating Detection but I did something which looked good to me and it worked :)

I took all the players having $$$>=5000$$$ score and sorted them in non increasing order of the solves. Assuming no cheating, I thought the adjacent players will have less mismatches because of similarity in value of $$$S$$$. Mismatch in a particular question is when score of player $$$i$$$ is different from score of player $$$j$$$. Calculated mismatch for all players. For players which are not on the end points, I took the average value.

I defined a function $$$f_i = a \cdot mismatch_i + b \cdot solves_i $$$.

I took the player having the maximum $$$f$$$ because there is good chance for the cheater to have good amount of solves and good amount of mismatches from its adjacents.

Tried bunch of values for $$$a$$$ and $$$b$$$ and it passed both sub-tasks with $$$a=5$$$ and $$$b=4$$$.

Solution (bit messy)

'''Author- Akshit Monga'''

# import sys
# # For getting input from input.txt file
# sys.stdin = open('output.txt', 'r')

# # Printing the Output to output.txt file
# sys.stdout = open('output11.txt', 'w')
from sys import stdin, stdout
from fractions import Fraction
from math import log,e
# input = stdin.readline
import random
t = int(input())
p = int(input())
for _ in range(t):
    stdout.write("Case #"+str(_ + 1)+": ")
    strs=[]
    cheater=1
    good=[]
    d={}
    for i in range(100):
        s=input().strip()
        strs.append(s)
        # val=s.count('1')-s.count('0')
        p=s.count('1')
        if p>=5000:
            good.append((p,i+1))
            d[i+1]=p
    good=sorted(good,reverse=True)
    # good=good[:29]
    l=len(good)
    if l<=2:
        print(good[0][1])
        continue
    mismatch={}
    ma=0
    for i in range(l-1):
        p1=good[i][1]-1
        p2=good[i+1][1]-1
        mis=0
        for j in range(10**4):
            if strs[p1][j]!=strs[p2][j]:
                mis+=1
        # print(p1+1,p2+1,mis)
        if p1+1 not in mismatch:
            mismatch[p1+1]=mis
            if i==0:
                if mismatch[p1 + 1] > ma:
                    ma = mismatch[p1 + 1]
                    ans = p1 + 1
        else:
            mismatch[p1+1]=(mis+mismatch[p1+1])/2
            if mismatch[p1 + 1] > ma:
                ma = mismatch[p1 + 1]
                ans = p1 + 1
        if p2+1 not in mismatch:
            mismatch[p2+1]=mis
            if i==l-2:
                if mismatch[p2 + 1] > ma:
                    ma = mismatch[p2 + 1]
                    ans = p2 + 1
        else:
            mismatch[p2+1]=(mis+mismatch[p2+1])/2
            if mismatch[p2 + 1] > ma:
                ma = mismatch[p2 + 1]
                ans = p2 + 1

    # print(mismatch)
    misss=[]
    for i in mismatch:
        misss.append((i,mismatch[i]))
    misss=sorted(misss,key=lambda x:x[1],reverse=True)
    fitness=0
    ans=-1
    for i in mismatch:
        val=5*mismatch[i]+4*d[i]
        if val>fitness:
            fitness=val
            ans=i
    # print(good)
    # print(misss)
    print(ans)

Sadly, I missed $$$3rd$$$ sub-task of Moons and Umbrellas and couldn't get perfect score. I should've tested it properly :(

→ Reply

4 years ago, # |

← Rev. 2 →

How to "prove" the full solution to P5? I just tried an intuitive idea hoping it would pass Test Set 1 and got AC on both Test Sets.

I'm assuming there are several different approaches that works, so I'm going to roughly state my solution:

Let the easyness of a question be the number of people who solve it.

Then I just select the participant with the max variance of easyness over problems they solve.

I think its pretty intuitive why this is a fairly decent metric, but how do you even begin to prove that it will work on average at least 86% of the time with random data?

Was there some other idea that was easy to prove?

Code

#include <bits/stdc++.h>
#define int long long
using pii=std::pair<int,int>;
using namespace std;

const int maxn = 105, maxq = 1e4 + 5;

int t, p, cnt[maxq], solved[maxn][maxq], have[maxn], mean[maxn], deviation[maxn];
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> t >> p;
    for(int cases = 0; cases < t; cases++)
    {
        for(int j = 0; j < 10000; j++)
            cnt[j] = 0;
        for(int i = 0; i < 100; i++)
            deviation[i] = mean[i] = have[i] = 0;
        for(int i = 0; i < 100; i++)
        {
            string s;
            cin >> s;
            for(int j = 0; j < 10000; j++)
            {
                solved[i][j] = s[j] - '0';
                cnt[j] += solved[i][j];
            }
        }
        for(int i = 0; i < 100; i++)
        {
            for(int j = 0; j < 10000; j++)
                if(solved[i][j])
                {
                    mean[i] += cnt[j];
                    have[i]++;
                }
            if(!have[i])
                continue;
            // rounding shouldn't matter
            mean[i] /= have[i];
            for(int j = 0; j < 10000; j++)
                if(solved[i][j])
                {
                    int diff = abs(cnt[j] - mean[i]);
                    deviation[i] += diff * diff;
                }
            deviation[i] /= have[i];
        }
        int take = 0;
        for(int i = 1; i < 100; i++)
            if(deviation[i] > deviation[take])
                take = i;
        cout << "Case #" << (cases + 1) << ": " << take + 1 << "\n";
    }
    return 0;
}

→ Reply

4 years ago, # |

← Rev. 2 →

+26

Problems solutions:

→ Reply

Coder

4 years ago, # ^ |

Similar in E, divide success rate in 10% hardest questions by overall success rate and whoever has the highest is the cheater.

→ Reply

forcdc

4 years ago, # ^ |

In C's solution

"If you reversed from last to beginning, you can reverse it again from beginning to last."

Can someone please explain it a bit more

Thanks!

→ Reply

4 years ago, # ^ |

For example, if we have initial array:

1,2,3,4,5

If we reversed 4th index till last:

1,2,3,5,4

If we reversed 3rd index till last:

1,2,4,5,3

We have an array of: 1,2,4,5,3

Now, if we reversed from 3rd index till last:

1,2,3,5,4

If we reversed from 4th index till last:

1,2,3,4,5

We returned to the original array. Meaning, that this operation, is reversible so the problem turned from finding an array with C to find how many reverses you need to reach C(so it became really much easier like the first problem).

→ Reply

4 years ago, # |

← Rev. 2 →

+45

Thanks for the round! I think my E solution is considerably stronger than intended--I generated a suite of 2000 test cases locally and found, rather shockingly, that it had 100% accuracy on the sample. I also tested locally and found that it has 100% accuracy on the actual input.

For anyone curious, here's my approach. I sort the problems by solve counts and split them into 50 buckets of 200 problems each. Then, I assume the difficulty of problems in the i'th easiest bucket (using 0-indexing) is $$$-2.94 + 0.12i$$$. (In other words, I assume the buckets cover evenly distributed subintervals of $$$[-3, 3]$$$ and that the difficulty of each problem is approximated by the average difficulty in its bucket.) For each contestant, I iterate over all possible skill levels of the form $$$-3 + 0.06i$$$ (assuming that this will be a reasonable approximation for their actual skill), and I compute an error function (the sum of the squares of expected solve count minus actual solve count over the fifty buckets) for each player-skill level combination if the player is cheating and if they are not cheating. Then, I compute each player's minimum error function if they are cheating and minimum error function if they are not cheating, and I output the player who minimizes the quotient when the error function if the player cheats is divided by the error function if the player does not cheat.

Here's my code: https://pastebin.com/4Vy70PRg

→ Reply

4 years ago, # ^ |

Wow, that distribution is way more accurate than me just getting mean values which still has 99.9% success rate(10 failed on 5K cases).

→ Reply

4 years ago, # ^ |

I'm impressed that you're able to achieve such high accuracy with a relatively simple approach--thanks for sharing your solution!

→ Reply

4 years ago, # ^ |

+24

I am also impressed not just you xD.

→ Reply

ecnerwala

4 years ago, # ^ |

+34

If your success rate on 50% is very high, you can try evaluating accuracy when the cheater only cheats 10% of the time or something. My solution gets 1000/1000 with a 50% cheater, and about 80% accuracy on a 10% cheater. I bet you can do better though.

Here's my approach: The "theoretically correct" solution is to directly apply Bayesian analysis and evaluate a 10100-dimensional integral of conditional probabilities, because you have a complete set of priors of the inputs. This seems pretty infeasible (though maybe someone knows how?), so one approximation you can take is assuming that the Bayesian posterior of the people/problem ratings are all very sharp peaks, and you just try to estimate the location of the peak. You can do this iteratively by alternating optimizing people-ratings and optimizing problem-ratings. Once you've estimated the maximum-likelihood ratings, you can then take your conditional probabilities: Bayes' theorem says that you should rank people based on the ratio of $$$P(given-scores | cheating) / P(given-scores | not-cheating)$$$, which is a ratio of sigmoids.

→ Reply

4 years ago, # ^ |

My solution essentially has the same idea as yours, so I've tried my solution on a 10% cheater as you suggested. Although I get 100% accuracy on a 50% cheater, the result is around 5%.

Can you share more details on how do you optimize people and question ratings? How many iterations do you do? I could afford only 10, otherwise, I got TLE.

→ Reply

ecnerwala

4 years ago, # ^ |

I actually only do 1 iteration; I initialize the people ratings by taking the inverse of the sigmoid CDF of their solve rate (assuming questions are uniformly distributed), and then I ternary searched to find optimal problem ratings.

Did you change your constants in the Bayes' rule evaluation with the updated cheat percentages?

Code here: https://ideone.com/nRYKXS

→ Reply

4 years ago, # ^ |

You were right, I didn't change the constant in Bayes rule... Now the accuracy on 10% cheater is around 65%, which is not that bad, but far from your result.

My solution is substantially a log-likelihood gradient ascent, starting from same yours initial values. Probably with a better tuning of the learning rate and squeezing more the time limit to make more steps I can improve the result, but definitely ternary search is better.

Thanks!

→ Reply

_h_

4 years ago, # ^ |

+25

I used this Bayesian approach but with a simple one-step approximation for question difficulties like Geothermal. The algorithm is what Geothermal described except you replace the sum-of-squares error function with a log-likelihood. On 5000 test cases with a 10% cheater it passes 4156.

→ Reply

Mike_Mirzayanov_Is_Pussy

4 years ago, # |

How to solve problem D for hidden test case ?

I used binary search and number of iterations will be around $$$log2(3)+log2(4).....+log2(50)$$$ in worst case which is >200 but since data in input are randomly made , I think average could be less and thus it might pass the hidden test case .

Also when hidden test case verdict will be out ?

→ Reply

gaurav1903

4 years ago, # ^ |

← Rev. 2 →

-31

What you did is binary search .but if think carefully you'll find that actually you can split list into 3 parts at the same time. Here's my code in python3

t, n, q = map(int, input().split())
for i in range(0, t):
    done = 3
    print(1, 2, 3)
    y = int(input())
    if (y == 1):
        x = 2
        z = 3
    elif (y == 2):
        x = 1
        z = 3
    else:
        x = 1
        z = 2
    ans = [x, y, z]
    next = 4
    f = 0
    while (next < n + 1 and f == 0):
        start=0
        e = 0
        end = len(ans) - 1
        while (e == 0):
            
            a=start+(end-start+1)//3
            mid = (a + end) //2 + (a+end)%2
            # print(a,mid)
            # print(ans)
            print(ans[a], ans[mid], next)
            y = int(input())
            if (y == -1):
                f = 1
                break
            elif y == ans[a]:
                end=a-1
                if(start-end==1):
                    ans.insert(start,next)
                    e=1
                if(start==end):
                    end+=1
            elif y == ans[mid]:
                start=mid+1
                if(start-end==1):
                    ans.insert(start,next)
                    e=1
                if(start==end):
                    start=mid
            else:
                start=a+1
                end=mid-1
                if(start-end==1):
                    ans.insert(start,next)
                    e=1
                if(start==end):
                    start=start-1
                # if (mid - a == 1):
                #     ans.insert(mid, next)
                #     e = 1
        if (f == 1):
            break
        next += 1
    if (f == 1):
        break
    for i in range(0, len(ans)):
        print(ans[i], end=' ')
    print()
    y = int(input())
    if (y == -1):
        break

Hope it helps

→ Reply

gaurav1903

4 years ago, # ^ |

-19

why is my comment downvoted?? what did i do wrong?

→ Reply

Hakiobo

4 years ago, # ^ |

← Rev. 2 →

I would assume it's putting raw code directly in a comment

Instead of in a Spoiler

Like this

→ Reply

4 years ago, # ^ |

+31

Hidden case verdicts are available now. The main idea of D is to solve the problem using insertion sort in $$$O(n \log_3 n)$$$. Essentially, if the position of an element $$$x$$$ to be inserted is bounded within the range $$$[l, r]$$$, query $$$x$$$ with the elements at positions $$$\frac{2l+r}{3}$$$ and $$$\frac{l+2r}{3}.$$$ This will result in a range roughly $$$\frac{1}{3}$$$ as large, achieving the desired $$$n \log_3 n$$$ complexity.

→ Reply

4 years ago, # ^ |

← Rev. 3 →

Binary Search is actually sufficient as long as you ensure that a region of size $$$n$$$ is divided into at regions of size at most $$$\frac{n - 1}{2}$$$ and end the loop if you find the required point partway through.

I'm not sure how to show this reduces it enough but it passed the hidden subtask and didn't exceed an average of $$$165$$$ queries over a few thousand runs locally with random input. I think the uniform random test generation plays a role in it.

Code (ignore the unneeded messy endpoint conditions in check that aren't even needed)

#include <bits/stdc++.h>
#define int long long
using pii=std::pair<int,int>;
using namespace std;

int t, n, q;

int query(int x1, int x2, int x3)
{
    cout << x1 << " " << x2 << " " << x3 << endl;
    int resp;
    cin >> resp;
    assert(resp != -1);
    return resp;
}

int check(int x, int insval, vector<int>& vals)
{
    int eff = x;
    if(x == -1)
        eff = 0;
    else if(x + 1 == vals.size())
        eff = vals.size() - 2;
    int res = query(vals[x], vals[x + 1], insval);
    if(x == eff)
    {
        if(res == vals[x])
            return -1;
        if(res == vals[x + 1])
            return 1;
        return 0;
    }
    else if(x == -1)
    {
        assert(res != -1);
        if(res == vals[0])
            return 0;
        return 1;
    }
    else
    {
        assert(eff + 2 == vals.size());
        assert(res != 1);
        if(res == vals.back())
            return 0;
        return -1;
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin >> t >> n >> q;
    for(int cases = 0; cases < t; cases++)
    {
        vector<int> vals = {1, 2, 3};
        int fi = query(1, 2, 3);
        vals.erase(find(vals.begin(), vals.end(), fi));
        vals.insert(vals.begin() + 1, fi);
        for(int i = 4; i <= n; i++)
        {
            int lo = -1, hi = vals.size() - 1, mid;
            while (lo < hi)
            {
                mid = (lo + hi) / 2;
                int res = check(mid, i, vals);
                if(res == 0)
                    lo = hi = mid;
                else if(res == 1)
                    lo = mid + 1;
                else 
                    hi = mid - 1;
            }
            assert(lo == hi);
            if(lo == -1)
                vals.insert(vals.begin(), i);
            else if(lo + 1 == vals.size())
                vals.insert(vals.end(), i);
            else
                vals.insert(vals.begin() + lo + 1, i);
        }
        assert(vals.size() == n);
        for(int i = 0; i < vals.size(); i++)
            cout << vals[i] << " \n"[i + 1 == vals.size()];
        int resp;
        cin >> resp;
        assert(resp == 1);
    }
    return 0;
}

→ Reply

TimonKnigge

4 years ago, # ^ |

+17

Quicksort with two pivots also worked.

→ Reply

Kognition

4 years ago, # ^ |

← Rev. 2 →

+10

The search for each new element can be reduced to $$$\log_3(n)$$$ by splitting the array into thirds when you are querying for the place of a new element.

As a more general tip, remember you are not doing a comparison (i.e. binary operation), your query operation has 3 different possible outcomes, so you should be able to break up the space of possibilities into 3 different partitions on each query.

→ Reply

Mike_Mirzayanov_Is_Pussy

4 years ago, # ^ |

gaurav,Geothermal,Kognition log2(n) didn't worked :( . But i understood the log3(n) part .thanks i understood that i should have queried at points l + (r-l)/2 , r — (r-l)/2 for getting 1/3 of length in each iteration .

→ Reply

4 years ago, # ^ |

I applied binary search only with some some modifications to decrease queries per iteration and I was able to pass the last sub-task. I tested it locally and it was taking $$$155-175$$$ queries on an average.

Code

'''Author- Akshit Monga'''

import sys


def query(i, j, k):
    print(i, j, k, flush=True)
    return int(input())


t, n, q = map(int, input().split())
for _ in range(t):
    med = query(1, 2, 3)
    if med == 1:
        arr = [2, 1, 3]
    elif med == 2:
        arr = [1, 2, 3]
    else:
        arr = [1, 3, 2]

    for i in range(3, n):
        # finding the appropriate position for ith ele in already existing list and updating list
        start = 0
        end = len(arr) - 1
        while 1:
            # print(start, end)
            if start == end:
                arr.insert(start, i + 1)
                break
            if start == end - 1:
                med = query(arr[start], arr[end], i + 1)
                if med == arr[start]:
                    index = start
                elif med == arr[end]:
                    index = end + 1
                else:
                    index = end
                arr.insert(index, i + 1)
                break
            mid = (start + end) // 2
            # print(mid)
            # let's ask arr[start], arr[mid], i+1
            med = query(arr[start], arr[mid], i + 1)
            if med == arr[start]:
                end = start
            elif med == arr[mid]:
                if mid + 1 != end:
                    start = mid + 1
                else:
                    start = mid
            else:
                if mid - 1 != start:
                    end = mid - 1
                    if start + 1 != end:
                        start += 1
                else:
                    start = mid
                    end = mid
    print(*arr)
    x = int(input())
    if x == -1:
        sys.exit()

Code for testing

'''Author- Akshit Monga'''

import sys
import random

def query(i, j, k):
    global q,ans
    q+=1
    vals=[ans[i-1],ans[j-1],ans[k-1]]
    vals=sorted(vals)
    if vals[1]==ans[i-1]:
        return i
    if vals[1]==ans[k-1]:
        return k
    if vals[1]==ans[j-1]:
        return j
    # print(i, j, k, flush=True)
    # return int(input())

t=int(input())
n=int(input())
q=0
# t, n, q = map(int, input().split())
for _ in range(t):
    q=0
    ans=[i for i in range(1,n+1)]
    random.shuffle(ans)
    med = query(1, 2, 3)
    if med == 1:
        arr = [2, 1, 3]
    elif med == 2:
        arr = [1, 2, 3]
    else:
        arr = [1, 3, 2]

    for i in range(3, n):
        # finding the appropriate position for ith ele in already existing list and updating list
        start = 0
        end = len(arr) - 1
        while 1:
            # print(start, end)
            if start==end:
                arr.insert(start, i + 1)
                break
            if start == end - 1:
                med = query(arr[start], arr[end], i + 1)
                if med == arr[start]:
                    index = start
                elif med == arr[end]:
                    index = end + 1
                else:
                    index = end
                arr.insert(index, i + 1)
                break
            mid = (start + end) // 2
            # print(mid)
            # let's ask arr[start], arr[mid], i+1
            med = query(arr[start], arr[mid], i + 1)
            if med == arr[start]:
                end = start
            elif med == arr[mid]:
                if mid+1!=end:
                    start = mid+1
                else:
                    start=mid
            else:
                if mid-1!=start:
                    end = mid-1
                    if start+1!=end:
                        start+=1
                else:
                    start=mid
                    end = mid
        # print(arr)
    # print(arr)
    # print(ans)
    c=0
    for i in arr:
        c+=1
        assert ans[i-1]==c or ans[i-1]==n+1-c
    print(q)

→ Reply

Mike_Mirzayanov_Is_Pussy

4 years ago, # ^ |

Thanks for your code , could you please write in words how you modified the binary search ? It's little hard to read the code directly without any written info .

→ Reply

4 years ago, # ^ |

← Rev. 4 →

Here it goes-

You can easily find the relative position of $$$3$$$ elements with just $$$1$$$ query. Now, I try to place elements from index $$$4$$$ to $$$N$$$ in already existing list one by one.

Let's say during the current iteration, size of already existing list is $$$l.$$$ I define $$$start=0$$$ and $$$end=l-1.$$$ For insertion of new element, it can have potentially have $$$l+1$$$ positions ($$$l-1$$$ in between the elements and $$$1$$$ before start and $$$1$$$ after end). Define $$$mid=(start+end)/2.$$$

To find the appropriate position-

I ask $$$(start,mid,i)$$$ where $$$i$$$ is the index of current element we want to place. You can also ask $$$(end,mid,i)$$$ depending on your implementation.

Now, we want to analyze how our search space will be reduced.

If median is $$$start,$$$ we can stop our search and directly place $$$i$$$ before $$$start.$$$
If median is $$$mid$$$, we can be sure that position of $$$i$$$ is definitely not before $$$mid.$$$ We can initialize $$$start=mid+1.$$$ This way we reduce the search space by half.
If median is $$$i,$$$ we can be sure that position of $$$i$$$ is definitely not after $$$mid.$$$ We can initialize $$$end=mid-1.$$$ This way we reduce the search space by half. Also, we can increase $$$start$$$ by $$$1$$$ because we are also sure that the position is definitely after $$$start$$$, otherwise the result of the query would have be $$$start.$$$

Also, I handle the cases when search space reduces to $$$3$$$ or less separately because I don't wanna mess up and end in some infinite loop.

The total queries it takes is $$$1$$$ + $$$\Sigma^{N-1}_{i=3} (\log_2i-c)$$$ where $$$c \sim 1$$$. That $$$c$$$ is due to above mentioned few optimizations and the fact that input is random.

Also, I tested it locally and it takes $$$150-175$$$ queries. My initial solution was taking around $$$\sim 250$$$ queries because I was extra cautious and assigned $$$start=mid$$$ and $$$end=mid$$$ in case $$$2$$$ and $$$3$$$ respectively and did $$$1$$$ more query in case $$$1$$$ to confirm.

→ Reply

4 years ago, # ^ |

← Rev. 2 →

Also, you can compare the both codes for better understanding-

~250 queries

'''Author- Akshit Monga'''

import sys


def query(i, j, k):
    print(i, j, k, flush=True)
    return int(input())


t, n, q = map(int, input().split())
for _ in range(t):
    med = query(1, 2, 3)
    if med == 1:
        arr = [2, 1, 3]
    elif med == 2:
        arr = [1, 2, 3]
    else:
        arr = [1, 3, 2]

    for i in range(3, n):
        # finding the appropriate position for ith ele in already existing list and updating list
        start = 0
        end = len(arr) - 1
        while 1:
            if start == end - 1:
                med = query(arr[start], arr[end], i + 1)
                if med == arr[start]:
                    index = start
                elif med == arr[end]:
                    index = end + 1
                else:
                    index = end
                arr.insert(index, i + 1)
                break
            mid = (start + end) // 2
            # let's ask arr[start], arr[mid], i+1
            med = query(arr[start], arr[mid], i + 1)
            if med == arr[start]:
                end = start + 1
            elif med == arr[mid]:
                start = mid
            else:
                end = mid
    print(*arr)
    x = int(input())
    if x == -1:
        sys.exit()

~170 queries

'''Author- Akshit Monga'''

import sys


def query(i, j, k):
    print(i, j, k, flush=True)
    return int(input())


t, n, q = map(int, input().split())
for _ in range(t):
    med = query(1, 2, 3)
    if med == 1:
        arr = [2, 1, 3]
    elif med == 2:
        arr = [1, 2, 3]
    else:
        arr = [1, 3, 2]

    for i in range(3, n):
        # finding the appropriate position for ith ele in already existing list and updating list
        start = 0
        end = len(arr) - 1
        while 1:
            # print(start, end)
            if start == end:
                arr.insert(start, i + 1)
                break
            if start == end - 1:
                med = query(arr[start], arr[end], i + 1)
                if med == arr[start]:
                    index = start
                elif med == arr[end]:
                    index = end + 1
                else:
                    index = end
                arr.insert(index, i + 1)
                break
            mid = (start + end) // 2
            # print(mid)
            # let's ask arr[start], arr[mid], i+1
            med = query(arr[start], arr[mid], i + 1)
            if med == arr[start]:
                end = start
            elif med == arr[mid]:
                if mid + 1 != end:
                    start = mid + 1
                else:
                    start = mid
            else:
                if mid - 1 != start:
                    end = mid - 1
                    if start + 1 != end:
                        start += 1
                else:
                    start = mid
                    end = mid
    print(*arr)
    x = int(input())
    if x == -1:
        sys.exit()

→ Reply

rath772k

4 years ago, # |

-8

I have a nice recursive solution for $$$Median$$$ $$$Sort$$$. Inititially, call the function $$$sort(a[1,2,...,n])$$$. For all $$$3 \leq j \leq n$$$, query $$$a[1]$$$ $$$a[2]$$$ $$$a[j]$$$. From the output of the query, one can determine the position of $$$a[j]$$$ in the array, i.e. $$$left$$$, $$$middle$$$ or $$$right$$$ w.r.t $$$a[1]$$$ and $$$a[2]$$$. After this one can recursively solve $$$left$$$, $$$middle$$$ and $$$right$$$ parts. But the problem now is the three parts can be independently in correct or reversed order. We can determine the order by querying one of the elements of each part along with $$$a[1]$$$ and $$$a[2]$$$. I don't have a strict upper bound on the number of queries this program asks, but it asks about 165 queries per test case (tested locally on random tests).

My submission

#include <bits/stdc++.h>
using namespace std;

#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define S(x) (int)(x).size()
#define L(x) (int)(x).length()
#define ld long double
#define mem(x,y) memset(x,y,sizeof x)

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int , null_type , less<int> , rb_tree_tag , tree_order_statistics_node_update> ordered_set;

const int mod = 1e9+7;
const ll infl = 0x3f3f3f3f3f3f3f3fLL;
const int infi = 0x3f3f3f3f;

int query(int i, int j, int k)
{
	cout<<i<<' '<<j<<' '<<k<<'\n';
	cout.flush();
	int ret;
	cin>>ret;
	return ret;
}

vector<int> go(vector<int> v)
{
	int n=S(v);
	if(n<=2) return v;
	vector<int> l,r,m;
	for(int i=2;i<n;i++)
	{
		int q = query(v[i],v[0],v[1]);
		if(q==v[i]) m.pb(v[i]);
		else if(q==v[0]) l.pb(v[i]);
		else r.pb(v[i]);
	}
	l=go(l);
	m=go(m);
	r=go(r);
	if(S(l) >= 2 && query(l[0],l[1],v[0])==l[0]) reverse(all(l));
	if(S(m) >= 2 && query(m[0],m[1],v[1])==m[0]) reverse(all(m));
	if(S(r) >= 2 && query(r[0],r[1],v[1])==r[1]) reverse(all(r));
	vector<int> ret;
	ret.insert(ret.end(),all(l));
	ret.pb(v[0]);
	ret.insert(ret.end(),all(m));
	ret.pb(v[1]);
	ret.insert(ret.end(),all(r));
	return ret;
}
int n,q;
void solve()
{
	//cin>>n>>q;
	vector<int> v(n);
	iota(all(v),1);
	v = go(v);
	for(auto u:v) cout<<u<<' ';
	cout<<'\n';
	cout.flush();
	int res;
	cin>>res;
	if(res==-1) exit(0);
}

int main()
{
	IOS
	int t=1;
	cin>>t;
	cin>>n>>q;
	for(int i=1;i<=t;i++)
	{
		solve();
	}
}

→ Reply

4 years ago, # ^ |

I've implemented the same solution, except that instead of using the first 2 elements in the array, I choose them randomly. This because it's easy to find test cases where your solution fails to use less than 175 queries, even on average (i.e. array already sorted). I think that if the problem was in a CF round somebody was going to hack you. Probably CJ test cases were weak enough to pass.

→ Reply

sgtlaugh

4 years ago, # ^ |

Nope. It doesn't matter if you take random elements. Because of this line in the problem statement: The order for each case is generated uniformly at random from all possible orders, and independently of any other information.

→ Reply

4 years ago, # ^ |

I've missed that line in the statement, I'm sorry :(

But still, I think it's important to keep in mind that kind of solution are easily hackable in CF

→ Reply

4 years ago, # |

+21

Here's a link to my screencast: https://youtu.be/RThkP1UORhk. It'll be available in HD whenever the HD version finishes processing.

→ Reply

4 years ago, # |

← Rev. 2 →

+19

Seen lots of good solutions for E.

Here is how I went about the problem — note that the coin toss compresses the sigma function. If we compare a 'clever' person (let's say skill in the top 10%, i.e. > 2.4) with a cheat of average intelligence (0), we find the biggest gap between their probability of success lies in the middle questions.

So what worked for me was to take the top 5% of questions (0-499 in lowest solves list), find the 10% (i.e. 10) of people with the most solves on those questions, and then subtract their solves from the 'middle' 5% of questions (4750-5249 in the same list). Whoever has the biggest difference is the cheat.

→ Reply

huikang

4 years ago, # |

← Rev. 3 →

+13

Question E — For every contestant, I calculated the Pearson correlation coefficient with

whether the contestant got the question correct for each question
how many contestants got the question correct for each question

I guessed that the cheater is the one with smallest Pearson correlation coefficient. After the qualifiers, I found out that my answer was accepted on the borderline (with 7 mistakes out of 7 allowed mistakes).

Spoiler

#!/usr/bin/env python3

import sys
import numpy as np
from scipy.stats import pearsonr
input = sys.stdin.readline  # to read input quickly


def solve(ref):
    ref = [[int(x) for x in row.strip()] for row in ref]
    ref = np.array(ref)

    correct_for_each_question = np.sum(ref, axis=0)

    p_vals = []
    for result in ref:
        p_val = pearsonr(correct_for_each_question, result)[0]
        p_vals.append(p_val)
    cheater = np.argmin(p_vals)

    return cheater+1


def read_strings(rows):
    return [input().strip() for _ in range(rows)]


num_cases = int(input())
input()
for case_num in range(num_cases):
    k = 100
    arr = read_strings(k)  # and return as a list of str
    res = solve(arr)  # include input here
    print("Case #{}: {}".format(case_num+1, res))

→ Reply

askd

4 years ago, # ^ |

← Rev. 2 →

I did the exact same thing, had no idea it was that close to failing :o

→ Reply

https://codingcompetitions.withgoogle.com/terms

4 years ago, # |

+33

I share also my solution for problem E, since nobody has discussed this approach yet.

I've got 100% accuracy in problem E by implementing a gradient ascent for finding the maximum likelihood estimation of $$$S_i$$$ and $$$Q_j$$$, ignoring the presence of a cheater. I've then chosen as a cheater the student that increases most the likelihood if the cheater-distribution is used.

Here is the code

→ Reply

hellman_

4 years ago, # |

← Rev. 4 →

+25

For E, sort the questions by number of solutions and for each player compute average squared distance (in the sorted question list) for all his answers from his median position.

Seems to work pretty well, 5 errors on 25,000 runs. (99.98% accuracy)

python code

def solve(arr):
    qs = [(sum(vs), i) for i, vs in enumerate(zip(*arr))]
    qs.sort(reverse=True)
    qs = [q[1] for q in qs]

    res = []
    for pi in range(100):
        numans = sum(arr[pi])
        acc = 0
        med = 0
        for i, qi in enumerate(qs):
            acc += arr[pi][qi]
            if acc >= numans / 2.0:
                med = i
                break

        lst = []
        for i, qi in enumerate(qs):
            if arr[pi][qi]:
                lst.append(abs(i - med)**2)
        dist = sum(lst) / len(lst)
        res.append((dist, pi))
    return max(res)[1]+1

t = int(input())
p = int(input())
n0 = 0
for ti in range(t):
    arr = []
    for i in range(100):
        line = tuple(map(int, input()))
        assert len(line) == 10000, len(line)
        arr.append(line)
    ans = solve(arr)
    n0 += ans == 1
    print("Case #%d: %s" % (ti+1, ans))

→ Reply

_Ramba_

4 years ago, # ^ |

Can you share the solution?

→ Reply

kfqg

4 years ago, # |

← Rev. 12 →

+10

Here is a simple solution for E which passed both test cases:

Sort the problems by how many people solved them, and sort the players by how many questions they solved.

Let's say the "Difficult Problems" are the hardest 500 problems.

If there is anyone ranked in the bottom 80 who solved more than 200 Difficult Problems, I say that they are the cheater.
If not, then I say that whoever solved the most Difficult Problems is the cheater.

This solution tries to catch lower-skill cheaters with (1), and catch higher-skill cheaters with (2).

→ Reply

pallav12

4 years ago, # |

In problem D, Median Sort, I just got stuck to one idea ie using a BST, ultimately I couldn't get it right. Can anyone share insights if it's possible to solve it using BST?

→ Reply

Fawkes

4 years ago, # |

-17

O(N) solution for C

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define f first
#define s second
void solve() {
    ll n,m,k,i,j,l;
    cin>>n>>m;
    ll ub=(n*(n+1))/2 -1;
    ll lb=n-1;
    if(m<lb||m>ub) {cout<<"IMPOSSIBLE\n"; return;}
    vector<ll> positions,ans(n+1);
    for(i=1;i<=n/2;i++) {
        positions.push_back(n+1-i);
        positions.push_back(i);
    }
    j=1;
    k=n;
    for(i=1;i<=n-1;i++) {
        ll optobedone=n-1-i;
        // what is the position of j in array.
        // mystery
        // let's solve it.
        ll pos=positions[i-1];
        //cout<<optobedone<<" "<<k<<" "<<m<<" "<<i<<endl;
        if(k+optobedone<=m){
            m-=k;
            ans[pos]=i;
        // refilling the remainings are the target here. but a bastard task by Google.
        // if(m==optobedone) {
        //   if(i%2==1) {
              
        //   }
        // }
        }
        else {
            ll o=m-optobedone;
            
            // find optimal position of it.
            if(pos>n/2) { pos-=k-o; }
            else { pos+=k-o; }
            ans[pos]=i;
            vector<ll> v1,v2;
            j++;
            
            if(i%2==0) {
                j=n;
                for(ll l=1;l<=pos;l++) {
                    if(!ans[l]) v1.push_back(j--);
                }
                for(ll l=pos;l<=n;l++) {
                    if(!ans[l]) v2.push_back(j--);
                }
                reverse(v2.begin(),v2.end());
                ll it=0;
                for(ll l=1;l<=pos;l++) {
                    if(!ans[l]) {ans[l]=v1[it++];}
                }
                it=0;
                for(ll l=pos;l<=n;l++) {
                    if(!ans[l]) { ans[l]=v2[it++];}
                }
                break;
            }
            else {
                for(ll l=1;l<=pos;l++) {
                    if(!ans[l]) v1.push_back(j++);
                }
                for(ll l=pos;l<=n;l++) {
                    if(!ans[l]) v2.push_back(j++);
                }
                reverse(v1.begin(),v1.end());
                ll it=0;
                for(ll l=1;l<=pos;l++) {
                    if(!ans[l]) {ans[l]=v1[it++];}
                }
                it=0;
                for(ll l=pos;l<=n;l++) {
                    if(!ans[l]) { ans[l]=v2[it++];}
                }
            }
            break;
        }
        k--;
        j++;
    }
    for(i=1;i<=n;i++) {
        if(ans[i]==0) {
            ans[i]=n;
            break;
        }
    }
    for(i=1;i<=n;i++) {
        cout<<ans[i]<<" ";
    }
    cout<<endl;
}
int main() {
    ll t;
    cin>>t;
    ll i=1;
    while(t--) {
        cout<<"Case #"<<i<<": ";
        solve();
        i++;
    }
    
    return 0;

}

→ Reply

towrist

4 years ago, # |

+53

the discussions on problem E makes it sound like it is a hashcode problem: "yeah I don't know how it works, but here is my heuristic"

→ Reply

01_01_1998

4 years ago, # |

In country standing of codejam, Iran is missing. There are strong coders from Iran in codeforces community, then why the country name is gone?

→ Reply

elsantodel90

4 years ago, # ^ |

It is likely because Iran is not allowed into the contest:

"Each Contest is void in Crimea, Iran, North Korea, Quebec, and where prohibited by law."

→ Reply

elsantodel90

4 years ago, # |

+43

Here's a link to my [SPANISH] screencast + detailed explanation of problems

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

Fun fact: Problem D was actually almost identical to problem "Median" from IOI 2000, China!

I really liked all the Qualification Round problems this year. Congratulations to all the problem setters!

→ Reply

7pablof

4 years ago, # |

← Rev. 2 →

+28

Another simple approach for E which also achieves a 100% accuracy on 25000 local tests:

Estimate player $$$i$$$ skill level ($$$S_i$$$) as the sigmoid inverse of its ratio of correct answers.
Estimate question $$$j$$$ difficulty ($$$Q_j$$$) as the sigmoid inverse of its ratio of failed answers.
Loop through the questions answered by a player: If the probability of a player answering the question correctly is high (e.g., > 0.75) but the player has failed the question, then add $$$S_i - Q_j$$$ to the suspiciousness of player $$$i$$$.
The cheater is the player with the highest suspiciousness.

The code is really simple:

C++ source code

#include <bits/stdc++.h>

using namespace std;

double f_sigmoid(double x) {
    return (1.0 / (1.0 + exp(-x)));
}

double f_sigmoid_inverse(double x) {
    return log(x / (1.0 - x));
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    const int N = 100;
    const int M = 10000;

    int t, p;
    cin >> t >> p;
    for (int tcase = 1; tcase <= t; ++tcase) {
        vector<string> correct(N);
        vector<long long> pcorrect(N);
        vector<long long> qcorrect(M);
        vector<double> pskill(N);
        vector<double> qdiff(M);

        for (int i = 0; i < N; ++i) {
            cin >> correct[i];
        }

        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < M; ++j) {
                if (correct[i][j] == '1') {
                    pcorrect[i] += 1;
                    qcorrect[j] += 1;
                }
            }
        }

        for (int i = 0; i < N; ++i) {
            pskill[i] = f_sigmoid_inverse(pcorrect[i] / (double)M);
        }

        for (int j = 0; j < M; ++j) {
            qdiff[j] = f_sigmoid_inverse(1.0 - qcorrect[j] / (double)N);
        }

        vector<double> suspicious(N);
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < M; ++j) {
                double diff = pskill[i] - qdiff[j];
                double p_correct = f_sigmoid(diff);
                if (p_correct > 0.75 && correct[i][j] != '1') {
                    suspicious[i] += diff;
                }
            }
        }

        int ans = max_element(suspicious.begin(), suspicious.end()) - suspicious.begin() + 1;

        cout << "Case #" << tcase << ": " << ans << "\n";
    }
}

Fun fact: During the round I wrongly estimated players' skill level and questions' difficulty, using a linear function between -3 and 3 instead of the sigmoid inverse. However, this was still enough to pass test set 2 with just 3 wrong cases.

→ Reply

Hakiobo

4 years ago, # ^ |

← Rev. 2 →

+30

I see that your approach works very well, but I don't believe the inverse sigmoid accurately estimates the skill/difficulty level of contestants/problems. The inverse sigmoid will calculate the estimated skill of a contestant assuming all questions have difficulty 0, rather than from the uniform distribution [-3,3].

Instead, i think what should be done, is to integrate across the possibility problem difficulties for each contestant

$$$p = \frac{1}{6}\int_{-3}^{3}\frac{1}{1 + e^{q-s}}\,dq$$$

Solving this leads to this formula for the skill level of the contestant given the percent of correct answers $$$p$$$

$$$s = 3 + ln(\frac{e^{6p} - 1} {e^6 - e^{6p}})$$$

→ Reply

ustaritz

4 years ago, # ^ |

+10

Absolutely. I did the same and obtained 999 correct tests on 1000 random tests with a probability cheating of 50%.
In order to stress the method, I used a 10% probability of cheating (as suggested by ecnerwala) and obtained 801 correct tests on 1000 random tests.
I don't see any theoretical justification for using the inverse sigmoid method. This method actually underestimate the real skill by 30% to 40% on my tests.

→ Reply

7pablof

4 years ago, # ^ |

Thanks, you are absolutely right!

I changed the estimation to use you formula and now skill and difficulty estimations are considerably more accurate. However, using these improved estimations, the approach performs slightly worse overall (98% accuracy).

I do not understand why the previous version worked so well...

Just as a note: In the official Google analysis, they also state that skill/difficulty can be estimated by using the sigmoid inverse.

→ Reply

Vosatorp

4 years ago, # |

When does google code jam usually start? I want to put a reminder so that I don't miss registering for it next year.

→ Reply

aryanc403

4 years ago, # |

Apparently they are running a poll on twitter to decide design of this year's codejam. People here would be interested in voting.
https://twitter.com/googlecodejam/status/1379150242579410945

P.S. — I didnt liked any available design. :(

→ Reply

aeiou1

4 years ago, # |

Why codejam lost so much hype? I see just one small discussion on this site, ~10k participants (2 times lesser than codeforces div2 round), just 54 points was enough to advance.

BTW why so weird point distribution? I thought that C2 was harder than A2 or B3...

→ Reply

Coder

4 years ago, # ^ |

Maybe there was some discussion during the contest instead again ;)

I am curious what was the worst case in B3, i.e. the maximal difference between sum and the answer.

→ Reply

TeXit

4 years ago, # ^ |

+34

Or maybe round 1A got missed by many due to late night/early morning time

→ Reply

https://paste2.org/BjBcKD2L

4 years ago, # ^ |

Here are the outputs, including differences between sum and answer, and the maximum difference at the bottom.

The answer is 3025 (see bottom of file), so they engineered a test case to be at the limit, which makes sense.

→ Reply

Um_nik

4 years ago, # |

+43

Screencast of 1A with low-key commentary

→ Reply

kakashi.

4 years ago, # |

← Rev. 3 →

-10

Round 1A: Reading the editorial for the "Hacked Exam" problem, I think that maybe they overcomplicated the solutions for test sets 1 and 2 (or I'm completely wrong?). I just figured that, with T/F questions, adding a second student with a lower score doesn't change the expected value. So, the answer is to just replicate the best student (or the worst one inverted, for that matter). Does it make sense or I just got lucky to have passed with this idea? Thanks for any help! And please follow the code below.

string inv(string a) {
    string r;
    trav(x, a) {
        if(x == 'T') r += 'F';
        else r += 'T';
    }
    return r;
}

void run_test() {
    int n, q; read(n, q);
    int mx = 0;
    string ans;
    rep(k, n) {
        string a; read(a);
        int s; read(s);
        if(s <= q / 2) a = inv(a), s = q-s;
        if(s > mx) {
            mx = s;
            ans = a;
        }
    }
    cout << ans << " " << mx << "/1" << endl;
}

→ Reply

atharv

4 years ago, # ^ |

This solution was mentioned in the editorial as the "insight-based solution".

→ Reply

manpreet.singh

4 years ago, # ^ |

Where is the editorial?

→ Reply

atharv

4 years ago, # ^ |

There is an analysis tab under each problem.

→ Reply

Errichto

4 years ago, # |

Round 1A upsolving screencast with a lot of commentary https://youtu.be/RK-NFGYF-wY

→ Reply

vkgainz

4 years ago, # |

← Rev. 2 →

+10

Not sure where to ask this (can't find a R1B thread), so I'll just put it here.

Are you allowed to unofficially participate in Round 1B if you qualified off Round 1A already? I.e. will I be able to look at the problems and make submissions during the contest, or is my account barred from participation during contest?

→ Reply

tamajitbuba

4 years ago, # ^ |

I think you can participate.

→ Reply

mip182

4 years ago, # ^ |

+21

You can't make submissions.

→ Reply

dhruv7888

4 years ago, # |

I don't know where to ask , that is why I am asking here Does Google run Plag checker in the middle of the contest ? I am asking this because my rank is decreasing , even though I am not submitting any thing .

→ Reply

conan_0

4 years ago, # ^ |

← Rev. 2 →

+13

No, people above you are submitting their solutions again. The tie is broken by the last successful submission(source).

→ Reply

dhruv7888

4 years ago, # ^ |

Okkk , I didn't knew it , Now it looks like I did good by not taking chances for trying to solve hidden test cases .

→ Reply

DammitDwight

4 years ago, # ^ |

+21

I afraid that's not correct.

Submitting solutions again, increases the penalty only when the new solution got more points than the previous one.

→ Reply

dhruv7888

4 years ago, # ^ |

I too think that the rules are as u mentioned.

→ Reply

Venti_chai

4 years ago, # |

Another day, another lose!

→ Reply