-
Notifications
You must be signed in to change notification settings - Fork 0
/
cslog.html
1731 lines (1707 loc) · 63 KB
/
cslog.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8" />
<meta name="HandheldFriendly" content="true" />
<meta name="MobileOptimized" content="320" />
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Computer Science Log -- Be kind for 2020 (bkf2020)'s Website!</title>
<link rel="stylesheet" href="style.css">
</head>
<body>
<header>
<h1>Be kind for 2020 (bkf2020)'s Computer science log</h1>
<p>
<a href="/">home</a>
</p>
</header>
<article>
<h2>What is this?</h1>
<p>
These are computer science problems I am trying out this week.
I'll include notes. My goal is to seriously attempt/solve at least ALL
of the problems (as of Jan 02, 2022). This starts the week of Jan 03, 2022
to Jan 09, 2022. It's okay if I don't solve all the problems.
</p>
<p>
Possible status for each problem:
<mark class="ns">Not started</mark>,
<mark class="s">Started</mark>,
<mark class="sa">Attempted Seriously</mark>,
<mark class="so">Solved</mark>
</p>
<!-- Template
<details>
<summary>Click to show table</summary>
<table>
<tr>
<th>Problem Link</th>
<th>Status</th>
<th>Additional Notes</th>
</tr>
<tr>
<th><a href=""></a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href=""></a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href=""></a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href=""></a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href=""></a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href=""></a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
</table>
</details>
-->
<h2>Week of May 09, 2022 - May 15, 2022</h2>
<details>
<summary>Click to show table</summary>
<table>
<tr>
<th>Problem Link</th>
<th>Status</th>
<th>Additional Notes</th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1209">Feb 2022 USACO Gold Redistributing Gifts</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1210">Feb 2022 USACO Gold Cow Camp</a></th>
<th class="so">Solved</th>
<th>
Did not have the idea of "jumping" through the DP like in the solution.
</th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1211">Feb 2022 USACO Gold Moo Network</a></th>
<th class="s">Started</th>
<th>
Tried sorting the cows by the x-coordinate and then by the y-coordinate.
Then, I added possible edges between every 3 cows, and also connected all the groups.
This method did not work.
</th>
</tr>
</table>
</details>
<h2>Week of May 02, 2022 - May 08, 2022</h2>
<details>
<summary>Click to show table</summary>
<table>
<tr>
<th>Problem Link</th>
<th>Status</th>
<th>Additional Notes</th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1161">2021 USACO Dec Gold Paired Up</a></th>
<th class="so">Solved</th>
<th>
<p>
First, I read the first sentence of
<a href="http://usaco.org/current/data/sol_prob1_gold_dec21.html">the solution</a>
to get a hint on how to solve this problem.
<q>
Let's call two adjacent cows "linked" if they are able
to pair up with each other. We can split the cows up into
chains where each pair of adjacent cows in a chain are linked,
and no two cows in different chains are linked.
</q>
</p>
<p>
Using this idea, I was able to solve the T = 1 case correctly,
and my solution the T = 2 case was pretty similar to the solution.
However, it was wrong and more complicated. After reading the solution,
I understood that if there are an ODD number of cows already unpaired, and
you leave an unpaired cow <var>i</var> at an EVEN index,
then you must pair up cows <var>i - 1</var> and <var>i + 1</var>. If there are an
ODD number of cows already unpaired and you leave an unpaired cow at an ODD index,
you must pair up an even number of adjacent cows (0 is fine).
</p>
<p>
Similarly, I understood that if there are an EVEN number of cows already unpaired, and
you leave an unpaired cow <var>i</var> at an ODD index,
then you must pair up cows <var>i - 1</var> and <var>i + 1</var>. If there are an
EVEN number of cows already unpaired and you leave an unpaired EVEN at an even index,
you must pair up an even number of adjacent cows (0 is fine).
</p>
<p>
This approach lets you transition <code>dp[i][j] = dp[i + 1][j]</code> instead of
<code>dp[i][j] = dp[i + 2][j]</code> (which is what I did in my original solution).
</p>
<p>
If the current number of cows already unpaired DOES NOT have the SAME PARITY of
the total number of cows in a link, then we MUST be able to pair up addition
cows. Otherwise, we don't consider it.
</p>
</th>
</tr>
</table>
</details>
<h2>Week of Apr 25, 2022 - May 01, 2022</h2>
<details>
<summary>Click to show table</summary>
<table>
<tr>
<th>Problem Link</th>
<th>Status</th>
<th>Additional Notes</th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1162">2021 USACO Dec Gold HILO</a></th>
<th class="so">Solved</th>
<th>
Solved using 3 segment trees: one
which stores the indices i with
i > x + 0.5, one which stores
the remaining indices not in the
original array, and one which
stores if there is a HI before
a certain LO. I used tags for lazy
propagation, and I found that
if I wanted to set a section of
a segment tree to zero, it wouldn't
work because I wanted the tags
to be GREATER than zero. Fixed
by making the tags default to -1.
</th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1161">2021 USACO Dec Gold Paired Up</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
</table>
</details>
<h2>Week of Apr 18, 2022 - Apr 24, 2022</h2>
<details>
<summary>Click to show table</summary>
<table>
<tr>
<th>Problem Link</th>
<th>Status</th>
<th>Additional Notes</th>
</tr>
<tr>
<th><a href="https://codeforces.com/problemset/problem/1641/B">Codeforces Repetitions Decoding</a></th>
<th class="so">Solved</th>
<th>
Once I found out I could "reverse" part of the array, I figured out a solution
that grouped together the same numbers.
</th>
</tr>
</table>
</details>
<h2>Week of Apr 11, 2022 - Apr 17, 2022</h2>
<details>
<summary>Click to show table</summary>
<table>
<tr>
<th>Problem Link</th>
<th>Status</th>
<th>Additional Notes</th>
</tr>
<tr>
<th><a href="https://codeforces.com/problemset/problem/1641/B">Codeforces Repetitions Decoding</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href="https://codeforces.com/problemset/problem/1634/D">Codeforces Finding Zero</a></th>
<th class="so">Solved</th>
<th>
I noticed that by checking 4 numbers, with 4 queries, you can determine at most two
possible positions that can be zero. Using this idea, we can break down n possible numbers
into <code>2 * floor(n / 4) + n mod 4</code> possible numbers and so on...
Missed a lot of cases with a messy implementation, so it took a couple tries to get AC.
</th>
</tr>
</table>
</details>
<h2>Week of Apr 04, 2022 - Apr 10, 2022</h2>
<details>
<summary>Click to show table</summary>
<table>
<tr>
<th>Problem Link</th>
<th>Status</th>
<th>Additional Notes</th>
</tr>
<tr>
<th><a href="https://codeforces.com/problemset/problem/1646/D">Codeforces Weight The Tree</a></th>
<th class="so">Solved</th>
<th>
<p>
My idea is to try to weight all nodes that are currently
unweighted and are only connected to zero or one other
unweighted nodes. This is done by setting those nodes to the sum
of their already weighted neighbors, and setting the ONE node they
are connected to to weight one (if it exists).
If there is a component with ONLY two unweighted nodes connected,
then we should consider the two possible ways to weight one of the
nodes as 1. However, this does not guarantee the minimal
possible sum of weights. Not sure what is wrong yet.
</p>
<p>
Found a failing test case using <a href="https://cfstress.com/">CF Stress</a>.
I ended up using the editorial to figure out what I was missing.
I basically got the observation that all bad nodes should be set to one,
and all good nodes are a sum of their neighbors, but didn't use
this to motivate a tree-dp.
</p>
</th>
</tr>
<tr>
<th><a href="https://codeforces.com/problemset/problem/1641/B">Codeforces Repetitions Decoding</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href="https://codeforces.com/problemset/problem/1634/D">Codeforces Finding Zero</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
</table>
</details>
<h2>Week of Mar 28, 2022 - Apr 03, 2022</h2>
<details>
<summary>Click to show table</summary>
<table>
<tr>
<th>Problem Link</th>
<th>Status</th>
<th>Additional Notes</th>
</tr>
<tr>
<th><a href="https://codeforces.com/problemset/problem/1646/D">Codeforces Weight The Tree</a></th>
<th class="sa">Seriously attempted</th>
<th>
My idea is to try to weight all nodes that are currently
unweighted and are only connected to zero or one other
unweighted nodes. This is done by setting those nodes to the sum
of their already weighted neighbors, and setting the ONE node they
are connected to to weight one (if it exists).
If there is a component with ONLY two unweighted nodes connected,
then we should consider the two possible ways to weight one of the
nodes as 1. However, this does not guarantee the minimal
possible sum of weights. Not sure what is wrong yet.
</th>
</tr>
<tr>
<th><a href="https://codeforces.com/problemset/problem/1641/B">Codeforces Repetitions Decoding</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href="https://codeforces.com/problemset/problem/1634/D">Codeforces Finding Zero</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
</table>
</details>
<h2>Week of Mar 07, 2022 - Mar 13, 2022</h2>
<details>
<summary>Click to show table</summary>
<table>
<tr>
<th>Problem Link</th>
<th>Status</th>
<th>Additional Notes</th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1067">2020 USACO December Gold Problem 3 Square Pasture</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1066">2020 USACO December Gold Problem 2 Bovine Genetics</a></th>
<th class="s">Started</th>
<th>
Tried thinking of it, but can't come up with a solution. Decided to add Feb 2021 Gold
because they are easier and maybe more of my level.
</th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1113">2021 USACO Feb Gold Problem 1 Stone Game</a></th>
<th class="s">Started</th>
<th>
Let M be the max value of all a_i. Let <code>gte[j]</code> be the number
of values in a_i greater than or equal to j.
Then, for all values j between floor(M / 2) + 1 to M, I believe if
<code>gte[j]</code> is odd, then this value of j can be used on the first move.
I'm tried dealing with values of j from 1 to floor(M / 2), but no progress yet.
</th>
</tr>
</table>
</details>
<h2>Week of Feb 28, 2022 - Mar 06, 2022</h2>
<p>Sorry that I didn't make any progress this week.</p>
<details>
<summary>Click to show table</summary>
<table>
<tr>
<th>Problem Link</th>
<th>Status</th>
<th>Additional Notes</th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1067">2020 USACO December Gold Problem 3 Square Pasture</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1066">2020 USACO December Gold Problem 2 Bovine Genetics</a></th>
<th class="s">Started</th>
<th>
Tried thinking of it, but can't come up with a solution. Decided to add Feb 2021 Gold
because they are easier and maybe more of my level.
</th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1113">2021 USACO Feb Gold Problem 1 Stone Game</a></th>
<th class="s">Started</th>
<th>
Let M be the max value of all a_i. Let <code>gte[j]</code> be the number
of values in a_i greater than or equal to j.
Then, for all values j between floor(M / 2) + 1 to M, I believe if
<code>gte[j]</code> is odd, then this value of j can be used on the first move.
I'm tried dealing with values of j from 1 to floor(M / 2), but no progress yet.
</th>
</tr>
</table>
</details>
<h2>Week of Feb 21, 2022 - Feb 27, 2022</h2>
<details>
<summary>Click to show table</summary>
<table>
<tr>
<th>Problem Link</th>
<th>Status</th>
<th>Additional Notes</th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1065">2020 USACO December Gold Problem 1 Replication</a></th>
<th class="s">Started</th>
<th>
I have the idea of floodfill, but when robots
replicate, I'm not sure how to expand the floodfill.
Also, with the possibility of D not being 1, it is
harder to update the floodfill. I tried thinking of
brute force, but it's difficult to implement cleanly.
</th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1066">2020 USACO December Gold Problem 2 Bovine Genetics</a></th>
<th class="s">Started</th>
<th>
Tried thinking of it, but can't come up with a solution. Decided to add Feb 2021 Gold
because they are easier and maybe more of my level.
</th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1067">2020 USACO December Gold Problem 3 Square Pasture</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1113">2021 USACO Feb Gold Problem 1 Stone Game</a></th>
<th class="s">Started</th>
<th>
Let M be the max value of all a_i. Let <code>gte[j]</code> be the number
of values in a_i greater than or equal to j.
Then, for all values j between floor(M / 2) + 1 to M, I believe if
<code>gte[j]</code> is odd, then this value of j can be used on the first move.
I'm tried dealing with values of j from 1 to floor(M / 2), but no progress yet.
</th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1114">2021 USACO Feb Gold Problem 2 Modern Art 3</a></th>
<th class="so">Solved</th>
<th>
I defined <code>dp[i][j]</code> to be the cost of choosing
between the range i to j (inclusive). But, I didn't think
my dp equation was optimal yesterday, but after running through a few
cases today, I realized it was infact optimal.
</th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1115">2021 USACO Feb Gold Problem 3 Count the Cows</a></th>
<th class="so">Solved</th>
<th>
<p>
Let X represent how the pasture looks for 0 ≤ x, y ≤ 3<sup>n</sup> for some <var>n</var>.
Let O represent an empty pasture for 0 ≤ x, y ≤ 3<sup>n</sup> for the same <var>n</var>.
Then the pasture for 0 ≤ x, y ≤ 3<sup>n + 1</sup> looks like this:
</p>
<pre><code>XOX
OXO
XOX</code></pre>
<p>
n = 2 may suggest this idea, but I got this idea from writing a simple script to visualize the pattern.
I had the idea of doing this, because there must be some kind of pattern if you want to solve
this problem efficiently. I believe this is NOT against the USACO rules, so I can do this during a contest.
<u>I DID NOT SOLVE THIS PROBLEM DURING AN OFFICIAL CONTEST</u>.
</p>
<p>
<a href="https://codeberg.org/bkf2020/pages/src/branch/main/cpp/count_visual.cpp">
Code for the script</a>
</p>
<p>
After I wrote the script, I came up with the following idea:
Let <code>num_cows(x, y, d)</code>
count the number of cows from (x, y) to (x + d, y + d).
</p>
<p>
Then, we can enclose all such cows within a
3<sup>n</sup> by 3<sup>n</sup> grid. We
can find n using binary search.
</p>
<p>
As mentioned earlier, we can split the
3<sup>n</sup> by 3<sup>n</sup> grid into
smaller
3<sup>n - 1</sup> by 3<sup>n - 1</sup> grids,
and we can find the places the diagonal intersects
these grids.
</p>
<p>
Thus, we split up the original problem into
many smaller problems.
</p>
<p>
This is a rough outline, but my implemenation
was quit messy. It gets accepted but is
borderline TLE.
</p>
<a href="https://codeberg.org/bkf2020/pages/src/branch/main/cpp/count.cpp">
View the Code</a>
</p>
</th>
</tr>
</table>
</details>
<h2>Week of Feb 14, 2022 - Feb 20, 2022</h2>
<p>Note: sorry for making no progress for 2 weeks. Will try harder this week</p>
<details>
<summary>Click to show table</summary>
<table>
<tr>
<th>Problem Link</th>
<th>Status</th>
<th>Additional Notes</th>
<tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1185">USACO 2022 January Gold Drought</a></th>
<th class="sa">Seriously attempted</th>
<th>
<p>
I only can solve this problem if N is even.
</p>
<p>
To do this, I let <code>dp[i][a]</code> be the number of ordered tuples
<code>(h[i], ..., h[N])</code> from cows i to N with <code>h[i] ≥ a</code>.
</p>
<p>
Then, it is easy to get the values for <code>dp[N - 2][a]</code> (2 cow case).
After that I loop through values of <code>i</code> from <code>N - 4</code> to <code>0</code>
(decreasing by 2 each time), and for each value of <code>i</code>,
I loop through values of <code>a</code> from <code>H[i]</code> to <code>0</code>
(decreasing by 1 each time). I set <code>dp[i][a] = dp[i][a + 1]</code>
The cow at <code>i + 1</code> has a value <code>b</code> and for each value of <code>a</code>,
I loop through values of <code>b</code> from <code>a</code> to <code>H[i + 1]</code>.
For each value of <code>b</code>, I update
<code>dp[i][a] += dp[i + 2][0] - dp[i + 2][max(H[i + 2] - b + a + 1, 0)]</code>.
</p>
<p>
What we do here is make cows <code>i + 1</code> and <code>i + 2</code> equal to <code>a</code>
by subtracting <code>b - a</code> from them. Thus, cow <code>i + 2</code> can be at most
<code>H[i + 2] - b + a</code>. If <code>H[i + 2] - b + a + 1</code> is negative, I just use 0 instead.
</p>
<p>
The mistake I made was that <code>dp[i][a]</code> could be negative because of the mod. (I found out
with the USACO test data.) Thus, I need to do <code>dp[i][a] += MOD</code> to combat this issue.
</p>
<p>
I only pass the sample input if N is odd.
</p>
</th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1186">USACO 2022 January Gold Farm Updates</a></th>
<th class="s">Started</th>
<th>
Came up with a <code>O(N^2)</code> solution that for each query,
calculates the number of active barns you can visit from each barn
using DFS, then finds the barns that are not relevant, and computes
the answers for those barns.
</th>
</tr>
</table>
</details>
<h2>Week of Feb 07, 2022 - Feb 13, 2022</h2>
<p>Note: I have problems to do for a computer science class, and also school work, so I may have less time...</p>
<details>
<summary>Click to show table</summary>
<table>
<tr>
<th>Problem Link</th>
<th>Status</th>
<th>Additional Notes</th>
<tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1185">USACO 2022 January Gold Drought</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1186">USACO 2022 January Gold Farm Updates</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
</table>
</details>
<h2>Week of Jan 31, 2022 - Feb 06, 2022</h2>
<p>Didn't spend much time working on computer science...</p>
<h2>Week of Jan 24, 2022 - Jan 30, 2022</h2>
<p>Note: I have problems to do for a computer science class, and so school work, so I may have less time...</p>
<details>
<summary>Click to show table</summary>
<table>
<tr>
<th>Problem Link</th>
<th>Status</th>
<th>Additional Notes</th>
<tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1065">2020 USACO December Gold Problem 1 Replication</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1066">2020 USACO December Gold Problem 2 Bovine Genetics</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1067">2020 USACO December Gold Problem 3 Square Pasture</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
</table>
</details>
<h2>Week of Jan 17, 2022 - Jan 23, 2022</h2>
<details>
<summary>Click to show table</summary>
<table>
<tr>
<th>Problem Link</th>
<th>Status</th>
<th>Additional Notes</th>
<tr>
<tr>
<th><a href="https://cses.fi/problemset/task/1651">CSES Range Update Queries</a></th>
<th class="ns">Not started</th>
<th>
Solve if there is time. Read on BIT and Segment Tree.
</th>
</tr>
<tr>
<th><a href="https://cses.fi/problemset/task/1734">CSES Distinct Values Queries</a></th>
<th class="ns">Not started</th>
<th>
Solve if there is time. Read on BIT and Segment Tree.
</th>
</tr>
<tr>
<th><a href="https://open.kattis.com/problems/robotturtles">Kattis Robot Turtles</a></th>
<th class="so">Solved</th>
<th></th>
</tr>
<tr>
<th><a href="http://www.usaco.org/index.php?page=viewproblem2&cpid=245">USACO Tractor (2013 Feb Silver)</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href="http://www.usaco.org/index.php?page=viewproblem2&cpid=669">USACO Moocast (2016 Dec Silver)</a></th>
<th class="so">Solved</th>
<th>
I binary searched on the value of X,
and used DSU to merge the components of
two points, if the distance between
the two points ≤ sqrt(X).
The problem was that I checked
the size of the component of 0, but the
root of the DSU doesn't have to be 0.
</th>
</tr>
</table>
</details>
<h2>Week of Jan 10, 2022 - Jan 16, 2022</h2>
<p>
I have to finish some homework for a computer science class.
I will try to finish that, and will assign problems if there
is time.
</p>
<p>
<b>Update:</b> Will assign problems for now.
</p>
<details>
<summary>Click to show table</summary>
<table>
<tr>
<th>Problem Link</th>
<th>Status</th>
<th>Additional Notes</th>
</tr>
<tr>
<th><a href="https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=944">Online Judge 10003 Cutting Sticks</a></th>
<th class="so">Solved</th>
<th>
<details>
<summary>My solution</summary>
First, sort the cuts and let the cuts in the input
be <code>cuts[1], cuts[2], ..., cuts[n]</code>.
Define <code>cuts[0] = 0</code> and <code>cuts[n + 1] = L</code>.
I defined <code>cost[i][j]</code> to be the cost
of placing the cuts between i and j (inclusive) between
<code>cuts[i - 1]</code> and <code>cuts[j + 1]</code>.
Then <code>cost[i][j] = min(cuts[j + 1] - cuts[i - 1] + cost[i][k - 1] + cost[k + 1][j])</code>
for all possible k. (If <code>k - 1 < i</code> or <code>k + 1 > i</code>, ignore it.)
</details>
However, this solution got wrong answer.
<p>
<u>Update:</u> After talking to another person, I redefined <code>cost[i][j]</code>
to be the cost of performing all cuts between positions
<code>cuts[i]</code> and <code>cuts[j]</code> on the piece of wood.
This caused the transition equation to become
<code>cost[i][j] = min(cuts[j] - cuts[i] + cost[i][k] + cost[k][j])</code>
for all possible k.
</p>
</th>
</tr>
<tr>
<th><a href="http://www.usaco.org/index.php?page=viewproblem2&cpid=839">USACO Talent Show</a></th>
<th class="sa">Seriously Attempted</th>
<th>
<p>
My first solution was to greedily add the cows with the highest ratios,
but I think it doesn't work because adding a cow with a lower ratio and lower weight
might result in a higher overall ratio. As a result, I used
<a href="http://www.usaco.org/current/data/sol_talent_gold_open18.html">
the USACO solution</a>, but I don't understand why <code>dp[k1]</code>
will always have the optimal value, because <code>dp[k]</code> can be updated
and it doesn't guarantee <code>dp[k1]</code> gets updated.
I believe if <code>dp[k]</code> can get updated by a cow with weight w,
<code>dp[k1]</code> can get updated for the same cow with weight w by using
<code>dp[k1 - w]</code> (or <code>dp[W]</code> if k1 = W).
</p>
<p>
<u>Update:</u> After talking to another person, I realized that
<code>dp[k1]</code> shouldn't get updated by the same cow that
<code>dp[k]</code> gets updated by. Still need to finish implementing this problem.
</p>
</th>
</tr>
<tr>
<th><a href="https://csacademy.com/contest/archive/task/mountain-time">CS Academy Mountain Time</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href="http://www.usaco.org/index.php?page=viewproblem2&cpid=671">USACO Lasers and Mirrors</a></th>
<th class="so">Solved</th>
<th>
Wrote a complicated solution. See <a href="https://codeberg.org/bkf2020/pages/src/branch/main/cpp/lasers.cpp">
the file</a>.
The mistakes I made were not including lines
25 and 26:
<p>
<code>
points.push_back({xl, yl});
points.push_back({xb, yb});
</code>
</p>
and on line 49 where I used <code>N</code>
instead of <code>points.size();</code>
</th>
</tr>
<tr>
<th><a href="http://www.usaco.org/index.php?page=viewproblem2&cpid=899">USACO Shortcut</a></th>
<th class="so">Solved</th>
<th>
My original solution stored the shortest path
from the barn to each vertex in a vector.
This was too inefficient, and I fixed it by storing
the next node in the optimal path of each node.
This is similar to <a href="http://www.usaco.org/current/data/sol_shortcut_gold_jan19.html">
the <code>O(Mlog N + N^2)</code> solution on USACO</a>.
</th>
</tr>
<tr>
<th><a href="http://www.usaco.org/index.php?page=viewproblem2&cpid=384">USACO Ski Course Rating</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
</table>
</table>
</table>
</details>
<h2>Week of Jan 03, 2022 - Jan 09, 2022</h2>
<details>
<p>
<b>Reflection:</b>
I think the problems I chose this week were too hard.
I will try to do easier problems, and also not cram
everything onto one weekend. I will look back on these
problems, but probably in a month or so, since I don't
understand enough to solve them.
</p>
<summary>Click to show table</summary>
<table>
<tr>
<th>Problem Link</th>
<th>Status</th>
<th>Additional Notes</th>
</tr>
<tr>
<th><a href="https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=944">Online Judge 10003 Cutting Sticks</a></th>
<th class="sa">Seriously attempted</th>
<th>
<details>
<summary>My solution</summary>
First, sort the cuts and let the cuts in the input
be <code>cuts[1], cuts[2], ..., cuts[n]</code>.
Define <code>cuts[0] = 0</code> and <code>cuts[n + 1] = L</code>.
I defined <code>cost[i][j]</code> to be the cost
of placing the cuts between i and j (inclusive) between
<code>cuts[i - 1]</code> and <code>cuts[j + 1]</code>.
Then <code>cost[i][j] = min(cuts[j + 1] - cuts[i - 1] + cost[i][k - 1] + cost[k + 1][j]</code>
for all possible k. (If <code>k - 1 < i</code> or <code>k + 1 > i</code>, ignore it.)
</details>
However, this solution got wrong answer.
</th>
</tr>
<tr>
<th><a href="http://www.usaco.org/index.php?page=viewproblem2&cpid=839">USACO Talent Show</a></th>
<th class="sa">Seriously Attempted</th>
<th>
EDIT: may try to understand this week.
My first solution was to greedily add the cows with the highest ratios,
but I think it doesn't work because adding a cow with a lower ratio and lower weight
might result in a higher overall ratio. As a result, I used
<a href="http://www.usaco.org/current/data/sol_talent_gold_open18.html">
the USACO solution</a>, but I don't understand why <code>dp[k1]</code>
will always have the optimal value, because <code>dp[k]</code> can be updated
and it doesn't guarantee <code>dp[k1]</code> gets updated.
I believe if <code>dp[k]</code> can get updated by a cow with weight w,
<code>dp[k1]</code> can get updated for the same cow with weight w by using
<code>dp[k1 - w]</code> (or <code>dp[W]</code> if k1 = W).
</th>
</tr>
<tr>
<th><a href="http://www.usaco.org/index.php?page=viewproblem2&cpid=384">USACO Ski Course Rating</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href="https://oj.uz/problem/view/JOI18_commuter_pass">JOI 2018 Commuter Pass</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href="http://www.usaco.org/index.php?page=viewproblem2&cpid=971">USACO Moortal Cowmbat</a></th>
<th class="sa">Seriously Attempted</th>
<th>
Took a while to come up with a solution for this problem.
First, I use Floyd-Warshall to find the minimum cost to change
from button i to button j. Then, I found the minimum cost
of changing the first i buttons in the combo to a letter j.
After that, I let <code>dp[i]</code> be the minimum cost for the first
i letters. The equation was
<code>dp[i] = min(dp[i - K] + cost, dp[i - K - 1] + cost, dp[i - K - 2] + cost, ...)</code>.
Here, <code>cost</code> represents the cost to change the last letters.
This is O(NK) and is therefore too slow.
</th>
</tr>
</table>
</details>
<h2>Week of Dec 27, 2021 - Jan 02, 2022</h2>
<details>
<summary>Click to show table</summary>
<table>
<tr>
<th>Problem Link</th>
<th>Status</th>
<th>Additional Notes</th>
<tr>
<tr>
<th><a href="https://oj.uz/problem/view/NOI18_knapsack">NOI 18 Knapsack</a></th>
<th class="so">Solved</th>
<th>
<a href="https://usaco.guide/problems/noi-knapsack/solution">
Used the USACO Guide solution for this problem</a>.
Couldn't think of anything efficient, because I focused on the bonds of K
instead of the bonds on S.
</th>
</tr>
<tr>
<th><a href="http://www.usaco.org/index.php?page=viewproblem2&cpid=897">USACO Cow Poetry</a></th>
<th class="so">Solved</th>
<th>
See my code <a href="https://codeberg.org/bkf2020/pages/raw/branch/main/cpp/poetry.cpp">here</a>.
I made the mistake of making <code>ways_group</code> too small. The size of that should be M.
I also used <code>unordered_map</code> and <code>unordered_set</code> because of the solution,
but I don't think it had that big of an impact. Originally, I did a O(NM) solution by updating
<code>ways_group</code> for every possible group size, and that TLE'd, but I think there was
a constant factor from <code>modpow</code> that made it too slow.
</th>
</tr>
<tr>
<th><a href="https://cses.fi/problemset/task/1639">CSES Edit Distance</a></th>
<th class="so">Solved</th>
<th>
<a href="https://codeforces.com/blog/entry/70018">Had to use the editorial</a>.
I didn't have any idea where to start originally.
When I tried implementing the editorial solution, I messed up
by leaving <code>dp[i][0]</code> undefined for i ≥ 1.
</th>
</tr>
<tr>
<th><a href="https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=944">Online Judge 10003 Cutting Sticks</a></th>
<th class="sa">Seriously attempted</th>
<th>
<details>
<summary>My solution</summary>
First, sort the cuts and let the cuts in the input
be <code>cuts[1], cuts[2], ..., cuts[n]</code>.
Define <code>cuts[0] = 0</code> and <code>cuts[n + 1] = L</code>.
I defined <code>cost[i][j]</code> to be the cost
of placing the cuts between i and j (inclusive) between
<code>cuts[i - 1]</code> and <code>cuts[j + 1]</code>.
Then <code>cost[i][j] = min(cuts[j + 1] - cuts[i - 1] + cost[i][k - 1] + cost[k + 1][j]</code>
for all possible k. (If <code>k - 1 < i</code> or <code>k + 1 > i</code>, ignore it.)
</details>
However, this solution got wrong answer.
</th>
</tr>
<tr>
<th><a href="http://www.usaco.org/index.php?page=viewproblem2&cpid=839">USACO Talent Show</a></th>
<th class="sa">Seriously Attempted</th>
<th>
EDIT: may try to understand this week.
My first solution was to greedily add the cows with the highest ratios,
but I think it doesn't work because adding a cow with a lower ratio and lower weight
might result in a higher overall ratio. As a result, I used
<a href="http://www.usaco.org/current/data/sol_talent_gold_open18.html">
the USACO solution</a>, but I don't understand why <code>dp[k1]</code>
will always have the optimal value, because <code>dp[k]</code> can be updated
and it doesn't guarantee <code>dp[k1]</code> gets updated.
I believe if <code>dp[k]</code> can get updated by a cow with weight w,
<code>dp[k1]</code> can get updated for the same cow with weight w by using
<code>dp[k1 - w]</code> (or <code>dp[W]</code> if k1 = W).
</th>
</tr>
<tr>
<th><a href="http://www.usaco.org/index.php?page=viewproblem2&cpid=789">USACO MooTube</a></th>
<th class="so">Solved</th>
<th>
Should <a href="https://usaco.guide/gold/dsu?lang=cpp">read about DSU</a> before attempting.
<a href="https://cp-algorithms.com/data_structures/disjoint_set_union.html">Another good DSU resource</a>.
For this problem, I <a href="http://www.usaco.org/current/data/sol_mootube_gold_jan18.html">used the solution</a>.
I had the idea of sorting the queries by largest weights (probably because I had done this problem before),
but I didn't think to sort the edges, and this prevented me from solving the problem.
</th>
</tr>
<tr>
<th><a href="http://www.usaco.org/index.php?page=viewproblem2&cpid=992">USACO Wormhole Sort</a></th>
<th class="so">Solved</th>
<th>
<a href="https://usaco.guide/problems/usaco-992-wormhole-sort/solution#solution-3---dsuuf">
Used this solution on USACO guide</a>.
The DSU solution I thought of was adding an edge, and then checking if
every node has the same parent. However, the correct solution is to
go through each node <code>i</code> and its parent <code>p[i]</code>
and add edges until both have the same parent.
Additionally, I made cycles which are formed by connecting <code>i</code>
to <code>p[i]</code>, but it is not needed to check every node in a cycle
having the same parent.
Will need to do more dsu problems this week (if possible) or next week.
</th>
</tr>
<tr>
<th><a href="http://www.usaco.org/index.php?page=viewproblem2&cpid=384">USACO Ski Course Rating</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href="https://cses.fi/problemset/task/2101/">CSES New Road Queries</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href="https://cses.fi/problemset/task/1202">CSES Investigation</a></th>
<th class="so">Solved</th>
<th>
Should <a href="https://usaco.guide/gold/shortest-paths?lang=cpp">read about shortest paths</a> before attempting.
At first, I didn't think abou the problem seriously, so I took a quick look
at the <a href="https://usaco.guide/problems/cses-1202-investigation/solution">USACO guide solution</a>
and realized to use Dijsktra. I likely would have realized this as well, if I seriously thought of the problem.
I got wrong answer on my first submission because I didn't read that the flights are ONE-WAY.
</th>
</tr>
<tr>
<th><a href="https://oj.uz/problem/view/JOI18_commuter_pass">JOI 2018 Commuter Pass</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href="https://oj.uz/problem/view/JOI21_ho_t4">JOI 2021 Robot</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>