kostka's blog

By kostka, 3 years ago, In English

Join our online coding competition and tackle fun problems designed by Google engineers! ➡️g.co/kickstart

Round C starts in less than 24 hours (on May 23rd at 11:00 UTC).

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

| Write comment?
»
3 years ago, # |
  Vote: I like it +38 Vote: I do not like it

Yay AC.

I realised that the OJ server is laggy, is that your experience as well?

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

    I had to wait for at least 2 min to see if my C passed or not (9 times). It was really annoying. I wonder what the reason was for this slowness.

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

      Same, it was really frustating, I reloaded the page actually and that basically just removed the submission, when I did it again, again it was coming again I reloaded. Then at last I finally waited after submitting and I saw now that all 3 submission came simultaneously, and all were wrong, now what is this.

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

        same happened with me i faced 3 extra penalties due to this:(

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

I don't know if it is just me or not... but almost every time I have to wait several minutes to submit my code :(

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

Problem B mostly same as https://atcoder.jp/contests/abc190/tasks/abc190_d

just divide the final answer by 2

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

Congratulations Errichto on winning the round
Eagerly waiting for your screencast (to know how I messed up today)

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

How to solve A test case 2?

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

Since analysis doesn't seem to have been posted yet, how to solve final subtask of P3?

I managed to get an expected value of 16000 with the following but no clue how to improve:

For E = W, random gets you 20 expected wins and 20 expected draws, I believe this is optimal and can't be improved.

For all other cases, find the best constants A, B, C, D where A + B + C + D = 60 such that playing Rock A times, then Scissors B times, Paper C times and Rock again D times produces the best possible answer for such a method.

Turns out such constants can get you an expected win rate of $$$28.13 \times E$$$ for $$$W = 0$$$, $$$28.71 \times E$$$ for $$$W = \frac{E}{10}$$$ and $$$31.51 \times E$$$ for $$$W = \frac{E}{2}$$$, so a total expected score of $$$500 \times \frac{28.13 + 28.71 + 31.51 + 40}{4}$$$ or $$$16000$$$.

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

    The analysis is already published.

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

    I after many adhoc thoughts, wrote a dp and it came simple enough dp involving states n, number of rock, scissors and paper. I used double also in hope to manage precision . At last constructed the solution, using the character to be chosen for maximum.

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

I did not find the round interesting also C was really weird. Managed to solve the first 2 and get a rank of 1400'ish. Here are the ideas,

A
B
Code - A
Code - B
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    B can also be solved by noticing the number of days cannot exceed $$$\sqrt{2 \times G}$$$ as then even starting from $$$1$$$, we get $$$\frac{n * (n + 1)}{2} \gt G$$$.

    Also notice that there is exactly 1 way to get a given score in a given number of days, as $$$sum_{i = j}^{i = j + k} {i}$$$ increases as $$$i$$$ increases. Since this property is monotonic, we can binary search on it, solving the problem in a total of $$$O(\sqrt{G} logG)$$$

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

      B is equivalent to just counting the number of odd divisors of $$$G$$$

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

Expected value of probability of asking a problem from "Probability Theory" in Google Kickstart or Codejam =1.

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

Can someone help me to provide a counter-case for A, please?

My Code for A: Smaller Strings
  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +9 Vote: I do not like it
    Check this testcase :
    

    1 12 9 edciahibffdh

    The output shud be 257993

    but you are getting 257994
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Thanks a lot, buddy, just a tweak and it passed both tests. Thanks, again! Although, I wasted my 2 hours in searching for the mistake :'(

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

      I used a condition s[i]<s[n-i-1] till i=(n+1)/2 to check if the ans would be increased by one.Turns out I was wrong. I implemented it in another way and got AC but anyone can help me with 1st approach.

      My code:-
»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Could somebody share how they came up with a good enough hash function for D? I came up with functions $$$(a \cdot RAND + b) \% mod1$$$ and $$$(a + RAND1) \cdot (b + RAND2) \% mod2$$$ pretty fast, but they didn't pass the second case and I was having trouble creating a better function.

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

    $$$(70 * (a + 45) + 40 * (b + 9)) * (130 * (a + 23) + 90 * (b + 7))$$$

    Just some random sum and multiplication. it worked for me.

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

      Thanks, indeed I tried (after contest) hash function $$$(a \cdot a \cdot RAND1 + b \cdot b \cdot RAND2 + a \cdot b \cdot RAND3 + RAND4) \% mod$$$ and it seems to work. I'm not sure why my functions were too weak though.

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

        First can be easily failed with addition and second with multiplication.

        For example, $$$(a\cdot RAND + b) \% mod1 + (c \cdot RAND + d) \% mod1 = (a\cdot RAND + d) \% mod1 + (c \cdot RAND + b) \% mod1$$$ (if b and d don't overflow $$$mod1$$$, but assume they are small enough)

        For second one similarly $$$f(a, b) \cdot f(c, d) = f(a, d) \cdot f(c, b)$$$

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

          Thanks for the explanation!

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

          Is Q4 meant to be solved using hash function ? I was thinking doing all non sense using bigint and all with max 200 digits

          Asking this because this is the first time I came across a real use of hasing in CP.I always felt hashing is luck dependent so why would anyone use it in a contest

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

            You can use a custom hash function for the # operations, but it needs to be strong enough (this solution is mentioned in the official editorial). About it being luck based: the probability of it actually failing is usually very low, and you can further decrease it by using a tuple of hashes instead of only one. And you don't need big int because you can just calculate everything modulo some prime.

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

for problem B . After analysing on first 100 values of 'g' . I found out that answer is total number of odd unique factors of 'g' . And finding factors can be done in O(sqrt(N)) for given value of N. I need proof for this :).

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

    Let’s suppose if we start at a units, and we get g units in d+1days. Hence, a+(a+1)+(a+2)+...+(a+d)=g. Hence, (d+1)*(2a+d)==2g. Now, the rest of the proof is pretty straightforward !

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

Me after reading C:
"I will never play rock paper scissors ever again!"

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

I can't understand what problem C meant they gave so confusing explanation too
If anyone has good explanation please link it here

I solved A subtask 1
B complete question
and D subtask 1 but I used randomisation and python large numbers

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

The transitions in the editorial for C are wrong.

Should be: \begin{split} v[r][p][s] & = & \max & (v[r — 1][p][s] + \frac{p}{n — 1} \times \mathbf{W} + \frac{s}{n — 1} \times \mathbf{E}, \ & & & v[r][p — 1][s] + \frac{s}{n — 1} \times \mathbf{W} + \frac{r}{n — 1} \times \mathbf{E}, \ & & & v[r][p][s — 1] + \frac{r}{n — 1} \times \mathbf{W} + \frac{p}{n — 1} \times \mathbf{E}) \ \end{split}

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

    I made the same mistake. It cost me 1 penalty, 30 minutes and 50 strands of hair

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

    Could you explain it?

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

      If we choose rock, we win if the opponent chooses scissors and draw if they also choose rock. The probability of them choosing scissors is $$$p / (n - 1)$$$ and the probability of them choosing rock is $$$s / (n - 1)$$$ (according to the problem statement). The cases in which we choose paper or scissors can be handled similarly.

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

        Oh right, it's my bad mistake. I thought the opponent chooses S with Pr[S] = s/(n-1).

        Thanks!

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

        Good to know that I was not the only one. Sadly I did not figure it out during the contest.

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

    Can precision loss be an issue? I did the same but it failed and I still don't know what's going wrong in my solution https://ideone.com/iedIGo

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

Between oversleeping and some mix of panic/annoyance at the lagging judge, I ended up chipping away at smol solves and settling in on D which (EVENTUALLY) worked out... thought I was being smurt by putting in an intentional TLE (infinite loop) to diagnose an RE bug, but somehow managed to both fix the latter (break rather than keep trying to parse an input that got shortened) by adding something unnecessary (account for (0)->0) while also adding an actual infinite loop bug (attempting to get a unique randint from too narrow of a range)... tl;dr crappy rainboy impression was actually crappy...?

272nd is the best I've done in these sorts of things, not sure how to feel about it... maybe slightly relieved after failrun at codejam round 2...?

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

    Your performance is the perfect depiction I have seen of the constant reminder everyone gives but hard to follow of "reading all the problems". Good job lol

»
3 years ago, # |
Rev. 9   Vote: I like it +28 Vote: I do not like it

Problem D is really easy to implement in Python. We don't even need to parse the expression manually, but rather we can let Python's built-in eval() take care of it.

The idea is to override the | operator (or any other unused operator) and then replace all existing occurrences of # with our overridden operator. The eval() function can then automatically parse and evaluate the resulting expression. We only need to provide the hash function.

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

    I didn't know the inbuilt implementation of eval I did something like this

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

    I upsolved it with a random oracle function

    @Infix
    @lru_cache(None)
    def op(x, y):
        return random.randint(0, 2**64-1)
    
»
3 years ago, # |
  Vote: I like it -14 Vote: I do not like it

In the "Rock Paper Scissor" problem, for the DP transactions there is no proof provided that the optimal answer for a particular state is resolvable from one of the exact previous state. I don't see why that would be the case always.

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

    If you have an optimal (highest-scoring) strategy, take any prefix, suppose it has r rocks, p, papers, and s scissors. Then that prefix is the highest scoring among all strategies with r rocks, p, papers, and s scissors, as otherwise, you could rearrange the prefix and get a strictly score overall.

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

The problems were quite good, but the system works worse and worse everyday. I faced numerous issues with loading problem statements just after beginning at Kick Start Round B and Code Jam Round 2. It took almost minute for me to load at least one problem statement. Today at Kick Start Round C I spent even more time trying to load problem statement. At some point a saw the "Something went wrong, please try again in 30 seconds" message. And I was not deceived, I had to wait for more than 30 seconds before the next attempt to load a problem statement. And yes, all these delays between submitting and displaying the queued attempt left me with tons of doubts:

  • Is the issue on my side?

  • How much time a have to wait before doing something?

  • Should I submit the solution again?

  • Should I refresh the page?

And so on... Please, consider updating the contest system. As of today, it is causing too much inconvenience to the participants.

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

What will be the rating of problems A, B,C, D in terms of CF question ratings

  • »
    »
    3 years ago, # ^ |
      Vote: I like it -18 Vote: I do not like it

    In my opinion, it should be like:

    Problem B — Div2 A — 1100 — Tags: Math

    Problem A — Div2 B — 1500 — Tags: Implementation

    Problem C — Div2 D — 2100 — Tags: DP, Games

    Problem D — Div2 E — 2300 — Tags: Hashing

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

      Completely disagree. I think both problems A and B are close to Div2 C. Problems C and D are far from what you typically see at Codeforces contests. Problem C can be solved with DP-approach that is typical for Div2 E / Div1 C. Problem D is about implementation and picking up a proper hashing function. This problem is not suitable for use in Codeforces contests.

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

        I thought D will be interesting and suitable in a Hackforces Educational Round.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it -8 Vote: I do not like it

        Problem D is about implementation and picking up a proper hashing function. This problem is not suitable for use in Codeforces contests.

        Hacking isn't an issue if your function is randomized by time, right?

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

          That wasn't about hacking to be honest. By Codeforces contests I rather meant contests with hidden verdict. It might be very unpleasant to got WA only because for $$$#$$$-operation you picked one of the few functions that fail system testing.

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

            Then I disagree. Choosing a proper hashing function is part of the solution. This could be used in a CF round and the main drawback is only that it's somewhat standard.

            (btw. getting WA on systests is always unpleasant)

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

Google kickstart

Smaller Strings

Getting TLE for Test Case2

(Following official editorial's method)

`Can someone suggest any improvements please?``` ~~~~~ Your code here...

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

int exp(int a,int b){
    int res=1;
    while(b){
        if(b&1)
            res=res*a;
        a=a*a;
        b>>=1;
    }
    return res;
}
int basek(string s,int k){
    int ans=0,n=s.length();
    for(int i=n-1;i>=0;i--){
        ans=ans+(s[i]-'a')*exp(k,n-i-1);
    }
    return ans;
}
string generate(string s,int l,int v,int k){
    while(v>0){
        s+='a'+(v%k);
        v=v/k;
    }
    while(s.length()<l){
        s+='a';
    }
    reverse(s.begin(),s.end());
    return s;
}
int main() {
	// your code goes here
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t,l=1;
	cin>>t;
	while(t--){
		int n,k;
		cin>>n>>k;
		string s;
		cin>>s;
		int ans=0,h=ceil(n/2.0);
		string t="";
		
    for(int i=0;i<h;i++){
        t+=s[i];
    }


    int total=0;
    total=basek(t,k);
    for(int i=0;i<total;i++){
        string temp=generate("",h,i,k);
        if(temp<t){
            ans+=1;
        }
    }
        int nextSt=0;
       string r=t;
       reverse(r.begin(),r.end());
       if((n&1)){
           nextSt+=1;
       }
       for(int i=nextSt;i<r.length();i++){
           t+=r[i];
       }
       if(t<s){
           ans+=1;
       }   
    cout<<"Case #"<<l<<": "<<ans<<endl;
    l++;
}
return 0;

} ~~~~~

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

    You need to compute the answer modulo $$$10^9+7$$$. It seems like you forgot about it.