74TrAkToR's blog

Codeforces Round #828 (Div. 3)
By 74TrAkToR, history, 18 months ago, translation, In English

Hello! Codeforces Round 828 (Div. 3) will start at Oct/16/2022 17:35 (Moscow time). You will be offered 6-8 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating of 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of open hacks.

You will be given 6-8 problems and 2 hours and 15 minutes to solve them.

Note that the penalty for the wrong submission in this round is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participant of the third division, you must:

  • take part in at least five rated rounds (and solve at least one problem in each of them)
  • do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work, pashka for help with ideas for problems and for coordination of my work. Problems have been created and written by MikeMirzayanov, 74TrAkToR and pashka.

We would like to thank: Gornak40, meowcneil, Vladosiya, senjougaharin, efimovpaul, powergee101, tanus_era for testing the contest and valuable feedback. List of testers will be updated.

Good luck!

UPD: Editorial

  • Vote: I like it
  • +155
  • Vote: I do not like it

Comments Comments (125)
| Write comment?
»
18 months ago, # |
  Vote: I like it +4 Vote: I do not like it

As an enthusiastic coder, I will comment first :)

→ Reply
»
18 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Finally, my first Unrated Div.3!!

→ Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But imagine what might happen...

    Spoiler
    → Reply
»
18 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Classical + Mathematics

→ Reply
»
18 months ago, # |
  Vote: I like it -27 Vote: I do not like it

Can anyone tell me why I am getting TLE on this submission? https://codeforces.com/contest/1665/submission/176381750

→ Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Use map instead of unordered_map

    → Reply
    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But unordered_map operations have time complexity O(1) which is less than map operations time complexity O(logn). How this worked?

      → Reply
»
18 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Fell down below 1600 due to FST. Getting a chance to rise, the very next day! Thanks!

→ Reply
»
18 months ago, # |
← Rev. 2   Vote: I like it +106 Vote: I do not like it

Source

→ Reply
»
18 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Wow, I thought to give Div3 Tommorow but became an Expert today :)

Spoiler
→ Reply
»
18 months ago, # |
  Vote: I like it +11 Vote: I do not like it

The current number of upvotes is 74, and the announcement was sent by 74traktor. Leave a message to commemorate it.

→ Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Quick, upvote this comment so when it has +66, we can commemorate it as well!

    → Reply
    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I don't really care about that, but 74traktor is a very high level coordinator, and we're working with him, and I think the problems he set must be great.

      → Reply
»
18 months ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it
Spoiler
→ Reply
»
18 months ago, # |
  Vote: I like it +1 Vote: I do not like it

It is so good that contest are hold often :)

→ Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Wishing everyone positive delta, although that is technically impossible.

→ Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think the number of participants will be less than the average due to EL CLASSICO time which is the same as the round

Spoiler

GL everyone !

→ Reply
»
18 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Custom Invocation is broken, runs forever.

→ Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Did 6/7, but the overall user experience is rather poor compared to Leetcode. Custom invocation was crushing for the first hour, making it impossible for me to test my solutions. Sure I can get an external interpreter which I guess I will have to do next, meh. Adding a dedicated problem discussion would be really nice, to compare ideas and solutions.

→ Reply
»
18 months ago, # |
  Vote: I like it +1 Vote: I do not like it

These math rounds always make me revisit my high school math. Nice questions though

→ Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hint for E1 Please

→ Reply
  • »
    »
    18 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it
    Hint
    → Reply
    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Bruh!! after that? I have a gut feeling that it is going to be insanely easy

      → Reply
    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      got it, thanks As I guessed, it is insanely easy

      → Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    check for all possible x(or y).

    → Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I used sieve. You can also think of solving it with sieve

    → Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem E2?

→ Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Think about prime factorization of a * b

    → Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    x must be divisible by the product of any divisor of a and any divisor of b. So for all divisors of a and b check if there is a corresponding x and y or not

    → Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Video Solution for E2.

    → Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve problem d??

→ Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Some number $$$m$$$ is divisible my $$$2^n$$$ if it has $$$n$$$ twos when you break it down into prime factors.

    Firstly you need to count the number of twos in product of all numbers in $$$a$$$. If there is less then $$$n$$$ twos, you will need to multiply some numbers by $$$i$$$. It is best to multiply with $$$i$$$ s with most twos when you break it down into prime factors first. When you have number of twos greater than or equal to $$$n$$$ you are done. You just need to output have many times you multiplied with $$$i$$$.

    My submission: 176530693.

    → Reply
    • »
      »
      »
      18 months ago, # ^ |
      ← Rev. 2   Vote: I like it +2 Vote: I do not like it

      As an alternative way (simpler implementation), you can generate an array of all numbers in $$$[1,n]$$$, sort them in decreasing order by the number of trailing zeroes they have in their binary representation (this is essentially the same with the number of $$$2$$$ in its prime factorization), and do a simple iteration on it. My submission is 176524669.

      → Reply
      • »
        »
        »
        »
        18 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Please help me with this solution. I pretty much did something similar but it got hacked 176544364

        → Reply
        • »
          »
          »
          »
          »
          18 months ago, # ^ |
            Vote: I like it +2 Vote: I do not like it

          You are iterating over an array of size $$$2\times 10^5$$$ on every test case. This is $$$O(NQ)$$$ (given $$$N=2\times 10^5$$$). You need to reduce this number of iterations to $$$n$$$ on each testcase, to use the fact that the sum of $$$n$$$ in all test cases is not bigger than the maximum value possible.

          → Reply
      • »
        »
        »
        »
        18 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        178050351 chromate00 please help me to see why my submission is wrong, I can not understand, thank you very much

        → Reply
        • »
          »
          »
          »
          »
          18 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          It's hard to exactly point out the issue on this solution, but I think it should be an overflow issue. (You could use addition instead of multiplication in this problem.)

          → Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you for having wonderful Div 3 Test. Thanks to all concerned who organized the test.

It is to inform that in Question "E1 Divisible Numbers (easy version)" I have submitted my code in python.

In third test, there is a possible answer 9 16. But autorun rejected my code on test 3. It is informed that it is valid answer as per your conditions. Kindly check and please accept my code. You can restrict the answer if there are multiple answers.

Thank you.

→ Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve E2 ?

→ Reply
  • »
    »
    18 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    it's not hard you need the a*b divisors but since it's too large you could get the divisors of a and b and then multiply each two elements of both numbers divisors and put it in the array of a*b divisors and the rest is the same

    → Reply
»
18 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

can anyone please tell me why in question D in this case 4 13 17 1 1 the answer is -1 after (13⋅1)⋅(17⋅2)⋅(1⋅3)⋅(1⋅4) this operation for 1 time if i choose i=2 and do (17,2) again then what will be the total number of factor in the multiplication there will be 4 factor of 2 and the multiplication is divided by 2^n as n=4 here so why the answer is -1 here as here it is said i can do the operation as many times but in each operation the chosen index should be different?

→ Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    You cannot apply the operation repeatedly to a single index. In other words, all selected values of i must be different. I guess, you didn't pay attention to this sentence.

    → Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The statement stated that you can apply the operation on each index only once.

    → Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can do at most $$$n$$$ operations. You can't choose any $$$i$$$ more than once.

    → Reply
»
18 months ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

I think my solution for E1 is hackable, can anyone try to hack it?

https://codeforces.com/contest/1744/submission/176559805

→ Reply
»
18 months ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Anyone here who knows Java and has solved Traffic light problem?

→ Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello guys. I want to cry. LOOK AT THIS PLEASE. I just send this code in the round and it got TL (problem D). 

for (int i = 0; i < n; i++) {
    cin >> a[i];
    pr *= a[i];
}
while (!(pr & 1)) {
    k++;
    pr >>= 1;
}

But now, I send this, and it got "OK". Can someone answer me — "WHY?":

for (int i = 0; i < n; i++) {
    cin >> a[i];
    while (!(a[i] & 1)) {
        k++;
        a[i] >>= 1;
    }
}
→ Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    You overflow pr. So it presumably become 0 and now you have infinite loop

    → Reply
»
18 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Such a unlucky contest for me. Spent more then 90 minutes combined on $$$A$$$ and $$$C$$$ trying to figure out why I am getting WA, reimplemented both problems in a little different way and got AC...

→ Reply
»
18 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I Wanna shoot my HEAD .. I spent half an hour trying to understand wtf is wrong with my E2 Solution and in the end I realized i wrote in the for loop divo2.size() instead of j<divo2.size() .. I wanna **** my stupid code .

→ Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1744/submission/176594390

can anyone show me a testcse where my solution not fits?(problem c)

→ Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can print the specific test case by modifying your code.

    → Reply
»
18 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I liked B, especially D.

→ Reply
»
18 months ago, # |
  Vote: I like it +12 Vote: I do not like it

Solved the last task of the round for the first time!!!!!! Indeed its a new exciting day!

→ Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What is your approach for problem F?

    → Reply
    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Well,

      1. First realize that for MEX > MED, the first t elements should be 0 1 2 ... t-1

      2. Now, save the tighest bounds for {0} ,{0 1}, {0 1 2}, ... using two arrays, to be used on demand

      3. Iterate on t [from 1 to (n+1)/2 ]

      4. The sub array size could be 2t or 2t-1 and so, calculate the left and right slacks, you can get the possible number of subarrays for this t.

      I felt the base testcase which they gave was veryy good, I corrected 4~5 bugs using it.

      → Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How did this solution get hacked? 176544364 I'm certain my solution was correct. For every power of 2 I will take the largest 2^i which costs me 1 unit and gives me a lot of 2's. Even positions will also give me 1 unit of cost for a single 2. I combined both and sorted based on largest 2 giver. Then took prefix count.

→ Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    When the condition twos >= n is fulfilled, you always iterate over all two array: for (auto [i, j] : two). So complexity of your solution is $$$O(t M)$$$, where $$$M = 200000$$$. So, it is obvious that this solution will most likely get TL.

    → Reply
»
18 months ago, # |
  Vote: I like it +5 Vote: I do not like it

One of the hacks that works for E1: 10 1 1 100000 100000 1 1 100000 100000 1 1 100000 100000 1 1 100000 100000 1 99999 100000 100000 1 99999 100000 100000 1 99999 100000 100000 99999 99999 100000 100000 99999 99999 100000 100000 99999 99999 100000 100000

→ Reply
»
18 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

176594240 It says that my answer is wrong in 17th test case but when I am running on my compiler and other online compiler I am getting correct answer. Someone please help my solution was correct still I had to stuck in this question because of this error. Thank you in advance!

→ Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Don't use floating point operations unless you have a concrete proof that the result will be exact.

    → Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    At least, your rounding (long long int)log(...)/log(2) doesn't always work...

    → Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why isn't there score distribution in Div.3 and Div.4 rounds like in Div.2 and Div.1 rounds?

→ Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Because Div. 3, Div. 4 and Edu rounds follow ICPC rules

    → Reply
  • »
    »
    18 months ago, # ^ |
    ← Rev. 2   Vote: I like it -8 Vote: I do not like it

    It follows the format of Extended ICPC, meaning that rank is first determined by solve count, and then by penalty. Still, there is a reason why solving (subjectively) easier problems first is more beneficial. We need to understand that the penalty is the sum of the penalties on each problem. Now to simplify things, lets assume you can solve A in $$$5$$$ minutes and B in $$$10$$$ minutes, and there are no more problems than these two. If you solve A first, the penalty will be $$$5+(5+10)=20$$$ minutes. However if you solve B first, the penalty will be $$$10+(10+5)=25$$$ minutes. Therefore in this simplified model, solving the easier one first is ideal. We can generalize this to more than 2 problems, and understand that it is ideal to solve problems in increasing order of difficulty.

    → Reply
    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I know what format of Extended ICPC means, but why format of Div.2 rounds isn't used?

      → Reply
      • »
        »
        »
        »
        18 months ago, # ^ |
          Vote: I like it -11 Vote: I do not like it

        I wish I knew. IIRC Div.3 was planned to be Ex-ICPC format from its first round and on, but I don't exactly know why they decided it that way.

        → Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Solution for F:

Enumeration $$$i$$$ from $$$1$$$ to $$$n$$$,consider subarray $$$Sub$$$ which's median is $$$a[i]$$$.

To make $$$MEX(Sub)>MED(Sub)$$$,$$$1,2,...,a[i]∈Sub$$$ must be hold.

Use binary search to find the min subarray $$$Sub_{min}$$$,which contains $$$1,2,...,a[i]$$$.

Next,we have to make sure that $$$a[i]$$$ is the median.We can add some numbers on the left and right sides of $$$Sub_{min}$$$ to achieve it.Then we can easily count it.

→ Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

nice problems

→ Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you rise TL on E? So many hacks by TL, that should not happened

→ Reply
»
18 months ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve E2? Can someone explain in a easy way?

→ Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    You can get the prime factors of a, and b. Then create every possible pair of numbers with those factors.

    For example, if a = 2^2 * 3, b = 2^3 * 5, then a*b = 2^5 * 3 * 5. all possible pairs are

    1 480

    2 240

    ...

    In the end, check if the pair has the constraints. (if x <= a, then make x to (a/x + 1)*x).

    → Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Prerequisite: Maximum number of divisors of n if $$$ n \leq 10^9 $$$ is 1344, you can refer oeis and this comment.

    So first calculate all divisors of a and b. And iterate over all possible pairs of divisors of a and b, be l and m. Try to set x as multiple of l*m and y as a multiple of $$$ \frac{a*b}{l*m} $$$

    Overall complexity would be : $$$ O(\sqrt{A}+\sqrt{B}+A^\frac{1}{3}*B^\frac{1}{3}) $$$

    → Reply
»
18 months ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Epic tests for problem E1, thank you!

→ Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

10 1 1 100000 100000 1 1 100000 100000 1 1 100000 100000 1 1 100000 100000 1 99999 100000 100000 1 99999 100000 100000 1 99999 100000 100000 99999 99999 100000 100000 99999 99999 100000 100000 99999 99999 100000 100000

I hacked 31 Solutions of E1 problem using this testcase.

→ Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Unfortunately.your solution on E1 has been hacked:(

→ Reply
»
18 months ago, # |
  Vote: I like it -8 Vote: I do not like it

rainboy Can you please explain your solution for Question 1744F - MEX vs MED ?

→ Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I could have been an expert, but my E1 got hacked...TAT

→ Reply
»
18 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

A job is free for you, 15$ per hour during contests so you remind me to use long long for all variables.

The second contest this week I get WA because one of the variables is int

→ Reply
»
18 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

can anyone help me debug C? https://codeforces.com/contest/1744/submission/176567867 found it

→ Reply
  • »
    »
    18 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Why do you set first to true when i==n?

    What about rgr?

    View your code on a mobile phone without custom test. Forgive me if I were wrong.

    → Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Editorial?

→ Reply
»
18 months ago, # |
  Vote: I like it +1 Vote: I do not like it

isn't it a rated contest? When it will changes our rating?

→ Reply
  • »
    »
    18 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I guess, tomorrow at the latest (2 div3 contest ago they took 1 day to update rating, as cheaters were being eliminated)

    → Reply
»
18 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Why is this code only gives YES as output?

include <bits/stdc++.h>

using namespace std; int main() { int t; cin>>t; while(t--){ int n,k=0; string s; int a[n]; for(int i=0;i<n;i++){ cin>>a[i]; } cin>>s; map<int,char>m; for(int i=0;i<n;i++){ auto it = m.find(a[i]); if(it==m.end()||s[i]==(*it).second){ m.insert(pair<int,char>({a[i],s[i]})); } else{ k++; } } if(k==0){ cout<<"YES"<<endl; } else{ cout<<"NO"<<endl; } } return 0; }

→ Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F ?

→ Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Assume a segment s of size k. To have mex(s) > med(s), s must atleast have the elements 0, 1, 2, ..., k/2. With this knowledge, we can now keep track of the index at which each p_i occurs, Now we iterate k from 1 to n, and maintain two variable l and r to keep track of the leftmost and rightmost index between which 0..k/2 are located. If r-l+1 > k, then we have no good segments of size k. Else the number of good segments would be given by min(l, n-k) — max(0, r-k+1) + 1. The expression above is simply the number of segments of length k that contain the range l..r

    You can see my submission here: https://codeforces.com/contest/1744/submission/176616730

    → Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is this code giving tle? it was working fine in the local editor code-my submission

→ Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

E2 passed , E1 failed :(

→ Reply
»
18 months ago, # |
  Vote: I like it +2 Vote: I do not like it

I'm talking about the coincidence with the decisions of other participants. This is not fair, I wrote the code completely by myself, it took more than an hour. You can see the evolution of my code and attempts. I do not understand at all how someone could copy my code, please do not ignore my attempts, since this is only my second contest in the rating. I have not logged into my account for a long time, I will try to change the password. Please at least update my rating, i been waiting all day for this and at the end of this. Next time I'll be more careful with my account. https://codeforces.com/contest/1744/submission/176557816 https://codeforces.com/contest/1744/submission/176570918 https://codeforces.com/contest/1744/submission/176579287 https://codeforces.com/contest/1744/submission/176580294

→ Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve the problem of E1????

→ Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My naive solution was , iterate on x from a+1 to c and try to calculate y by taking x.y = a.b.1 or a.b.2 or .....

    This passed the system tests at first, but got hacked later on

    → Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

too ez! try harder next time.

→ Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem B? I get TLE on test 5

→ Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Just have one variable for the sum of whole array. You also need to keep track of number of odd elements and number of even elements. If you iterate over the array every query that will be $$$O(nq)$$$ which is too slow.

    At the beginning you need to count the number of odd and even numbers in an array and calculate the sum. In every query will add $$$x$$$ multiplied by number of odd/even numbers to the sum. Note that number of even and odd numbers changes so try to update those numbers without iterating over the whole array. Try to think about the parity of

    $$$2k+2k$$$,

    $$$2k+(2k+1)$$$,

    $$$(2k+1)+(2k+1)$$$

    to calculate new number of even and odd numbers after each query.

    → Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How hacking will increases your points in div 3 or educational round Like in general div 2 round it will increases your point by 50.

→ Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Getting hacked sucks! I fell from rank 200 to 1000... Regardless...the round was GG

→ Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain the E2 for me,I got no idea on this problem,thx!

→ Reply
  • »
    »
    18 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    E2 is quite simple. You first use Sieve to find all the primes in the range 1 to max(sqrt(a)+1,sqrt(b)+1). Then, you do prime factorization on both a and b and push back all of them into a vector. After that just use somewhat like a knapsack dp to find all the factors of a*b. Try if the pair of factors can fit into a<x<=c and b<y<=d by multiplying a constant k. If it is possible output the answer, else output -1 -1.

    → Reply
    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think I applied your idea just by a different way.

      I pushed all the prime factors of a*b in a vector and generated different combinations so that the factors can be distributed into 2 sets for x and y, but would not it cost us (2^size). In problem E1, size can go upto 32 at max, so still it gave me TLE.

      I think I am missing something.

      → Reply
»
18 months ago, # |
  Vote: I like it +3 Vote: I do not like it

finally Expert!!!

→ Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, can anyone please help me with my solution to D solution. I've been debugging it for some time, but idk whether it is the way I found largest power of 2 below n gives the wrong answer. Thanks a lot in advance!

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

nice round

→ Reply