Hello, Codeforces.
Contest: SpeedForces
Time: [contest_time:418314]
Writer: O--O
Tester: JOIN_GROUP, E404_Not_Found, psychobot
You will have 8 problems in 120 minutes.
Problems are very interesting and problem statements are short.
Problem C and D had little mistakes in statement.
Problem F had mistake in sample.
Winners
1. Kirill22
2. Svyat
3. huangxiaohua
4. Kniaz
5. wery0
6. bitset
Did you like the contest?
Solutions are opened.
As a tester, nice problems. I recommend to participate.
Alright
what the problem rate for this contest?
~ 800-1900
I like your contests! (Mathforces was good)
What about the score distribution?
normal ICPC scoreboard
I will write it.
omg maroonk
fake maroonrk
Are you sure that everything is fine with problem F?
Thanks for Saturday's workout!
I saw D on codeforces
Can you share the link?
idk, i found it incredibly long time ago in some blog
Not codeforces but there was an atcoder problem with basically the same idea and solution: https://atcoder.jp/contests/arc108/tasks/arc108_b.
Could you share Problem H solution? I thought of a solution involving set, however, seemed too complicated to implement, especially for 1 second execution time.
My solution was to iterate k, and maintain a data structure for the products a[i]*a[j] for j < k. For each k, you can iterate p, and query the data structure for the number of pairs a[i]*a[j] <= x / (a[k]*a[p]). The complexity should be O(N^2 log N).
I solved all the problems, but then the solution was changed to F and it broke for me. I understood why the text was changed, but in the end I didn't understand the solution. My idea is that for all n except 1 and 4, we need to output the prime number closest from below. And it is unpleasant that the old premises of the "complete solution" are now taken into account in the fine.
Condition F says that $$$n \ge 1$$$, but in test 4 $$$n=0$$$.
I changed the test.
Shit of piece, not a contest. Only idiots will give penalty for WA on first test. Testers are also silly noobs — missed obvious bug in checker in F. Author is so lazy, that decided not write validator for tests, resulting $$$0$$$ appeared in fourth test in F.
SHITOFPIECEOFSHIT!
Thanks bro
Why so rude bro? Mashup contests will give penalty for WA on first test by default and the author can't change this setting, Also do not write any comment with alt account, at least be brave for writing your comments with real account. wery0
In problem D, does the player have to delete all the substrings or just one? If s = "abababa" and t = "aba", does s become "b" after the 1st move or a player can choose? Why wasn't it specified in the statement or at least in samples?
ll p = 1000005; ll dp[p]; for(int i=0;i<p;i++){ dp[i] = INT_MAX; } dp[1] = 0; for (int i=2; i<p; i++) { dp[i] = dp[i-1]+1; for (int j=2; j<10; j++) { if (i % j == 0) { dp[i] = min(dp[i], dp[i/j]+j); } } }Link to sol: Soln
In problem E, just traversing inner loop from 2 to 10 passed the test cases. Just wanted to make sure if there is some logic behind this ? Since in the ideal solution, we should have checked for more than that, as given below
ll p = 1000005; ll dp[p]; for(int i=0;i<p;i++){ dp[i] = INT_MAX; } dp[1] = 0; for (int i=2; i<p; i++) { dp[i] = min(dp[i], dp[i-1]+1); for (int j=2; j*i<p; j++) { dp[i*j] = min(dp[i*j], dp[i]+j); } }Link to sol: Soln
Because we can construct a small answer as the upper bound.
For example $$$n=131071=(11...11)_2=2^{17}-1$$$,we can construct a scheme:
$$$*2 \rightarrow +1 \rightarrow...(16 times)$$$
We can simply see that the upper bound of the answer is $$$3 \lceil log_2(n) \rceil$$$.
Thanks, got it now.
I used segment tree in problem B, and ACed, but felt it was kinda dumb. Anyone thought of anything smarter?
my submission: [submission:186634062]
Help pls :P
thanks in advance.
Just keep array elements (let's call each element as $$$a_{i}$$$) and the value of xor of all elements (let's call it $$$X$$$), then after each query do this : Do $$$X$$$ xor $$$a_{i}$$$, after that replace $$$a_{i}$$$ with the integer given in query, and then do $$$X$$$ xor $$$a_{i}$$$ and print the answer. The point is when you xored a number and you want to remove it from xor you should xor with that number again, cuz it's like when you xor even times with a number, it's like you haven't added it to xor.
Find smallest $$$k$$$ that $$$\log_x k=\sqrt[x]k$$$.
Wait... when $$$x=4$$$ shouldn't $$$k=16$$$ be smaller?
Did I misunderstand something?
Upd: I didn't see $$$=x$$$.
Upd2: nifek said that there was no $$$x$$$. It seems that O--O your team need better testers!
Upd3: I'm really curious about it is something wrong with the statement or with the solution.
= x as well, that wont be = x
Sorry, I didn't see that.
Sorry for wasting your time.
The author edited the statement, you were correct, there was no = x
O--O please at least give credit to those who find mistakes in your problems and dont make them look dumb, stop just silently editing
I think
= xmade the problem very obvious, so maybe he decided not to include it.Although, he should clarify this himself.
didn't see =x at first either.
but now if consider =x, shouldn't that k be unique? how about smallest
Any one better idea for F? Im getting TLE
My solution: https://codeforces.com/submissions/_Aryan_#
How do find more updates on these unrated contests?