### kostka's blog

By kostka, 13 months ago,

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

• +41

 » 13 months ago, # |   0 Since competition ends now can anyone tell me How to check if two expression with only + and * gives same value or not?
 » 13 months ago, # |   +38 Yay AC.I realised that the OJ server is laggy, is that your experience as well?
•  » » 13 months ago, # ^ |   +6 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.
•  » » » 13 months ago, # ^ |   +9 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.
•  » » » » 13 months ago, # ^ |   +3 same happened with me i faced 3 extra penalties due to this:(
 » 13 months ago, # |   +75 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 :(
•  » » 13 months ago, # ^ |   -6 Yeah I also feel some lag while submitting solution.
•  » » 13 months ago, # ^ |   +17 +1I even submitted the same code twice because of that.
•  » » » 13 months ago, # ^ | ← Rev. 2 →   -19 .
 » 13 months ago, # |   +22 Problem B mostly same as https://atcoder.jp/contests/abc190/tasks/abc190_djust divide the final answer by 2
•  » » 13 months ago, # ^ |   +24 And you explained me quite well here
•  » » » 13 months ago, # ^ |   +20 That's why I remembered this problem:)
•  » » » » 13 months ago, # ^ |   +31 Reunion xD
•  » » » 13 months ago, # ^ |   +18 Benefits of upsolving XD
•  » » 13 months ago, # ^ |   0 so sad, I recognized it too but had never got around to actually upsolving it...what I did instead at the time was try out a 2-pointers solve which (hindsight, duh, 10^12) was still way too slow... b-b-but it was around when the edu section here at codeforces put up that tutorial so I just had to try it everywhere...!
•  » » 13 months ago, # ^ |   +11 It is available on leetcode and Binarysearch too: Leetcode Binarysearch.
•  » » 13 months ago, # ^ |   0 LoL I just realized I did this in exactly same way as I did this Atcoder D in Atcoder one I printed ans*2 here ans
 » 13 months ago, # | ← Rev. 2 →   0 thank you
 » 13 months ago, # |   +32 Congratulations Errichto on winning the roundEagerly waiting for your screencast (to know how I messed up today)
•  » » 13 months ago, # ^ |   +56 Thanks and here you go https://youtu.be/TagGSh6QALs
 » 13 months ago, # |   +4 How to solve A test case 2?
 » 13 months ago, # | ← Rev. 3 →   0 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$.
•  » » 13 months ago, # ^ |   0 The analysis is already published.
•  » » 13 months ago, # ^ |   0 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.
 » 13 months ago, # | ← Rev. 2 →   -25 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, ASimple counting problem, iterate uptil n/2 on a string as we dont care about the other half and then fix current position and then add $(s[i] - 'a')$$k^r$ to the answer and decrement $r$. Initially $r$ is the number of free postions after we fix the first position. Also check all edge cases. BThis was also a math problem. After a bit of rearrangement we get this : $(D + 2K)(D + 1)$ $=$ $2G$ where $D$ is the number of days. Now factorize $2G$ into product of 2 numbers and bruteforce over these pairs to get the value of $D$ (set them either $(D+1)$ or $(D + 2K)$ and check if the $K$ value is valid and increment the count. Code - A//Think simple yet elegant. #include using namespace std; #define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define ll long long #define all(v) v.begin(),v.end() #define ff first #define ss second #define pb push_back #define mp make_pair #define pi pair #define REP(i,n) for(int i=0;i 0) { if (b & 1) res = res * a % mod; //mod a = a * a % mod; //mod b >>= 1; } return res; } ll add(ll a,ll b){ return (a+b+mod)%mod; } ll mul(ll a,ll b){ return ((a%mod)*(b%mod))%mod; } ll cnt = 0; void rec(int n,int k,string s,string now){ if(s.length()==n){ string t1 = s; reverse(all(s)); if(t1==s and t1> n >> k; string s; cin >> s; ll ans = 0,rem; if(n%2) rem = n/2; else rem = n/2 - 1; for(i=0;i1){ string tt1 = s.substr(0,n/2); reverse(all(tt1)); tt = s.substr(0,n/2) + s.substr(n/2,1) + tt1; if(tt> t; int cn = 1; while(t--){ cout<<"Case #"< using namespace std; #define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define all(v) v.begin(),v.end() #define F first #define S second #define ll long long #define pb push_back #define mp make_pair #define pi pair #define REP(i,n) for(int i=0;i> g; vector p; for(i=1;i*i<=2*g;++i){ if((2*g)%i==0) p.pb({i,2*g/i}); } set h; for(auto [k1,k2] : p){ ll n1 = k1-1; if(k2-n1>=0 and (k2-n1)%2==0 and (k2-n1)/2 > 0) h.insert((k2-n1)/2); n1 = k2-1; if(k1-n1>=0 and (k1-n1)%2==0 and (k1-n1)/2 > 0) h.insert((k1-n1)/2); } cout<<(int)h.size()<<"\n"; } int main(){ fast; int q; cin >> q; int cn = 1; while(q--){ cout<<"Case #"<
•  » » 13 months ago, # ^ |   +1 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)$
•  » » » 13 months ago, # ^ |   0 Cool idea, though the complexity of both our approaches is the same.
•  » » » 13 months ago, # ^ |   0 B is equivalent to just counting the number of odd divisors of $G$
 » 13 months ago, # |   +18 Expected value of probability of asking a problem from "Probability Theory" in Google Kickstart or Codejam =1.
 » 13 months ago, # |   0 Can someone help me to provide a counter-case for A, please? My Code for A: Smaller Strings#include using namespace std; #define M1 1000000007 #define forl(i,n) for(int i=0;i0&&r<=y) { if(r&y) { ans*=x; ans%=m; } r<<=1; x*=x; x%=m; } return ans; } void ans(){ int t;cin>>t; fore(l,t){ cout<<"Case #"<>n>>k>>s; int f=0; if(n==1){ int x=(s[0]-'a'); cout<=0;i--){ if(s[i]s[n-1-i]){ break; } } if(g){ c++; } forl(i,(n-1)/2){ if(s[i]!='a'){ int y=(s[i]-'a'); int r=(n-1)/2; int z=powM(k,r-i,M1); int w=(y*z)%M1; c=(c+w)%M1; } } cout<=0;i--){ if(s[i]s[n-1-i]){ break; } } if(g){ c++; } forl(i,(n-1)/2){ if(s[i]!='a'){ int y=(s[i]-'a'); int r=(n-1)/2; int z=powM(k,r-i,M1); int w=(y*z)%M1; c=(c+w)%M1; } } cout<
•  » » 13 months ago, # ^ | ← Rev. 2 →   +9 Check this testcase :  1 12 9 edciahibffdh  The output shud be 257993  but you are getting 257994 
•  » » » 13 months ago, # ^ |   +3 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 :'(
•  » » » 13 months ago, # ^ | ← Rev. 2 →   -8 I used a condition s[i] using namespace std; // #include //Read at https://codeforces.com/blog/entry/11080 // #include // using namespace __gnu_pbds; // template using oset = tree, rb_tree_tag, tree_order_statistics_node_update>; /* find_by_order(k):- returns itertator to kth largest element in set (0-based) order_of_key(x):- return number of values strictly less than x */ #define lll __int128 #define ll long long int #define ull unsigned long long int #define ld long double #define pii pair #define pll pair #define vi vector #define vii vector #define vl vector #define vll vector #define ar array #define setbits(x) __builtin_popcountll(x) #define f(i,l,r) for(ll i=l;i=m;i--) #define deb(...) cout<<" [" <<#__VA_ARGS__ ": " << (__VA_ARGS__) << "] "; #define clr(x) memset(x,0,sizeof(x)); #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() #define sz(x) (ll)x.size() #define INF (ll)(1e18) #define P (ll)(1e9+7) #define PI acosl(-1.0l) #define mod 998244353 #define pb push_back #define F first #define S second #define IP ios_base::sync_with_stdio(false);cin.tie(NULL); #define fixed(n) cout< bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; } template bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; } mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); int dx[]={1,0,-1,0}; int dy[]={0,-1,0,1}; const int MXN = 3e5+65; ll fact[MXN],ifact[MXN]; ll expo(ll a,ll x) { if(x==0) return 1; ll ans=expo(a,x/2); ans=ans*ans%P; if(x&1) ans=ans*a%P; return ans; } ll check(string &s) { ll n=sz(s); f(i,0,n/2) { if(s[i]!=s[n-1-i]) return 1; } return 0; } int main() { IP ll t=1; cin>>t; for(ll tc=1;tc<=t;tc++) { ll n,k; cin>>n>>k; string s; cin>>s; ll ans=0; if(check(s)) { string c=""; for(ll i=0;i<(n+1)/2;i++) { c+=s[i]; } for(ll i=(n/2)-1;i>-1;i--) { c+=s[i]; } if(c
 » 13 months ago, # |   +11 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.
•  » » 13 months ago, # ^ | ← Rev. 3 →   +13 $(70 * (a + 45) + 40 * (b + 9)) * (130 * (a + 23) + 90 * (b + 7))$Just some random sum and multiplication. it worked for me.
•  » » » 13 months ago, # ^ |   +8 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.
•  » » » » 13 months ago, # ^ |   +19 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)$
•  » » » » » 13 months ago, # ^ |   +8 Thanks for the explanation!
•  » » » » » 13 months ago, # ^ |   +1 Is Q4 meant to be solved using hash function ? I was thinking doing all non sense using bigint and all with max 200 digitsAsking 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
•  » » » » » » 13 months ago, # ^ | ← Rev. 2 →   +9 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.
 » 13 months ago, # | ← Rev. 3 →   +8 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 :).
•  » » 13 months ago, # ^ | ← Rev. 2 →   +8 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 !
•  » » » 13 months ago, # ^ |   +8 got it . Thanks !!
 » 13 months ago, # |   +41 Me after reading C:"I will never play rock paper scissors ever again!"
 » 13 months ago, # |   0 I can't understand what problem C meant they gave so confusing explanation tooIf anyone has good explanation please link it hereI solved A subtask 1B complete questionand D subtask 1 but I used randomisation and python large numbers
 » 13 months ago, # | ← Rev. 2 →   +60 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}
•  » » 13 months ago, # ^ |   +67 I made the same mistake. It cost me 1 penalty, 30 minutes and 50 strands of hair
•  » » 13 months ago, # ^ |   +11 Could you explain it?
•  » » » 13 months ago, # ^ |   +22 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.
•  » » » » 13 months ago, # ^ |   +5 Oh right, it's my bad mistake. I thought the opponent chooses S with Pr[S] = s/(n-1).Thanks!
•  » » » » 13 months ago, # ^ |   0 Good to know that I was not the only one. Sadly I did not figure it out during the contest.
•  » » 13 months ago, # ^ |   0 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
•  » » 13 months ago, # ^ |   0 Can you help me find the error in my code? https://ideone.com/YCxupJDon't judge me by my rating, I don't use codeforces.
 » 13 months ago, # |   0 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...?
•  » » 13 months ago, # ^ |   0 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
 » 13 months ago, # | ← Rev. 9 →   +28 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. Codefrom hashlib import blake2b # Hack to define custom infix operators # Reference - https://code.activestate.com/recipes/384122/ class Infix: def __init__(self, func): self.func = func def __or__(self, other): return self.func(other) def __ror__(self, other): return Infix(lambda x, self=self, other=other: self.func(other, x)) h = lambda x: int(blake2b(str(x).encode()).hexdigest(), 16) op = Infix(lambda x, y: h((x, y))) for i in range(1, int(input()) + 1): E = [input() for _ in range(int(input()))] V = [eval(expr.replace('#', '|op|')) for expr in E] num = dict() for v in V: num[v] = num.get(v, len(num) + 1) res = ' '.join(str(num[v]) for v in V) print('Case #{}: {}'.format(i, res)) 
•  » » 13 months ago, # ^ | ← Rev. 2 →   0 I didn't know the inbuilt implementation of eval I did something like this codeimport sys input = sys.stdin.readline for _ in range(int(input())): print(f"Case #{_ + 1}: ", end='') n = int(input()) l = [] for i in range(n): l.append(input().strip()) l1 = [] for i in l: l1.append([]) j = 0 if i == '0': l1[-1] = 0 else: while j < len(i): if i[j] in '()*+#': l1[-1].append(i[j]) j += 1 else: t = '' while j < len(i) and i[j] not in '()*+#': t += (i[j]) j += 1 l1[-1].append(int(t)) ans = [] for i in range(len(l1)): if l1[i] != 0: l2 = list(l1[i]) while len(l2) > 1: idx = len(l2) - l2[-1::-1].index('(') - 1 if idx < len(l2) and idx >= 0: if l2[idx + 2] == '#': a = l2[idx + 1] b = l2[idx + 3] t = (a+17)*(9*(a+19)+(b+69)*23)*414+a+b*((a+23)*31+(b+27)*314)+1241+a*b*1213 if l2[idx + 2] == '+': t = l2[idx + 1] + l2[idx + 3] if l2[idx + 2] == '*': t = l2[idx + 1] * l2[idx + 3] l2 = l2[:idx] + [t] + l2[idx + 5:] ans.append(int(l2[0])) else: ans.append(0) fans = [-1 for i in range(len(ans))] s = set() ttt = 1 for i in range(len(ans)): if i not in s: fans[i] = ttt for j in range(i + 1, len(ans)): if ans[j] == ans[i]: fans[j] = ttt s.add(j) ttt += 1 s.add(i) print(*fans) 
•  » » 13 months ago, # ^ |   0 I upsolved it with a random oracle function @Infix @lru_cache(None) def op(x, y): return random.randint(0, 2**64-1) 
 » 13 months ago, # |   -14 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.
•  » » 13 months ago, # ^ |   0 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.
 » 13 months ago, # | ← Rev. 2 →   0 .resolved
•  » » 13 months ago, # ^ |   0 You can download the test cases from the website and debug your code.
 » 13 months ago, # |   +18 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.
 » 13 months ago, # |   +3 What will be the rating of problems A, B,C, D in terms of CF question ratings
•  » » 13 months ago, # ^ |   -18 In my opinion, it should be like:Problem B — Div2 A — 1100 — Tags: MathProblem A — Div2 B — 1500 — Tags: ImplementationProblem C — Div2 D — 2100 — Tags: DP, GamesProblem D — Div2 E — 2300 — Tags: Hashing
•  » » » 13 months ago, # ^ |   +9 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.
•  » » » » 13 months ago, # ^ |   0 I thought D will be interesting and suitable in a Hackforces Educational Round.
•  » » » » 13 months ago, # ^ | ← Rev. 2 →   0 No, problem B was certainly not close enough to Div 2c. It was comparable to Div 2a, although you had to arrive at the logic correctly. Otherwise, I dont see any reason to put it on the same page as Div 2c.
•  » » » » 13 months ago, # ^ |   -8 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?
•  » » » » » 13 months ago, # ^ |   0 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.
•  » » » » » » 13 months ago, # ^ |   +12 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)
 » 13 months ago, # | ← Rev. 2 →   0 Google kickstartSmaller StringsGetting TLE for Test Case2(Following official editorial's method)Can someone suggest any improvements please? ~~~~~ Your code here... #include 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()>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
•  » » 13 months ago, # ^ |   0 You need to compute the answer modulo $10^9+7$. It seems like you forgot about it.
•  » » » 13 months ago, # ^ | ← Rev. 3 →   0 thanks