2037A - Twice
Problem Credits: cry
Analysis: cry
We want to count how many times we can choose $$$i$$$ and $$$j$$$ such that $$$a_i = a_j$$$. Suppose $$$f_x$$$ stores the frequency of $$$x$$$ in $$$a$$$. Once we choose $$$a_i = a_j = x$$$, $$$f_x$$$ is subtracted by $$$2$$$. Thus, the answer is the sum of $$$\lfloor \frac{f_x}{2} \rfloor$$$ over all $$$x$$$.
t = int(input())
for _ in range(t):
n = int(input())
a = list(map(int, input().split()))
print(sum([a.count(x) // 2 for x in range(n + 1)]))
2037B - Intercepted Inputs
Problem Credits: cry
Analysis: chromate00
It is worth noting that test $$$4$$$ is especially made to blow up python dictionaries, sets, and Collections.counter. If you are time limit exceeding, consider using a frequency array of length $$$n$$$.
You must check if you can find two integers $$$n$$$ and $$$m$$$, such that $$$n \cdot m+2=k$$$. You can either use a counter, or use two pointers. Do note that $$$n^2+2=k$$$ is an edge case that must be separated if you use a counter to implement it. This edge case does not appear in the two pointers approach. Time complexity is $$$O(n \log n)$$$ (assuming you are wise enough to not use a hash table).
testcases = int(input())
for _ in range(testcases):
k = int(input())
list = input().split()
freq = []
for i in range(k+1):
freq.append(0)
for x in list:
freq[int(x)] = freq[int(x)]+1
solution = (-1,-1)
for i in range(1,k+1):
if i*i==k-2:
if freq[i]>1:
solution = (i,i)
elif (k-2)%i==0:
if freq[i]>0 and freq[(k-2)//i]>0:
solution = (i, (k-2)//i)
print(solution[0], solution[1])
2037C - Superultra's Favorite Permutation
Problem Credits: sum
Analysis: chromate00
Remember that all even numbers greater than $$$2$$$ are composite. As $$$1+3 > 2$$$, any two numbers with same parity sum up to a composite number. Now you only have to find one odd number and one even number that sum up to a composite number. One can manually verify that there is no such pair in $$$n \leq 4$$$, but in $$$n=5$$$ there exists $$$(4,5)$$$ which sums up to $$$9$$$, a composite number.
for _ in range(int(input())):
n = int(input())
if n < 5:
print(-1)
continue
for i in range(2,n+1,2):
if i != 4:
print(i,end=" ")
print("4 5",end=" ")
for i in range(1,n+1,2):
if i != 5:
print(i, end = " ")
print()
2037D - Sharky Surfing
Problem Credits: cry
Analysis: chromate00
Process from earliest to latest. Maintain a priority queue of power-ups left so far. If Mualani meets a power-up, add it to the priority queue. Otherwise (Mualani meets a hurdle), take power-ups in the priority queue from strongest to weakest until you can jump over the hurdle. This guarantees that each time Mualani jumps over a hurdle, she takes the minimum number of power-ups necessary. Time complexity is $$$O((n+m)\log m)$$$, where $$$O(\log m)$$$ is from the priority queue.
Note that the hurdle intervals are inclusive. If there is a hurdle at $$$[l, r]$$$, she must jump from position $$$l-1$$$ to $$$r+1$$$.
import sys
import heapq
input = sys.stdin.readline
for _ in range(int(input())):
n,m,L = map(int,input().split())
EV = []
for _ in range(n):
EV.append((*list(map(int,input().split())),1))
for _ in range(m):
EV.append((*list(map(int,input().split())),0))
EV.sort()
k = 1
pwr = []
for a,b,t in EV:
if t == 0:
heapq.heappush(pwr,-b)
else:
while pwr and k < b-a + 2:
k -= heapq.heappop(pwr)
if k < b-a + 2:
print(-1)
break
else:
print(m-len(pwr))
2037E - Kachina's Favorite Binary String
Problem Credits: vgoofficial
Analysis: Intellegent
Notice that for if for some $$$r$$$ we have $$$f(1, r) < f(1, r + 1)$$$ then we can conclude that $$$s_{r + 1} = 1$$$ (if it is $$$0$$$ then $$$f(1, r) = f(1, r + 1)$$$ will be true) and if $$$f(1, r)$$$ is non-zero and $$$f(1, r) = f(1, r + 1)$$$ then $$$s_{r + 1}$$$ is $$$0$$$.
Unfortunately this is only useful if there is a $$$0$$$ in $$$s_1,s_2,...,s_r$$$, so the next thing can try is to find is the value of the longest prefix such that $$$f(1, r)$$$ is $$$0$$$ (after this point there will be a zero in all prefixes).
See that if $$$f(1, r) = 0$$$ and $$$f(1, r + 1) = k$$$ then $$$s_{r + 1} = 1$$$, the last $$$k$$$ characters of $$$s_1,s_2,...,s_r$$$ must be $$$0$$$ and the first $$$r - k$$$ characters must be $$$1$$$. To prove this we can argue by contradiction, suppose it is not true and then it will become apparent that some shorter prefix will be non-zero when we query it.
The one case that this does not cover is when all prefixes are zero, from similar contradiction argument as above we can see that the string must look like $$$111...1100....000$$$ in this case, in this case it is not hard to see that all queries will give a value of zero, and thus we can report that it is impossible.
So we should query all prefixes, the first one which is non-zero (if this does not exist we can report impossible) we can deduce its value as discussed above, then there will be a $$$0$$$ in the prefix so we can deduce all subsequent characters as discussed at the start.
def qu(a,b):
if (a,b) not in d:
print("?", a+1,b+1)
d[(a,b)] = int(input())
return d[(a,b)]
for _ in range(int(input())):
d = dict()
n = int(input())
SOL = ["0"] * n
last = qu(0,n-1)
if last:
z = 1
for i in range(n-2,0,-1):
nw= qu(0,i)
if nw != last:
SOL[i+1] = "1"
last = nw
if last == 0:
z = i+1;break
if last:
SOL[1] = "1"
SOL[0] = "0"
else:
last = 1
for j in range(z-2,-1,-1):
nw = qu(j,z)
if nw == last:
SOL[j] = "1"
last = nw
print("!","".join(SOL))
else:
print("! IMPOSSIBLE")
2037F - Ardent Flames
Problem Credits: vgoofficial
Analysis: vgoofficial
Let's perform binary search on the minimum number of hits to kill at least $$$k$$$ enemies. How do we check if a specific answer is possible?
Let's consider a single enemy for now. If its health is $$$h_i$$$ and we need to kill it in at most $$$q$$$ attacks, then we need to be doing at least $$$\lceil\frac{h_i}{q}\rceil$$$ damage per attack to this enemy. If this number is greater than $$$m$$$, then obviously we cannot kill this enemy in at most $$$q$$$ attacks as the maximum damage Xilonen can do is $$$m$$$ damage per hit. Otherwise, we can model the enemy as a valid interval where we can place Xilonen. Specifically, the inequality $$$m-|p-x|\geq\lceil\frac{h_i}{q}\rceil$$$ must be satisfied.
Now that we have modeled each enemy as an interval, the problem is reduced to finding whether or not there exists a point on at least $$$k$$$ intervals. This is a classic problem that can be approached by a sweep-line algorithm, sorting the events of intervals starting and ending by time and adding $$$1$$$ to your counter when an interval starts and subtracting $$$1$$$ to your counter when an interval ends.
Note that the maximum possible answer to any setup with a solution is $$$\max( h_i)=10^9$$$, so if we cannot kill at least $$$k$$$ enemies in $$$10^9$$$ attacks then we can just output $$$-1$$$ as our answer.
The total time complexity is $$$O(n\log({n})\log({\max(h_i)})$$$.
import sys
input = sys.stdin.readline
from collections import defaultdict
for _ in range(1):
n,m,k = map(int,input().split())
h = list(map(int,input().split()))
x = list(map(int,input().split()))
lo = 0
hi = int(1e10)
while hi - lo > 1:
mid = (lo + hi) // 2
ev = defaultdict(int)
for i in range(n):
ma = (h[i] + mid - 1) // mid
if ma > m: continue
ev[x[i]-m+ma] += 1
ev[x[i]+m-ma+1] -= 1
sc = 0
for y in sorted(ev.keys()):
sc += ev[y]
if sc >= k:
hi = mid
break
else:
lo = mid
if hi == int(1e10):
print(-1)
else:
print(hi)
2037G - Natlan Exploring
Problem Credits: vgoofficial
Analysis: vgoofficial
Denote $$$dp[i]=$$$ the number of ways to get to city $$$i$$$. Brute-forcing all possible previous cities is out of the question, as this solution will take $$$O(n^2\cdot\log({\max{a_i}}))$$$ time complexity. What else can we do?
Instead, consider caseworking on what the greatest common factor can be. Let's keep track of an array $$$count$$$ which for index $$$i$$$ keeps track of the sum of $$$dp$$$ values of all previous cities who has a factor of $$$i$$$. Say the current city has attractiveness $$$a_i$$$. We can almost recover $$$dp[i]$$$ by adding up the $$$count$$$ values of all factors of $$$a_i$$$. Unfortunately, this fails as it overcounts many instances. For example, if $$$\gcd(a_i, a_j)=12$$$ the $$$dp$$$ state from $$$i$$$ will be counted five times: $$$2, 3, 4, 6, 12$$$.
Note that we don't actually care what the greatest common factor is, since the only requirement is that the greatest common factor is not $$$1$$$. This also means that repeat appearances of the same prime number in the factorization of $$$a_i$$$ doesn't matter at all — we can assume each prime factor occurs exactly once. Now, if $$$\gcd(a_i, a_j)=12$$$, it is only counted three times: $$$2,3,6$$$. Now, instead of blindly adding the $$$count$$$ values from all previous states, let's instead apply the Principle of Inclusion-Exclusion on the prime factors. Let's first add the $$$count$$$ values from all prime factors, then subtract the $$$count$$$ values from all factors with two prime factors, then add the $$$count$$$ values from all factors with three prime factors, and so on. It can be seen that actually, the value is only counted one time now.
So what's the time complexity of this solution? Precomputing the set of all prime number takes $$$O(\max(a_i)\log(\max(a_i)))$$$ time (by the harmonic series $$$\frac{n}{1}+\frac{n}{2}+\ldots+\frac{n}{n}\approx n\log(n)$$$). For each number $$$a_i$$$, we have to consider all $$$2^{f(a_i)}$$$ subsets of prime factors, where $$$f(a_i)$$$ is the number of prime factors of $$$a_i$$$. The number with the most distinct prime factors is $$$510510=2\cdot3\cdot5\cdot7\cdot11\cdot13\cdot17$$$, so worst case $$$2^7=128$$$ operations are needed per number. This goes to a total operation count of approximately $$$128\cdot n$$$ which will pass in the time limit.
Note that we may also use the Mobius function to compute the answer. The Mobius function's properties makes it utilize the Principle of Inclusion-Exclusion efficiently. The time complexity of this solution is $$$O(\max(a_i)\log(\max(a_i))+n\max(d(a_i)))$$$ where $$$d(a_i)$$$ is the maximum number of factors of $$$a_i$$$. This time complexity can be shown to be the same as the above time complexity.
import sys
def input():
return sys.stdin.buffer.readline().strip()
MOD = 998244353
ma = int(1e6 + 5)
P = [1] * ma
D = [[] for _ in range(ma)]
for i in range(2, ma):
if P[i] == 1:
for j in range(i, ma, i):
P[j] = i
F = [0] * ma
LU = [0] * ma
BMS = [[] for _ in range(ma)]
RES = []
from itertools import combinations
def getBMS(x):
if not BMS[x]:
y = help(x)
for i in range(len(y)):
p = combinations(y, i + 1)
for a in p:
xx = 1
for j in a:
xx *= j
BMS[x].append((xx,i))
return BMS[x]
def helps(x):
y = x
while x != 1:
s = P[x]
D[y].append(s)
while x % s == 0:
x //= s
def help(x):
if not D[x]: helps(x)
return D[x]
for yy in range(int(input())):
n = int(input())
A = list(map(int, input().split()))
for xx,i in getBMS(A[0]):
F[xx] = 1
LU[xx] = yy
for i in range(1, n - 1):
tot = 0
for xx, j in getBMS(A[i]):
if LU[xx] != - 1 and LU[xx] != yy:
F[xx] = 0
LU[xx] = yy
if F[xx]:
if j % 2:
tot -= F[xx]
tot %= MOD
else:
tot += F[xx]
tot %= MOD
for xx, j in getBMS(A[i]):
F[xx] += tot
F[xx] %= MOD
S = 0
for xx,i in getBMS(A[-1]):
if LU[xx] != - 1 and LU[xx] != yy:
LU[xx] = yy
F[xx] = 0
if F[xx]:
if i % 2:
S -= F[xx]
S %= MOD
else:
S += F[xx]
S %= MOD
RES.append(str(S))
print("\n".join(RES))
nice fast editorial
fast editorial !! thankYou
damn quick editorial
Very Nice contest. :)
fast tutorial
Damn! Ultra Fast editorial Great Contest. Very good problems, Thanks!
Intellegent orz
wtf
could anyone help me to figure out what is wrong here:292060911
You're taking powerups you can't have.
Think about this test case:
294624105 can you please help in whats wrong in this code.
Working soln: https://mirror.codeforces.com/contest/2037/submission/292084754
You can't take every powerup.. you always need to compare with current_hurdle
yotta fast edito'
Thankkyou
Hi everyone, I apologize for the statement for D being unavailable for ~15 minutes during the round. It turns out I misspelled \textbf which caused the PDF to not generate. :(
For 2037F - Ardent Flames can you please explain which intervals are we talking about here? — sorting the events of intervals starting and ending by time and how are we trying to do binary search?
The intervals are possible $$$p$$$ such that $$$m-|p-x|\geq\lceil\frac{h_i}{q}\rceil$$$. You do binary search on the answer, and if such $$$p$$$ exists, you move the right bound to the mid; otherwise left bound.
very cool round, thank u.
I liked this contest, especially C exercise was interesting and pretty quirky at first :D Hope to see more div3 contests in the future
Can someone take a look at my implementation? (since below is my thinking for E which matches the tutorial exactly)
IMPOSSIBLE if and only if there exists no "01" substring, which is equal to querying the entire string and getting an answer of 0.
Otherwise, there is some "01", and we start querying all the prefixes [1, 2], [1, 3] ... [1, n]. Suppose the first one to give a non-zero answer is [1, i]. Let that answer be R. Then, since all prefixes before [1, i] gave 0 as an answer, the string over [0, i-1] is i-1-R 1's followed by R 0's. Also s[i] must be 1. To determine the suffix s[i+1, n], we query over the prefixes still [1, i+1], [1, i+2] ... [1, n], and, at each query, if the answer increases from the previous one, we have a 1 there, otherwise it is 0 there. In total, we take exactly 1 query for each char in s[2, n], meaning we require n-1 queries.
Implementation: https://mirror.codeforces.com/contest/2037/submission/292068546 (skip to very bottom, there is a bunch of template stuff at top)
Bro you should return int in the function
char(this should be int) interQuery(int a, int b) { std::cout << "? " << a << " " << b << endl; std::cout.flush();
}
Good luck Mate..!!
NOOOOO WTH, I didn't solve E due to that BS!!! :(((( This is genuinely heartbreaking -- the difference between being rank ~1500 and being rank ~500
Thanks for the contest, I was glad to participate) Thanks for explaining task G, I was very hesitant when I sent it and got a time limit exceeded on the 5th test
D felt like it would be hard problem at first but once u start solving it I found it easier than C
I was waaay off for D. i was thinking graphs. Thanks for the learning.
As a Pythonist participant, thanks for covering test 4 on Problem B that gives TLE verdict with dictionaries. I too got this verdict: Submission 291964656 Then, using set for tracking a prior occurrence worked on Submission 291974200 , instead of having to rely on the suggested collections.Counter().
Will have to see if this get hacked or failed in any of the main test.
As a Pythonist tester, happy to hear :)
Edit: Looking at your Solution it is probably still hackable as set uses the same hash function as a dict, :(
You've saved us an unexpected TLE! :clapping:
Yes, it is also noted under the editorial for Problem B that Set and Dictionary uses same Hash function. But, my understanding is that as Set only stores a single occurrence of an element, there's only that single entry in that Set that will be subject to that collision with every matching hash attempt, unlike a Dictionary where that entry also buckets corresponding values to that key. Please do suggest if you have any such testcase which may fail this submission. I would have been amazed to see it getting hacked on this possibility too.
非常好的题目,使我大脑旋转:D
Don't use Chinese to reply in CodeForces.
how tf a newbie chineese ?
Help me with this please: 292083026
You need to continue processing hurdles until the left bound of the current hurdle surpasses current power-up.
For your code, consider:
which your code gives $$$-1$$$ but the answer is $$$2$$$.
Please review my answer too : 292104008 , it also gives output -1 to the above testcase that you have provided and I have run my loop on hurdles not powerups, but I am unable to understand why the answer should be 2 for this testcase and not -1 because after the first hurdle {5 5} the power left should be zero so how will we reach to 10 and get +20 in power.
Jumping through a hurdle doesn't consume power. It only requires enough power.
Thankyou
How to implement the Inclusion-Exclusion in G?
I knew about the principle and just did a bunch of for loops which at least look kinda cool :D 292061306 but I see others used other method.
its essentially iterating through the masks, if the number of elements we're grabbing is even, subtract it, otherwise add it
Got it, thanks!
Respect the dedication of coding allat, the usual way of implementing the inclusion exclusion is with bitmasks, iterate from 0, having no elements in the set, to 2^n — 1, having everything in the set, when the i'th bit is 1, it means the i'th element is in the set, now u can notice for odd sizes u add for even sizes u subtract, after calculating the current contribution, if the number of set bits was odd add it otherwise subtract it
Can you explain why you did this and what is val array achieving?
i think it would be better to have G1 with lower constraint on $$$a_i <= 10^3$$$ to allow
$$$O(n*max(d(a_i)) ^ 2)$$$ solution as there are max 32 factors up to 1000, but anyways nice problems.
Thanks for the contest!
It would be solvable in O(nA), where A is maximal a[i] with dp[x] = # of paths ending at element x, so it would be too easy.
oh yes, i didn't think of it.
I am unable to understand why am i getting idleness time limit exceeded. — https://mirror.codeforces.com/contest/2037/submission/292077028. Please someone help.
Try with following test case, it shows "!" as answer
Can someone suggest some binary search problems like F (same or little higher difficulty) please.
Q3 and Q4 of today's leetcode weekly contest. Q3 is easier (*1300 in cf) and Q4 is harder (*2000 in cf).
Thanks a lot.
https://mirror.codeforces.com/blog/entry/127432
Thanks a lot.
Hi I have two doubts.
First, why in problem B, using dictionaries in Python give TLE, but AC in C++?
Second, what is wrong in my code for problem E? https://mirror.codeforces.com/contest/2037/submission/292049495
I query (1, i) for i from 1 to n, find the first point where this value is non zero, and if this value increases fill in 1, else 0.
You cannot query $$$[1,1]$$$
FUCK.
Can someone help me with this solution for D. 292088654
Before visiting
h[k]
, confirm ifk<n
: 292092021Thanks a lot.
292093110
can someone pls see why this gives a wrong ans and what do I need to change ?
Check if $$$curr<n$$$ before using it as the index. 292094676
What's wrong with my solution for D? it gives tle(test-2). 292076200
i=h[k].second
and the followingi=h[i].second
are wrong. They're coordinates, not indices.Thanks!!
can somebody explain tourist code for problem G ? whats the mob array ?? whats the intuition behind the solution ?
291975854
or just simply explain whats the mobius function solution
You can see the mobius function as the coefficients of the inclusive-exclusive solution
Mobius function $$$\mu(n) = (-1)^k \cdot [\alpha_1=\alpha_2=\dots=\alpha_k=1]$$$ where $$$n=\prod\limits_{i=1}^k p_i^{\alpha_i}$$$.
Useful property of Mobius function is that $$$\sum\limits_{d|n}\mu(d)=[n=1]$$$.
Consider $$$\texttt{dp}[i]$$$ is the number of paths from $$$1$$$ up to $$$i$$$ and $$$\texttt{sum}[i][x]=\sum\limits_{j=1}^{i}\texttt{dp}_j\cdot [a_j=x]$$$.
We may calculate $$$\texttt{dp}[i]$$$ as $$$\sum\limits_{j=1}^{i-1}\texttt{dp}_j-\sum\limits_{x=1}^{10^6}\texttt{sum}[i-1][x]\cdot [\gcd(x, a_i)=1]$$$. Let us apply the property of Mobius function for $$$[\gcd(x, a_i)=1]$$$. So that:
For each $$$d$$$ you may maintain $$$\sum\limits_{x=1}^{10^6}[d|x]\cdot \texttt{sum}[i-1][x]$$$ and $$$d$$$ is the divisor of $$$a_i$$$ what makes it possible to compute $$$\texttt{dp}[i]$$$ in $$$\mathcal{O}(\sqrt{a_i})$$$.
I loved problem F, any problems like it please? :)
LeetCode 3357
Thank you!
Using Counter still failed me in test case 4 for B (Or maybe there is a mistake in my implementation)
Testcase 4 provokes hash collisions in Python, you can either use a Wrapper to avoid them or use an apporach without hashing.
I am aware but the Editorial mentioned using Counter to avoid TLE
Oh, well it technially works if you do it with strings, but at that point you could just us normal set or dict. To my knowledge Counter uses the same hash function anyways.
My bad, I wrote the note and I'm not really familiar with python. You'd have to use a frequency array of length $$$n$$$.
cry would be blessed if you also post the C++ code rather than just the 3 lines of the explanation in which you think everyone should understand how to solve the problem. Not everyone is a genius like you.
The code will be added after the open hacking phase
I would've ACed D if I used multiset instead of set. That was the only change I made for my code to AC after the contest... :(
292066305 292064554 gpt guy solve g in 3 minutes
can we solve D problem using dp approach,with two cases only selecting a particular power or ignoring it
that will be correct but very slow , O(n^2) when seeing high constraints like 1e6. Try thinking greedy
One easy way of preventing tle with sets in Python for B is to just move all the factors of k-2 into another map or set and do the same thing.
Hey guys, I don't know why my binary search solution fails. If you could help me with this that would amazin ^-^ thanksss
https://mirror.codeforces.com/contest/2037/submission/292111215
ahh forgot to include problem in the post, it's problem B btw sorryy
Nice contest, as expected from cry! Btw in problem E, were the constraints on $$$n$$$ reduced from $$$10^5$$$ to $$$10^4$$$? I used 32-bit integer during the contest and realized later on that my solution could get hacked...
In fact, in testing, several testers got WA verdict with n<=10^5 because of overflow. Since its an interactive problem and the query limit is the hard part of the problem (as opposed to the time limit) we decided just to make n<=10^4 so nobody can overflow.
Thanks for the fast editorial.
Why is there a runtime Error for this submission?
https://mirror.codeforces.com/contest/2037/submission/292195133
The length of
counter
is not enough. Consider $$$[2,2,1,1,1,1]$$$, your code visitscounter[4]
and crashes.great contest::)
damn, fast tutorial! nice contest
Will anyone explain how to do G with mobius inversion?
click here
Thanks for the contest!
I like to share some lessons I learned during this contest.
With only 30 minutes left, once a tempting idea occurred to me for problem E (do f(1,2), if 0 then impossible, otherwise, do f(1,i) for each i in [2,n])
I rushed into this idea without any checking or some sort of a proof.
It was only when I got WA that I prompted my mind to think about the underlying assumptions in this solution. And I immediately realized, it's possible to do f(n-1,n), same idea. then I rushed again, now lost all the time. and couldn't solve the problem.
Upsolving this task, I realized that if there any "01" substring in s, then it's possible with enough queries to locate this substring and construct the rest. Now, I had another idea, this time, it was not easy at least for me to find the bug, but there was another very strong indication that this cannot be the way. The solution was 150+ lines of ugly troublesome problematic error-prone code. lots of if-else if, lots of ++, +=2, -=2 and shit.. That should have been more than enough to discard this whole idea from the beginning.
But I discovered the problem, after 1 hour, I knew it's not working.
The interesting thing is once I prompted my mind to think again a different solution, I quickly found the right idea, this time it was so convincing and I can see the code is reasonable and elegant.
So, 1. test and challenge your idea, you don't have to have a rigorous proof, but at least some argument, and the min is to see what assumptions you're making
2. if the solution is so long and complicated, with unreasonable amount of cases, it's likely not the intended solution. and if it is, then love yourself and just discard this problem.
This is common sense but sometimes, one forget common sense esp. during contest pressure. I made similar mistake with problem C. I think it will really benefit to write down some tips next time and read before the contest.
In the D Question, I was confused that if the jump power is used for particular jump then same cannot be used by it again for eg. jump_power = {1,3,5}, hurdle= {-6, -6} ,then I thought the answer would be -1, since the 5, 3 would be used for first jump and it cannot be reused later. sorry, but can some one please help me find which part of the sentence indicated that we can reuse it twice.thank you
"When she is at position x with a jump power of k, she can jump to any integer position in the interval [x,x+k]."
It is clear that there is not a limit which stop Mualani jumping twice with the same distance.
thank you, sorry my bad I made a wrong assumption that after jump it decreases/loses its power
I wonder why G < F? I think the solution of greedy is easy to come out.
I meant F is much easier.
we can also do 2nd by binary search.
can somebody explain me why we have to output 2 3 instead of 3 2 in example output? (B problem) my code btw: 292481770 edit: well i just found my code problem (fixing it)
Can anyone explain why this is true for G:
Note that we don't actually care what the greatest common factor is, since the only requirement is that the greatest common factor is not 1. This also means that repeat appearances of the same prime number in the factorization of ai doesn't matter at all — we can assume each prime factor occurs exactly once.
Let's first add the count values from all prime factors, then subtract the count values from all factors with two prime factors, then add the count values from all factors with three prime factors, and so on. It can be seen that actually, the value is only counted one time now.
Can someone explain why this works?
For E,
I tried to make the string from left to right (? i n ) ,and in between if a 0 is encountered the remaining following sequence has to be (1111...1000...0)
For the input 2 01 its getting passed in test case 2 but when the same input comes in test case 3 its getting wrong answer!
Could someone please help me out!
Submission: 293642176
294078854 Hi, I got a negative output in test 6, can someone please help me to see what's wrong with my code?
in problem D: testcase 1:
2 5 50 7 14 30 40 2 2 3 1 3 5 18 2 22 32
after taking 4th power-up my total power is 11, but to jump the 2nd hurdle I need a power-up of atleast 12 right? Why is the answer 4 then? shouldn't it be 5?
You skip the 4th powerup at $$$x_i = 18$$$ and take the one at $$$x_i = 22$$$ instead