Идея: isosto, разработка: isosto
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
int main() {
int t; cin >> t;
while (t--) {
int n; cin >> n;
string s; cin >> s;
int i = 0;
while (i < n) {
int start = i;
cout << s[i++];
while (s[i++] != s[start]);
}
cout << endl;
}
}
Идея: diskoteka, разработка: diskoteka
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
int32_t main() {
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
k = min(k, 30);
cout << min(n, (1 << k) - 1) + 1 << "\n";
}
return 0;
}
Идея: pavlekn, разработка: playerr17
Разбор
Tutorial is loading...
Решение
testCases = int(input())
for testCase in range(testCases):
n, k, q = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
ans = 0
len = 0
for i in range(n):
if a[i] <= q:
len += 1
else:
if len >= k:
ans += (len - k + 1) * (len - k + 2) // 2
len = 0
if len >= k:
ans += (len - k + 1) * (len - k + 2) // 2
print(ans)
1840D - Фестиваль деревянных игрушек
Идея: diskoteka, разработка: diskoteka
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
sort(a.begin(), a.end());
int l = -1, r = 1e9;
while (r - l > 1) {
int m = (l + r) >> 1;
int i = 0;
while (i + 1 < a.size() && a[i + 1] - a[0] <= 2 * m) {
++i;
}
int j = n - 1;
while (j - 1 >= 0 && a.back() - a[j - 1] <= 2 * m) {
--j;
}
++i; --j;
if (i > j || a[j] - a[i] <= 2 * m) {
r = m;
} else {
l = m;
}
}
cout << r << "\n";
}
return 0;
}
Идея: diskoteka, разработка: diskoteka
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
int main() {
int x;
cin >> x;
while (x--) {
vector<string> s(2);
cin >> s[0] >> s[1];
int n = s[0].size();
int bad = 0;
for (int i = 0; i < n; ++i) {
if (s[0][i] != s[1][i]) {
++bad;
}
}
int t, q;
cin >> t >> q;
queue<pair<int, int>> unblock;
for (int i = 0; i < q; ++i) {
while (!unblock.empty() && unblock.front().first == i) {
if (s[0][unblock.front().second] != s[1][unblock.front().second]) {
++bad;
}
unblock.pop();
}
int type;
cin >> type;
if (type == 1) {
int pos;
cin >> pos;
if (s[0][pos - 1] != s[1][pos - 1]) {
--bad;
}
unblock.emplace(i + t, pos - 1);
} else if (type == 2) {
int num1, pos1, num2, pos2;
cin >> num1 >> pos1 >> num2 >> pos2;
--num1; --pos1; --num2; --pos2;
if (s[num1][pos1] != s[1 ^ num1][pos1]) {
--bad;
}
if (s[num2][pos2] != s[1 ^ num2][pos2]) {
--bad;
}
swap(s[num1][pos1], s[num2][pos2]);
if (s[num1][pos1] != s[1 ^ num1][pos1]) {
++bad;
}
if (s[num2][pos2] != s[1 ^ num2][pos2]) {
++bad;
}
} else {
cout << (!bad ? "YES" : "NO") << "\n";
}
}
}
return 0;
}
Идея: diskoteka, разработка: diskoteka
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int q;
cin >> q;
while (q--) {
int n, m;
cin >> n >> m;
int r;
cin >> r;
bool free[n + 1][m + 1][r + 1];
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= m; ++j) {
for (int k = 0; k <= r; ++k) {
free[i][j][k] = true;
}
}
}
for (int i = 0; i < r; ++i) {
int t, d, coord;
cin >> t >> d >> coord;
if (d == 1) {
for (int j = 0; j <= m; ++j) {
if (0 <= t - coord - j && t - coord - j <= r) {
free[coord][j][t - coord - j] = false;
}
}
} else {
for (int j = 0; j <= n; ++j) {
if (0 <= t - coord - j && t - coord - j <= r) {
free[j][coord][t - coord - j] = false;
}
}
}
}
bool dp[n + 1][m + 1][r + 1];
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= m; ++j) {
for (int k = 0; k <= r; ++k) {
dp[i][j][k] = !(i || j || k);
if (free[i][j][k]) {
if (i && dp[i - 1][j][k]) {
dp[i][j][k] = true;
}
if (j && dp[i][j - 1][k]) {
dp[i][j][k] = true;
}
if (k && dp[i][j][k - 1]) {
dp[i][j][k] = true;
}
}
}
}
}
int ans = -1;
for (int t = r; t >= 0; --t) {
if (dp[n][m][t]) {
ans = n + m + t;
}
}
cout << ans << "\n";
}
return 0;
}
1840G1 - В поисках истины (простая версия)
Идея: pavlekn, разработка: pavlekn
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e6 + 7;
int pos[MAXN];
int32_t main() {
int num;
cin >> num;
int ans = 0;
int cur = 1;
pos[num] = 1;
for (int i = 0; i < 1000; ++i) {
cout << '+' << " " << 1 << endl;
++cur;
cin >> num;
if (pos[num]) {
cout << '!' << " " << cur - pos[num] << endl;
return 0;
}
pos[num] = cur;
}
while (true) {
cout << '+' << " " << 1000 << endl;
cur += 1000;
cin >> num;
if (pos[num]) {
cout << '!' << " " << cur - pos[num] << endl;
return 0;
}
pos[num] = cur;
}
return 0;
}
1840G2 - В поисках истины (сложная версия)
Идея: pavlekn, разработка: pavlekn
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e6 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int pos[MAXN];
const int K = 400;
const int T = 300;
int get() {
return rng() % MAXN;
}
int32_t main() {
int num;
cin >> num;
int start = num;
int cur_delta = 0;
int N0 = num;
for (int i = 0; i < K; ++i) {
int delta = get();
cout << '+' << " " << delta << endl;
cur_delta += delta;
cin >> num;
N0 = max(N0, num);
}
cout << '-' << " " << cur_delta << endl;
cin >> num;
cout << '+' << " " << N0 - 1 << endl;
cur_delta = N0 - 1;
cin >> num;
pos[num] = N0;
for (int i = 0; i < T; ++i) {
++cur_delta;
cout << '+' << " " << 1 << endl;
cin >> num;
pos[num] = N0 + i + 1;
if (num == start) {
cout << '!' << " " << N0 + i << endl;
return 0;
}
}
cout << '-' << " " << cur_delta << endl;
cin >> num;
int ans = 0;
while (true) {
cout << '-' << " " << T << endl;
ans += T;
cin >> num;
if (pos[num]) {
cout << '!' << " " << ans + pos[num] - 1 << endl;
return 0;
}
}
return 0;
}
Nice contest!!
Where are constructivs?
On ROI 2023...
Problem F is a great problem, thank you
Is this a rated contest? My name is there in the rankings if the "show unofficial" box is checked, but I'm not there otherwise? I'm not sure why I'm not being included in them. Anyone know why?
Hacking phase is going on. Then, there will be a system test. Then, the final result will be published. It will be done by tomorrow I guess.
oh ok, I'm still not sure why I'm not a trusted and official participant though
Did you read the round announcement?
To qualify as a trusted participant of the third division, you must:
You have only competed in two rated rounds before this. Thus, you are not shown on the official leaderboard. Your rating will be updated regardless of this (but it might take some time).
I hacked the editorial solution for F. 208834351
There is another solution for G1. Let's make
+ kqueries with randomkfrom1to1e6until one of the indexes repeats. Also, let's save for each index sum of allkfor all queries done before it firstly appears (sum[next] = sum[current] + k). Thus, when an index repeats we can calculate length of the cycle (let it beL). As index repeats afterL+ 1queries,nis a divisor ofL. Let's iterate over alldthat divideLforO(sqrt(L))and check if index repeats afterd+ 1queries. Minimal of the suitabledis the answer. Average amount of queries required to find a cycle is around1250, the maximal number of divisors ofLis around1000, asL <= 1250 * 1e6, so no more than2250queries total. But on practice it is around1700.Code: 208832871
Upd1: Tested my solution on tests with random
nand indexes1, 2, 3 ... n. Average result is1200queries, but the dispersion is really high. The numbers were from650to3000. Guess G1 tests are not that good.That's... kinda strange. According to the birthday paradox, the chance of an index repeating within 2023 queries, with n = 1e6, is 87%, and there are more than 30 test that is like this, which means that you should have received "Wrong Answer". Guess you have dream luck then.
I'm not sure I follow the claim made in the editorial for F that if we can reach $$$(n, m)$$$ by traveling along some path, we can in fact do so while standing still at most $$$r$$$ times. For example, suppose $$$n = m = 3$$$ and our initial trajectory is to move from $$$(0, 0)$$$ to $$$(3, 0)$$$ to $$$(3, 3)$$$. Then suppose that at time $$$6$$$, the line $$$x = 3$$$ is targeted. If we don't stand still at all, we'll be at $$$(3, 3)$$$ at time $$$6$$$, while if we stand still once, we'll be at $$$(3, 2)$$$ at time $$$6$$$. In either case, we are at an inaccessible position, so if we want to follow the same trajectory we would need to stand still more than three times.
Of course, we can choose another trajectory to follow that will require us to stand still only once, but I'm confused specifically about the stronger claim made by the editorial since I didn't immediately see how to prove that there exists any path with which we stand still at most $$$O(r)$$$ times. This weaker claim seemed intuitive enough to me to submit under the assumption that it's true, but looking back it seems a bit tricky to prove formally.
By the way, does anyone know why the hacks on F were reversed? Was there an error in the generator that allowed invalid tests to be submitted?
Looking at the problem, it appears that the time limit has been changed to three seconds, which may be the reason the hacks were reversed. Will the round remain rated? This doesn't seem like too drastic a change, but it could reasonably have affected anyone who was hesitant to submit an $$$O(nm(n+m+r))$$$ solution due to the 1s time limit, and generally changing limits after the contest seems like a concerning precedent to set (e.g. in future rounds, should contestants submit solutions they think may get TLE due to a high constant factor and then complain after the contest hoping to have the TL raised?).
Incidentally, I'm not a big fan of the bounds of the problem: if your intent was to allow $$$O(nm(n+m+r))$$$ to pass, then the 1s time limit in contest was a bit tight and allowed for some annoying constant factor/ML issues that presumably caused all of these hacks, while if your intent was to require $$$O(nmr)$$$, it seems more reasonable to set e.g. $$$n \cdot m \le 10^5$$$ and $$$r \le 50.$$$
I guess the TL was increased because someone managed to make the author's solution TLE on the old TL.
This should not be a reason to extend time limits right? As long as someone was able to pass the time constraints smoothly, it is still solvable in 1s and should be considered a valid problem imo
Yes, I agree with you on this.
An Editorial-based solution passes the tests in 300 smth ms for me, the trick is to use bitwise operators in c++ when calculating the dp and then it works much faster
I believe that the authors should explain why the time limits are changed. I am guessing it is due to the test consisting of $$$10^6$$$ integers upto $$$10^9$$$, and as a side effect $$$O(nm(n+m+r))$$$ gets basically a free pass. I don't believe $$$O(nm(n+m+r))$$$ solutions are concerning enough to justify a drastic time limit change.
It is possible to squeeze $$$O(nm(n+m+r))$$$ solutions without too much efforts in the original constraints 208838975 (this is in Kotlin so it should be easy in C++) This is of course assuming "10000 1" is within the tests, and this cannot be done without taking a few TLE penalties. Even if all that fails, a simple modification to use bitsets suffices. (UPD: I missed a simple optimisation of not needing to make two dp arrays and copy as found in your solution. With that, the $$$O(nm(n+m+r))$$$ should pass very comfortably.)
Though considering how the test "10000 1" is completely missing from the tests, I feel like the authors did not consider the $$$O(nm(n+m+r))$$$ solution properly, let alone designing the TL accordingly.
During the contest, I thought a $$$nm(n+m+r)$$$ solution would be able to pass easily. I did not notice that in fact, it is $$$(n+1)(m+1)(n+m+r)$$$ and I would probably hesitate if I noticed that.
For the weaker claim, did you figure out how to prove formally? I am not sure how to.
No; I've spent some time thinking about it and still don't have a proof (though perhaps I'm missing something obvious). I'm hoping the authors post a corrected proof (or clarify the existing proof) before too long since this claim is obviously pretty central to solving the problem.
Problem G
What are the specific hacking rules for Codeforces? Percisely, should a solution be hacked for the seed of its random number generator? As far as I remember there are many solutions hacked this way, so why did you rejudge all submissions in G1 and G2?
So basically from problem B I understand the follwing. Suppose we have a number n, and let be 2^x the largest power of 2 which does not exceed x, so it's enough to have x bits to represent n. In this case, the total number of ways to set bits on such that n is not exceeded is n + 1. Is it correct?
Each number can be written as a bitmask. If we can "buy" a bitmask, that means its total cost is $$$\le n$$$. As every price is $$$2^k$$$, this total cost is just a number and can be achieved in only one way, so yes, you are correct
Could anyone please explain the solution of Problem B, I had hard time in understanding the solution of the editorial. Thanks in advance!
Tasting stuff here is like counting in binary where you can count using k-bits. we can simply count how many k-bit combinations are less than n (including all 0s).
ugly G :(
I have another similar approach for problem F.
$$$d = time[R] - currentTime + 1$$$
$$$visited[i][j] = 0, (i/j = fixed, j/i = varies)$$$
$$$currentTime = time[R] + 1$$$
Repeat Step 1 and Step 2 until $$$(N,M)$$$ cell is reached. $$$visited[N][M] = 1$$$
Time Complexity: $$$O(NMR)$$$
Space Complexity: $$$O(NM)$$$ (better than editorial solution)
Implementaion is easier and more intuitive idea than dp.
Code: 208794165
1729E - Guess the Cycle Size another interactive Div3 task which uses probabilities. similar to 1840G1 - In Search of Truth (Easy Version)
C, D, E were nice! Only if B was not so complicated, took me around 20 mins to understand+solve ;(
Can you tell me what is the error in my solution for E.
Can you give the submission link, if I'm not able to find out the error then maybe someone else can!
219706876
B took the most time from me I didn't get it fast :(
if u got it now can u explain me please, i am not able to get the editorial also
You just check what is the maximum number you can buy
if 2 pow k <= n you can buy n+1 elements from 0 to n
else the maximum you can buy is all elements from k
the number of ways is 2 pow k you can represent it in binary representation each element is 0 or 1
Hi Ahmed, please can you explain why they used
k = min(k, 30)? what is the meaning of using30?constrains are upto 1e9 and 1e9 has 30 bits in binary
to avoid integer overflow
For some reason, C is failing even though I implement the same logic. Can you please help me out?
https://mirror.codeforces.com/contest/1840/submission/208848852
You should just use long long instead of integers in the vectors
Anyone who solved F with recursive approach?
For pD, what does maximum prefix and suffix mean? How do you prove this to be the best?
I thought of using maybe a two-pointer approach to find which elements the carvers should handle,
but that didn't end well.
Ah, never mind. I understand it now. Surprised that I didn't think of binary search = =
I used a two-pointers approach without binary search, one for the right end of the prefix and one for the left end of the suffix. However, I was missing that I need to check only for the minimum between the updated prefix and suffix not the maximum between the 3 segments in each case (L+1 and R-1).
Wrong Submission: https://mirror.codeforces.com/contest/1840/submission/209091927
Accepted: https://mirror.codeforces.com/contest/1840/submission/209090257
Yeah I had pretty much the same idea and wrong observation like you. This pair with slow implementation really messed me up.
I hope I will reach an expert by the end of the final testing...
same
My congratulations !!!
The fourth question could've been framed in a better way I think. I though about it for 3-4 hours but couldn't think of a solution. The reason being that I thought that the time of different carvings by the same Carver have to be added. But we had to only take the maximum as each Carver can carve multiple toys at once. But this isn't clearly mentioned in the question. It's written that the carvers are skilled and can work at multiple people at once. It should've been written that one Carver can work at multiple carvings at once.
Im tripped this at first too. But I think the statement is quite clear and example made it more clear
During the preparation for the festival, the carvers will perfectly work out the technique of making the toy of the chosen pattern, which will allow them to cut it out of wood "instantly". To make a toy of pattern y for a carver who has chosen pattern x, it will take |x-y| time, because the more the toy resembles the one he can make "instantly", the faster the carver will cope with the work.Still imho many problem statements in contests use some hard and implied words that really hard to understand quickly for me, especially my english is not that good (but yeah that makes me improve better and better tho just need time for practice).
Can someone help spot mistake in my solution for E? I am getting wrong 52nd token in test 2 which I can't see, and I can't find bug after 3 hours. My approach was slightly different: I preprocessed the modifications and then after all of them I answered all the queries.__ https://mirror.codeforces.com/contest/1840/submission/208812489
Did you find it?
no
https://mirror.codeforces.com/contest/1840/submission/208865868 could someone help me find why i am getting WA? I cant find it.. :(
in your function where you are performing swap operation for query of type 2, in the second else if you are comparing op1 with both 1 and 2. Here is an accepted submission of your edited code https://mirror.codeforces.com/contest/1840/submission/208869321
In problem G2, the solution d=(1000-k)/2 should be sqrt(d)=(1000-k)/2
B was too complicated for a Div3 contest.Sure the solution can be written in a single line but it was not obvious at all.
UPD : Fixed
I have different approach to solve Problem D[problem:1840D] using Two pointer. we have to divide the sorted array into three parts, and maximum time for all three parts can be calculated in O(1) time. Here is my approach: 1. sort the array. 2. divide the array into three parts: part1 = (0,i-1), part2 = (i,j), part3 = (j+1,n-1). 3. calculate the time of all three parts, and store the maximum of them. 4. compare the time of 1(0,i) and 2(j,n-1) if 1>2 go to left (j--) else go to right (i++). — i is the left pointer and j is the right pointer and i starts from 1 and j starts from n-2. 5. print the minimum time.
very nice approach, but not so intutive btw
In F's editorial Code what does this line means?
To get to the position
(i, j)with k stops, it will takei + j + kseconds (since going vertically or horizontally by one unit takes 1 unit of time, and stopping takes one unit of time). The code snippet you gave is enforcing the principle that when a laser is fired horizontally, positions(coord, j)forjin[0, m]are not free at timet. Sot = coord + j + k, ergok = t - coord - jwhich is the expression in the third pair of brackets. Lastly we need to check thatkis in the interval[0, r]so that it is not out of bounds.Problem D really teaches a lot. Im new to this binary search on the answer. To somebody more experienced, could you please provide some problem which uses the same key concept?
CF Edu. https://mirror.codeforces.com/edu/courses
Really, Really, Really Nice problems
Could someone point out the problem in my submission for C ? I am getting wrong answer on test case 6.
208749011
I believe it is integer overflow. See this code snippet:
This would output
-727379968, since the intermediate resulty * yis an integer and exceeds the integer limit. Now see this code snippet:This correctly outputs
1000000000000, since it creates an intermediate result1LL * yof typelong longso1LL * y * yends up being along longtoo, rather than an integer.Hopefully this is enough to help fix your code now :)
In problem C, how did you get to C(l-k+2, l-k)?
The way I thought about it, is that if you have a section of length
land you want find the number of ways of choosing a subsection of lengthk<=x<=l, we can count up the ways of choosing subsections of all lengthsxin[k, l]and add them up. We can fully describe choosing a subsection of lengthxby where it begins. So we just need to add up the number of starting positions for the subsections. There arel-x+1different places that you can choose for the starting point (hopefully it shouldn't be too hard to convince yourself with some examples). So we end up adding(l-k+1) + (l-k) + (l-k-1) + ... + 1which you should recognise as triangular numbers starting from(l-k+1)i.e.(l-k+1)(l-k+2)/2which is the same as(l-k+2) choose 2or(l-k+2) choose (l-k). Maybe there's an easier way to understand it with combinatorics that somebody else can let us know, but this was my approach.What will be the solution if k would at most?
Can anyone help me if in problem D we call the number of carvers is k, and how to solve this problem if 1 <= k <= 200005, if it impossible to solve, what about 1 <= k <= 20
You can binary search on the answer. Here's the implementation: 208734553
Can someone help me to take a look at my Code for Problem E? I have been reviewing it for more than 1 hour and asked people around me, but I couldn't identify the issue.208958346
Both strings in type2 query can be same even if pos1==pos2.
So just remove this if statement.208961664
I am extremely grateful, you saved my life.
How would you solve E if the block operation were defined like this:
$$$ 1\ \ \ pos_1\ \ \ pos_2 $$$
Constraints:
$$$0 \le pos_1 \le |s_1|$$$
$$$0 \le pos_2 \le |s_2|$$$
$$$pos_i = 0$$$ meaning that there's no character to be blocked in $$$s_i$$$ on this operation.
Both strings may have different lengths.
Operation $$$3$$$ is guaranteed to be queried only when $$$|s_1| = |s_2|$$$ (ignoring blocked characters)
Examples:
Input:Output:Explanation:First case:
Second case:
Third case:
Actually,it can be solved easily with segment tree and hashing.
Check this submission for more details : https://mirror.codeforces.com/contest/1840/submission/208754257
Hi, can anyone spot the error in my submission for 1840E - Character Blocking -> 209220374
I tried to generate tests (although most of them had all NO's as output), but I couldn't find a case where my solution is failing :(
Take a look at Ticket 16872 from CF Stress for a counter example.
Thanks a lot man, was able to correct the error, really appreciate it. Really good website you made :)
Can anybody tell me where am I going wrong in problem E? submission — here
Seems a contest 3 weeks ago has been a ancient contest and nobody will care about it, but I still want to share my optimized BFS solution to problem F!
An instant thought is applying naive BFS running on $$$O(n\times m\times r)$$$ 3-dimensional space. It's no need to consider a railgun shot which is at a very late time.
But my time constant was high, for my unwise implementation with much unnecessary STL. Feeling too lazy to change my code greatly, I decided to try something to reduce my constant. In details, two optimization:
I used
set<tuple<int, int, int>>to record every point (x, y, time) to avoid repeating. But it was BFS, so when a(x, y, t + 1)occurred, all the records thattime = tturned useless. So aset<pair<int, int>>could be reuse again and again, reducing the size of the set greatly. Of course you can apply this on the 3-d bool array to reduce you memory cost.A well-known trick to boost BFS is A-star, and I designed a method to cut down the number of points in queue that familiar with A-star. If we have a nearest point (x, y) to the destination, taking railgun into consideration, we need no more than $$$d=n + m - x - y + r$$$ steps. For any point whose $$$n+m-x-y$$$ exceed the $$$d$$$, we just drop it.
In my (suck) implementation, both optimization are essential, or it gets TLE.
You may think it unnecessary to share such trivial things. Well, I just want to share my enjoyment of solving problems. Have a nice day. :)
Nice contest
f can use bitset to brute force dp
There is a typo in the analysis of the G2 problem — the expression d=(1000-k)/2 should be as follows sqrt(d)=(1000−k)/2.
What dose it mean k = min (k , 30) If you have the time, give an in-depth explanation.
I greatly appreciate your help.<3
N can be maximum 1e9 thus you can't buy the 31th item which costs 2^30 = 1073741824.
I have a more intuitive solution for D. We basically binary search for x, where x is minimum possible wait time. Suppose I need to check if task can be done in x time or not: Greedily its best to assign a=v[0]+x; then we find the first v[i] for which abs(v[i]-a)>x; now assign b=v[i]+x; and do the same for c; do this obviously after sorting the array.
In E, I am getting TLE. I am using hash functions to determine whether the current strings are equal. How can I optimize it to pass the time limit? Please, anyone!
This is my code : [submission:https://mirror.codeforces.com/contest/1840/submission/277553096]
Notice that the edutorial's G1 solution is similar to "baby-step giant-step" algorithm for computing the discrete logarithm.