codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1731.md (3085B)


      1 Source: https://codeforces.com/blog/entry/110630
      2 
      3 **UPD**: Code links are working now
      4 
      5 [1731A - Joey Takes Money](/contest/1731/problem/A "Codeforces Round 841 (Div. 2) and Divide by Zero 2022")
      6 
      7 Idea: [s_jaskaran_s](/profile/s_jaskaran_s "Candidate Master s_jaskaran_s")
      8 
      9 **Hint**
     10 
     11 What is the maximum value of $a + b$ when $a \cdot b = x$?
     12 
     13 **Solution**
     14 
     15 Tutorial is loading...
     16 
     17 **Code**
     18 
     19 [186975476](/contest/1731/submission/186975476 "Submission 186975476 by adedalic")
     20 
     21 [1731B - Kill Demodogs](/contest/1731/problem/B "Codeforces Round 841 (Div. 2) and Divide by Zero 2022")
     22 
     23 Idea: [s_jaskaran_s](/profile/s_jaskaran_s "Candidate Master s_jaskaran_s")
     24 
     25 **Hint**
     26 
     27 Check which direction is optimal for the next 2 steps and why?
     28 
     29 * 2 times Right?
     30 * 2 times Down?
     31 * 1 time Right and 1 time Down?
     32 * 1 time Down 1 time Right?
     33 
     34 **Solution**
     35 
     36 Tutorial is loading...
     37 
     38 **Code**
     39 
     40 [186975620](/contest/1731/submission/186975620 "Submission 186975620 by adedalic")
     41 
     42 [1731C - Even Subarrays](/contest/1731/problem/C "Codeforces Round 841 (Div. 2) and Divide by Zero 2022")
     43 
     44 Idea: [ka_tri](/profile/ka_tri "Candidate Master ka_tri")
     45 
     46 **Hint 1**
     47 
     48 What are the numbers with the odd number of divisors?
     49 
     50 **Hint 2**
     51 
     52 How many numbers with the odd number of divisors can be there in the range $2 \cdot 10^5$?
     53 
     54 **Hint 3**
     55 
     56 Try using prefix $\operatorname{XOR}$, iterating through all such numbers.
     57 
     58 **Solution**
     59 
     60 Tutorial is loading...
     61 
     62 **Code(C++)**
     63 
     64 [186975655](/contest/1731/submission/186975655 "Submission 186975655 by adedalic")
     65 
     66 **Code(Python)**
     67 
     68 [186975680](/contest/1731/submission/186975680 "Submission 186975680 by adedalic")
     69 
     70 [1731D - Valiant's New Map](/contest/1731/problem/D "Codeforces Round 841 (Div. 2) and Divide by Zero 2022")
     71 
     72 Idea: [s_jaskaran_s](/profile/s_jaskaran_s "Candidate Master s_jaskaran_s")
     73 
     74 **Hint 1**
     75 
     76 For a particular size, how to check if there's a cube greater than that?
     77 
     78 **Hint 2**
     79 
     80 Try Binary search on side length.
     81 
     82 **Hint 3**
     83 
     84 Let $x$ be the side length. How to check if a square has all its elements $\geq x$ in $O(1)$?
     85 
     86 **Solution**
     87 
     88 Tutorial is loading...
     89 
     90 **Code(Prefix Sum)**
     91 
     92 [186975714](/contest/1731/submission/186975714 "Submission 186975714 by adedalic")
     93 
     94 **Code(Sparse Table)**
     95 
     96 [186975738](/contest/1731/submission/186975738 "Submission 186975738 by adedalic")
     97 
     98 [1731E - Graph Cost](/contest/1731/problem/E "Codeforces Round 841 (Div. 2) and Divide by Zero 2022")
     99 
    100 Idea: [s_jaskaran_s](/profile/s_jaskaran_s "Candidate Master s_jaskaran_s")
    101 
    102 **Hint 1**
    103 
    104 Can you find the number of edges for each possible $GCD$?
    105 
    106 **Hint 2**
    107 
    108 Did you try Greedy?
    109 
    110 **Solution**
    111 
    112 Tutorial is loading...
    113 
    114 **Code**
    115 
    116 [186975762](/contest/1731/submission/186975762 "Submission 186975762 by adedalic")
    117 
    118 [1731F - Function Sum](/contest/1731/problem/F "Codeforces Round 841 (Div. 2) and Divide by Zero 2022")
    119 
    120 Idea: [nishkarsh](/profile/nishkarsh "Master nishkarsh") and [s_jaskaran_s](/profile/s_jaskaran_s "Candidate Master s_jaskaran_s")
    121 
    122 **Solution**
    123 
    124 Tutorial is loading...
    125 
    126 **Code**
    127 
    128 [186975785](/contest/1731/submission/186975785 "Submission 186975785 by adedalic")