By awoo, history, 2 years ago, translation, In English

Hello Codeforces!

On Mar/09/2020 17:35 (Moscow time) Educational Codeforces Round 83 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 7 problems and 2 hours to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 mhq 7 135
2 MiracleFaFa 7 145
3 neal 7 161
4 uwi 7 191
5 CWOI 7 196

Congratulations to the best hackers:

Rank Competitor Hack Count
1 MarcosK 134:-15
2 _apurv_ 28
3 racsosabe 24:-1
4 sv_restart 18:-3
5 Norrius 16
773 successful hacks and 620 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A hochesh 0:00
B Kirill22 0:02
C i.e 0:03
D neal 0:08
E andrew 0:09
F MiracleFaFa 0:33
G gisp_zjz 0:31

UPD: Editorial is out

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

»
2 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Good luck everyone!

»
2 years ago, # |
  Vote: I like it -47 Vote: I do not like it

7 problems in 2 hours! sounds like high rating :3

  • »
    »
    2 years ago, # ^ |
      Vote: I like it -54 Vote: I do not like it

    You think 7 problems in 2 hours is a lot? It is not a lot compared to that

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it -38 Vote: I do not like it

      But in this contest there were 3 bilateral questions (B1 and B2), (C1 and C2), (D1 and D2).

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it -45 Vote: I do not like it

        That is true, but after this contest everyone complained about too much subtasks. It doesn't make sense for 3 problems to have subtasks in 1 contest! Codeforces is not OI style. It is supposed to be CPC style! You might need to check this and this

  • »
    »
    2 years ago, # ^ |
      Vote: I like it -20 Vote: I do not like it

    thanks for the information :(

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks a lot..awoo

»
2 years ago, # |
  Vote: I like it +32 Vote: I do not like it

Wasn't this contest supposed to be like 3 weeks ago?

I remember registering to an Educational Round and it dissapeard, and I really wondered why.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Yes,it is.And I guess there is a problem of test data found by careful questioners.

»
2 years ago, # |
  Vote: I like it -38 Vote: I do not like it

I hope this contest will help me forget the past few contests and get over them. The setters look good for this one, although a few names are somewhat a matter of concern.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Seems more like a Speed Test.. XD

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

We want short description.So please.......

»
2 years ago, # |
Rev. 4   Vote: I like it -44 Vote: I do not like it

thanks for so many upvotes :)

»
2 years ago, # |
Rev. 2   Vote: I like it -10 Vote: I do not like it

.

»
2 years ago, # |
  Vote: I like it -9 Vote: I do not like it

Hope to get blue today!

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, just wanted to know when will the scoring distribution be put up?

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the imaginary scoring distribution

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Each problem is worth [10000 — # of minutes to solve] points.

»
2 years ago, # |
  Vote: I like it +55 Vote: I do not like it

»
2 years ago, # |
  Vote: I like it +14 Vote: I do not like it

ME: After 1 successful submission. Let's see friends standing :)

»
2 years ago, # |
  Vote: I like it -27 Vote: I do not like it

speedforces

»
2 years ago, # |
  Vote: I like it +2 Vote: I do not like it

I really need to code more because I got the idea of C in one min but it took me more than an hour to code it correctly it's my fault

»
2 years ago, # |
  Vote: I like it -15 Vote: I do not like it

why C is giving right answer on my ide and WA on codeforces ide for test case 1??please tell

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Because of precision error. Output can sometimes be 4.99999999999 while its actually 5. So just ciel if the difference is less than an epsilon value like 1e-9, else just floor.

    ll getLog(ll v) {
        double z = log2(v)/log2(k);
        ll a = (ll)z;
        if(fabs(z-(a+1)) < 1e-9)
            return a+1;
        return a;
    }
    
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it -28 Vote: I do not like it

      thanks but it's late...no problem next time

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        Well you weren't going to get a response during the contest anyways. Would be considered cheating I guess.

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it -13 Vote: I do not like it

          no but it's not accepted...btw and I didn't copy the logic...and I during the contest I thought...the leading team will be answing..not the contestants

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I faced the same issue. Thanks for the info, ll take care of it next time. A doubt though, why are the other online ides giving the correct answer?

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          I'm not sure tbh but I'd guess it depends on the compiler or PC architecture or maybe even just luck.

          Just be careful when using doubles and always use the difference instead to checking equality directly or try to avoid using them whenever possible.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Imagine being able to solve problems yourself ;) http://www.usaco.org/index.php?page=viewproblem2&cpid=648 (Problem E)

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    this round educated me on how to organize my folders better... I spent so long looking for my 262144 code ((

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In that problem, the move is the same, but the goal is to maximize the max element. Is it necessarily true that the resulting array is also the shortest possible array?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The goal of both the problems seems bit different. In today's question, they asked to minimise the length of array, whereas in the link they have asked to maximise the largest remaining element. Am I missing something?

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      No you are not missing something, but the dp in both problems is exactly the same if you read the solution except this problem requires one more (obvious) step.

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    [Deleted]

»
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it

How to solve E?

»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

How to solve D problem?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +69 Vote: I do not like it

    Let's construct the answer step by step. Consider a sorted array of length $$$n - 1$$$ for a moment, which contains no repetitions and whose elements range from $$$1$$$ to $$$m$$$.

    There are $$${m}\choose{n - 1}$$$ different arrays with this property (since there are no repetitions, one choice of $$$n - 1$$$ numbers from $$$m$$$ available corresponds to exactly one ordering of them).

    Now we can pick the maximum and throw some elements from the array to its right (in decreasing order), others remaining to its left. There is a total of $$$2^{n - 2}$$$ subsets of numbers that we can position to the right of our maximum, each subset corresponding to exactly one ordering (length $$$n - 1$$$, and we're not considering the maximum itself).

    Finally, we pick one of the numbers (but not the maximum) and add its duplicate to our array. There are $$$n - 2$$$ different choices for this. Also we must consider that we don't care whether the chosen element is on the right or on the left, since its copy will appear on another side, and we cannot distinguish between them. So, we need to divide the final answer by $$$2$$$.

    Thus, the answer is $$${m}\choose{n - 1}$$$$$$ \cdot 2^{n - 3} \cdot (n - 2)$$$.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Didn't understand why you divided the answer by 2 at the very end. For example, 1 2 5 4 3, we can have 1 as duplicate and get 1 2 5 4 3 1 and do the same for every n-2 number (1,2,3,4). So why divide by 2?

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        "There is a total of $$$2^{n−2}$$$ subsets of numbers that we can position to the right of our maximum".

        If you choose $$$1$$$ as the duplicate, you'll get the same resulting array if you move $$${1, 3, 4}$$$ to the right and if you move $$${3, 4}$$$ to the right in step 2 — either way there will be a $$$1$$$ on both sides.

      • »
        »
        »
        »
        2 years ago, # ^ |
        Rev. 2   Vote: I like it +10 Vote: I do not like it

        Another way of seeing this is, the repeating element has to be on both the sides of the peak element. For each of the non repeating element, you have 2 choices, either the left side or the right side. Therefore, (n-3) elements having 2 options each giving 2^(n-3) ways in total.

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          This is equivalent to chosing a subset of elements placed on a given side

    • »
      »
      »
      2 years ago, # ^ |
      Rev. 2   Vote: I like it +18 Vote: I do not like it

      Thanks for an excellent explanation. Understanding this made me realize that there's another way to think about it (minor differences) :

      • Pick (n-1) unique elements ranging from 1 to m. (The reason for n-1 instead of n is that one of these will eventually be duplicated, resulting in a total of n). This can be done in C(m, n-1) ways.
      • From these (n-1) elements, pick the largest number. This can be done in only one way.
      • From the remaining (n-2) elements, pick the duplicate. This duplicate will go on both sides (ensuring that we have at least one element to the left and right of the maximum). There's (n-2) ways of doing this.
      • The remaining (n-3) numbers can go either to the left or to the right of the maximum. There's 2^(n-3) ways of doing this.
      Total number of ways =  C(m, n-1) * (n-2) * 2^(n-3)
      
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you tell why are we taking n — 1 elements from m and not n elements`

      `

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        The reason for n-1 instead of n is that one of these will eventually be duplicated, resulting in a total of n (explained above by @sh_maestro).

    • »
      »
      »
      2 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      How to calculate it without overflowing long long? I can take the modulo when I multiply but it can make the result incorrect when I divide.

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        The correct way to do division is using modular inverse.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You can exclude the duplicate element from the set along with the maximum, so that you consider a set of $$$n-3$$$ elements. Then you don't need to divide by 2 afterwards.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Helped alot!! Thanks.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Very nicely explained went straight into my head thanks for it!!

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I have found the formula $$$C_{m}^{n-1} (n-2) 2^{n-3}$$$.

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

What was test case 4 of problem C??

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Is D is formula based ?? if yes!! then what's the formula

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +34 Vote: I do not like it

    Yes! The answer is: $$$ m\choose (n-1)$$$$$$ * (n-2) * 2^{(n-3)} $$$

    We choose $$$ ( n - 1 ) $$$ values from $$$1$$$ to $$$m$$$. Except the max value, each value can be chosen to duplicate ( in $$$(n-2)$$$ ways ). The remaining $$$(n-3)$$$ values ( except the max and duplicate value ) can be split into two ways, either on the left or right of the max value ( $$$2^{(n-3)}$$$ ways ).

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you explain why 2^(n-3)?

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Each element is given 2 options, either to be on the left or right of the max value. For example, if there is 1 element. It can either be L or R of the max value. If there are 2 elements, there are 4( $$$2^2$$$ ) ways: LL, LR, RR, RL. Similarly for $$$n-3$$$ elements, there are $$$2^{n-3}$$$ ways.

»
2 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

Can somebody tell me if a[l]~a[r] can be merged to one element.Whether this element is fixed?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Yes, this element seems to be fixed. Proof : define a quantity for your array S = sum of all 2^(a[i]) where a[i] is an array element Then notice, that in one operation, two nearby elements each with value x contributing 2^x each to the sum disappear and leave x+1 in their place which contributes 2^(x+1) as 2^x + 2^x = 2^(x+1) therefore this quantity which we defined, S never changes hence if a[l] to a[r] is merged into a single element, it is uniquely determined.

»
2 years ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it

Solved problem E in $$$O(n^3 \cdot \text{MaxValue}/64)$$$ with bitsets. submission

»
2 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

F, What's the tail-period-length of $$$(x,y,z)$$$? or just prep a $$$5^3$$$ offline memo?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    If you bruteforce period, you will see that it never exceeds 10. So you can precalculate all answers for all $$$(x, y, z)$$$ for numbers up to LCM(2, ..., 10) = 2520, and with this you can easily answer queries.

    • »
      »
      »
      2 years ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      I know it never exceed 10. I wanna know is there a relation $$$f(x,y,z)$$$... but wow, prep a long array is great.

      since I just got a naive idea, prep a length about 100, then for >100, use period-length to fit in (50..100).

»
2 years ago, # |
Rev. 2   Vote: I like it +26 Vote: I do not like it

I found G much easier than E and F

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I arrived at G's solution within 5 minutes after reading the question, whereas I spent 40+ minutes on F during and I'm still totally clueless.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      At last, I found one of my sons. I hope I also find my right child soon.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    For me E is much easier than D, F or G... I stuck at D for 50mins, but I solved E in just 10mins.

    Can you give me some hints on G?

»
2 years ago, # |
  Vote: I like it +42 Vote: I do not like it

Problem F sentence was SUPER. HARD. TROLLING.

"previous" and "no matter when" at the same sentence.. So It can be translated many ways.

I spend more than 1 hours at this problem...T^T

»
2 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

why following logic is not working for question D??

C= combination 
M= modulus
for(ll i=n-1;i<=m;i++)
{
ans=(ans+((C(i-1,n-2,M)*(n-2))%M))%M;
}
»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Can someone explain solution of E in detail. Thanks in advance.

  • »
    »
    2 years ago, # ^ |
    Rev. 3   Vote: I like it +11 Vote: I do not like it

    Dp Solition:

    for every subarray check if it possible to convert it into single integer value denote this as val(arr[i : j ]) => integer for any i , j pair 0 <= i <= j < n

    for every subarray [i, j]

    iterate over i<= z < j such that:

    if( val(arr[i : z]) ==   val(arr[z+1 : j])):
    
        val(arr[i : j ] ) =  val(arr[i : z ] ) + 1
»
2 years ago, # |
  Vote: I like it +2 Vote: I do not like it

What Test case 4 of C problem....?? question seemed easy but still was not able to pass it :-(

»
2 years ago, # |
  Vote: I like it +15 Vote: I do not like it

No Screencast? tmwilliamlin168

»
2 years ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

Why there is an "Unexpected verdict" when I try to hack solution of C?

»
2 years ago, # |
  Vote: I like it +16 Vote: I do not like it

How to solve F? I recalled Grundy Number technique, but the range is too large to use Grundy Number. Thus I tried to find the period, but I cannot find any period.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For Div2 E, I tried a greedy solution using stack, going left to right, and it failed.
Can someone help me how to prove it wrong ?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    7 7 5 5 6 8

    Going left to right gives, 8 7 8 Optimal Strategy gives, 7 9

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Try 1 1 1 2

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Greedy wont work. If processing left to right -> 5 3 3 3 4 -> 5 4 3 4. Whereas, you could have, -> 5 3 4 4 -> 5 3 5

    Same problem if you process right to left. Just invert the array.

»
2 years ago, # |
  Vote: I like it -14 Vote: I do not like it

SpeedForces.

»
2 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Why this wont work for D:

nCr(m-i,n-2)*(n-2) for i>=1

Fix 2 ends with a number i, so we have to fill n-2 places with numbers from i+1 to m (ie nCr(m-i,n-2)) , and we can have n-2 positions for the biggest number so multiply by n-2

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    This assumes that the repeat number is necessarily the smallest number, which is not necessarily the case.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You know what's wrong with this approach — We fix the value $$$v$$$ and position $$$p$$$ of the peak value. Numbers on left of peak are $$$p-1$$$ and on right are $$$n-p$$$. Now we have to choose total of $$$n-2$$$ values less than $$$v$$$ to place on non-peak position. Let

      $$$x$$$ = $$$min(p-1, n-p)$$$

      . Then

      $$$R$$$ = $$$\sum_{p = 2}^{n-1}\sum_{v = n-1}^mC_{x}^{n-2}C_{n-2}^{v-1}$$$

      .

      • »
        »
        »
        »
        2 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        It's fine — You missed a multiplying factor $$$x$$$ because you can choose any of them on the bigger side. 72880191

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i did the same

»
2 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Missed E by 2 minutes

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Can D be solved with DP, if yes please share dp states

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If it can, then I think it will be only as a by-product of the closed form solution.

»
2 years ago, # |
  Vote: I like it +12 Vote: I do not like it

I hate the fact that in educational codeforces we dont get the editorial before the next day.

»
2 years ago, # |
Rev. 2   Vote: I like it +18 Vote: I do not like it

I think there is something wrong with checker of problem C. I tried to hack one submission that should give WA and I got "unexpected verdict" (id of hack is 621220).

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh, it seems the problem with the checker is when n=1. I tried to hack with n=2 and got successful hacking attempt. Please, fix that :)

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to get 3 for the 4th string in the first testcase (problem G)? It looks impossible to me.

»
2 years ago, # |
  Vote: I like it +20 Vote: I do not like it

In problem F, how to find upper bound on precalculation ?

What I did is calculate 3 grundy values for 3 different attacks for a particular castle. Since x,y,z <= 5 , we need atleast 5 states to repeat.

First value can be from 0 to 3 and 2nd,3rd value can be from 0 to 2. So I thought (4*3*3)^5 is an upper_bound which is not the case.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Brute force shows that the upper bound for the period and pre-period is at most $$$36$$$, but proving it can be really painful.

    Well, one can prove some reasonable bounds like $$$10^5$$$ intuitively.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      More reasonable bound should be around 10^4, given t <= 1000 and time 3s. Unless and until there is some magic :D

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +14 Vote: I do not like it

        There is some magic.

        Originally, when I was preparing this problem, I decided to set $$$x, y, z \le 3$$$ so it would be clear that there are not so many states — the most generous upper bound is $$$4^9$$$ in this case.

        Then my colleagues told me that it could be possible to analyze all cases of $$$x, y, z$$$ since there were only $$$27$$$ of them, and most of them were symmetric to some other cases or trivial. I didn't want such solutions, so I've decided to check how far I could push the bounds.

        At some point, the bounds were $$$x, y, z \le 20$$$, leading to really large upper bounds, but surprisingly small periods when checked by brute force (if I remember correctly, even on such large constraints the longest period with pre-period was less than $$$500$$$). But these constraints were (intuitively) very unreasonable, so I've decided to drop them to $$$5$$$.

        I think that it's possible to prove that the period is something like $$$O(\max^2(x, y, z))$$$, but it surely will be a lot of work :)

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it +23 Vote: I do not like it

          Yes, good to keep it lower otherwise I would rather think about the different solution.

          Nonetheless it was a good problem.

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

https://codeforces.com/contest/1312/challenge/72826639 Hack my solution... I assumed no of steps are <=35 :((

»
2 years ago, # |
  Vote: I like it +11 Vote: I do not like it

What is Unexpected verdict in Hacks?

»
2 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Problem E, My greedy solution got WA on TC38 :( Can anyone help? Is the WA due to some corner case? Link

»
2 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Seems like checker for problem C not works. I got "Unexpected verdict" while hack others.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

WHY WHEN I HACK PROBLEM C I SEE "UNKNOWN VERDICT"?

»
2 years ago, # |
Rev. 3   Vote: I like it +45 Vote: I do not like it

E can probably be solved in n^2 — 72819557

explanation: let $$$dp[i]$$$ be number of answer for subarray $$$i..n$$$. If $$$i..j$$$ can be combined to get a single value we can write $$$dp[i] = min(dp[i],1+dp[j+1])$$$, to check if $$$i..j$$$ can be combined to get a single value, we can greedily merge from left to right, means if we get two adjacent equal values (If multiple such take leftmost) , we can erase them both and write a single value in their place. I have implemented this using stack

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you please explain your solution

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Do you know the proof for why if segment $$$i...j$$$ can be merged into one element, the order of operation won't matter and we will always get the same one element?

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      No, I don't know the proof

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Every element x was there at the beginning, or it was merged by two x-1. Independend of any other elements.

      Since the merge of two x-2 to one x-1 was before the merge of the two x-1 to x, there is only one possible tree-like path of merge ordering.

    • »
      »
      »
      2 years ago, # ^ |
      Rev. 2   Vote: I like it +8 Vote: I do not like it

      I've used the same approach (left-to-right greedy with stack merge of [L, R] into segment of length 1), though didn't bother optimizing from $$$N^3$$$ to $$$N^2$$$ 72829878


      Do you know the proof for why if segment i...j can be merged into one element, the order of operation won't matter and we will always get the same one element?

      Since we always transform adjacent, $$$a, a$$$ into $$$a+1$$$, the $$$Sum(2^{a_i})$$$ is an invariant, so if $$$a_L, a_{L+1}, ... , a_{R}$$$ could be merged into some value $$$U$$$, then $$$U = log_2 (2^{a_L} + 2^{a_L+1} + ... + 2^{a_R}) $$$

      (if I correctly understood Your question...)


      the order of operation won't matter

      Again, I'm not sure that I understood Your question, but I think it does: we can merge [1,1,1,1] into [3] ([1,1,1,1] -> [2,1,1] -> [2,2] -> [3]), but if we were to merge second and third 1, we would get [1,2,1] and no further merges are possible (but left-to-right greedy seems to work...)

»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Hii Can anyone plsss check this submission. He obfuscated all the codes. Is this Cheating https://codeforces.com/contest/1312/submission/72814153

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Writing your variable names in Russian doesn't make it obfuscation.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      No Its not Russian.

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +16 Vote: I do not like it

        YPFARROLCS obviously means sexy llama in Russian

        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          For each and everything defining it and making it not understandable is itself obfuscating. His accounts are aldready banned previously. Do check once His accounts are buihoatpt2k3provip buihoatpt2k3

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Umm that doesn't look like russian ? lol. Even if it is.. why tf would you replace a + sign with ECFEFMHJACSV lmao

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes . For each and everything. Previously his 2 accounts are banned

»
2 years ago, # |
  Vote: I like it -21 Vote: I do not like it

This contest was weird. G was trivial tree DP with segment trees and hashing whereas A was way too hard for a div2A.

»
2 years ago, # |
  Vote: I like it +50 Vote: I do not like it

One of the author's solution for the problem C had stupid bug so there are many hacks with unexpected verdict. Now everything is fixed and you can hack this problem. The round most probably will be rated because the initial test set didn't contain the tests that cause the bug. We are deeply sorry for this issue.

»
2 years ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

Greedy + Divide and conquer solution for E :

The greedy observation is that, minimum value in the array must be combined if possible.

Now consider a subarray having equal minimum elements.

Case 1 : It's length is even, then combine each pair is optimal

Case 2 : It's length is odd, then you should combine first few even elements, left one element which will break array into two, combine last remaining even elements.

Now call solve function for these 2 partitioned array, Do this for each possible breaking element at odd positions in subarray.

During contest, for Case 2, I called solve for the whole array again instead of 2 partitioned array. Which I hacked after the contest.

Update : Sorry, but this solution is also hacked by me.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I was thinking along these lines but couldn't complete it. The obstacle for me was in case 2 when you have exactly three identical elements, say 1 1 1. In that case you should combine either the left two 1's, or the right two 1's: for instance with

    $$$A = [1,1,1,2]$$$, it is optimal to combine the right two: 1 (1 1) 2 $$$\rightarrow$$$ 1 2 2, but:

    $$$A= [3,2,1,1,1,2]$$$, it is optimal to combine the left two: 3 2 (1 1) 1 2 $$$\rightarrow$$$ 3 2 2 1 2

    In general it seems hard to decide whether the left or right is better. Maybe you should count how long the consecutive "boundary" sequence 1,2,3,... is on both sides; like in the last example it extends till 3 on the left side but only till 2 on the right, so we chose left. But deciding this seems hard in general, since you can also have a sequence like 1,2,(2,2),4,5,6,(chain of 64 2s),8, which is equivalent to 1,2,...,8. (then I gave up)

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Isn't the case 2 makes it exponential ? What is the time complexity then ?

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Yes it is. Initially it passed at around 30ms so I thought there must be some magic, but when I calculated time complexity I got exponential so I hacked it.

»
2 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Can anybody suggest similar equation-finding problems as D.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    I think you can find similar problems in many Permutation and Combinations books of high school.

»
2 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Why the test cases for C problem were so bad? Is it necessary for problem creators to add weak test cases so that participants will try to hack others?

»
2 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Hack my C if you're cool

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

On E Will time n^3 hack?

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can explain me problem g sample one? how build a 10th string with 3 operation? i think i dont understand problem.

»
2 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Why are so many solutions for C failing?

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone hack this brute force solution of mine and get TLE? https://codeforces.com/contest/1312/challenge/72834695

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem E ?

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can sb hack my C?

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem D ?

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it +21 Vote: I do not like it

    Since one element has to be repeated, choose any (n-1) numbers from 1 to m to fill the array. This can be done in $$$\binom{m}{n-1}$$$ ways.

    Out of these n-1 numbers, one has to be repeated. Since we need a peak element, it cannot be repeated leaving us with n-2 numbers. Hence we can choose the repeating element in $$$\binom{n-2}{1}$$$ ways.

    We are left with (n-2) elements to be arranged on both the sides of the peak. Notice that we require strictly increasing and decreasing sequences on the left and right of the peak element, therefore the repeating element will never be on the same side. For the remaining (n-3) non repeating elements, every element has 2 options : to go either on the left or on the right of the peak. Therefore, number of ways of doing this is $$$2^{n-3}$$$.

    Final answer : $$$\binom{m}{n-1}$$$ x $$$\binom{n-2}{1}$$$ x $$$2^{n-3}$$$

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello Sir, I would like to bring your notice to the fact that some people are using multiple accounts for participating in contests and they hack their own solution to get points.

For Instance: https://codeforces.com/profile/rajankur this user has another account with URL as follows: https://codeforces.com/profile/CryBaby This is his secondary account and he used his primary account to hack his own solution which he submitted from his secondary account.

Hacked Solution- https://codeforces.com/contest/1312/submission/72825800 Same solution from different account- https://codeforces.com/contest/1312/submission/72845580

Just wanted to inform you about all these things going on and I hope that serious actions will be taken against such people (cheats).

Thank You

»
2 years ago, # |
  Vote: I like it -7 Vote: I do not like it

Can anyone hack my C ?

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem D? Explain please

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

there should be marks for successfully Hacking.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I wonder if there is any official editorial or somrthing

  • »
    »
    2 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Usually it becomes available just after hacking phase, when the contest is finished.

»
2 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

How to solve C with Bitmask ?? Can anyone help?

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Instead of keeping the count for the ith index, just set it to 1. such that pow(k ,i) is needed

    if any ith index is required and in bitmask if it is already set to 1, in that case you can't use it again simple print("NO"), return

    after iterating all over the index in array

    print("YES") , if not return

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why it is showing participants with rating more than 2100 in the official standing?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Select [Division 2] in top right

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Then also it is showing participants with rating mare than 2100 in division 1 official standing.

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        It was official contest for everyone but rated for only division 2.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What's wrong with my solution to C, i get runtime error?

  • »
    »
    2 years ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    please write the link of your solution in your comment.

    just erase break in line 43 and you will get accepted.

    after using break at that line, last of your current input used for next query and sometime result will be run time error.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Sorry i should've done that, and thanks for the help that was really dump

»
2 years ago, # |
  Vote: I like it +9 Vote: I do not like it

When will the editorials be released?

»
2 years ago, # |
  Vote: I like it +20 Vote: I do not like it

Please somebody tell the editorial releaser to do his job!

»
2 years ago, # |
  Vote: I like it +7 Vote: I do not like it

awoo when are the editorial gonna be published?

»
2 years ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

My solution for E: I did not have enough time to implement complete solution during the contest because I realized it after good amount of time.

So here it goes,finally minimum reduced sequence will have each element constituting some contiguous ranges of number. So for all ranges we need to figure out if that range could be reduced to a single number.Now here is a tricky part, if the range can be reduced to a single number?If we can do so, then frequency of all contiguous equal elements in the range must be a power of 2 or so, because it cannot be odd at any step of reduction or something like that.But the key point is, now we can greedily pick the elements and merge them using a stack, ie, push element to stack, merge top 2 elements of stack till you can and so on.So for each range check if the range becomes stack reducible and using a 1d dp, we can implement the rest of simpler part.

Edit : Time Complexity = O(N^2)

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

»
2 years ago, # |
  Vote: I like it +10 Vote: I do not like it

An off-topic question — can I undo an upvote made by mistake?

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Actually, both accounts are mines. For some problem, I submit that from my both account. I am really sorry and I ensure that this type situation will not be repeated.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

great round!!!! short statements and very combinatorics I wish every round were like this

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

When will the questions of the competition be put into the question bank?

»
2 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I would like to share another problem E's solution solving in $$$O(n^2)$$$.
Submission: 72874158
Without loss of generality, I assumed all numbers are combined to the right.
I changed dp[L][R]={can combine?, val} into three arrays, all of the indexs below are 0-based.
ans[i]: minimum length from $$$0 \text{~} i$$$
dp[i][k]: the minimum length if the $$$i$$$'th element was combined to $$$a[i]+k$$$, 0 represents it's unachievable
came[i][k]: if the $$$i$$$'th element was combined to $$$a[i]+k$$$, came[i][k] equals to the left boundary of this combination( aka. L in dp[L][R] and R represents $$$i$$$)

If the array is [7, 5, 4, 4, 6].
came[3][1]=1, dp[3][1]=3
came[3][2]=0, dp[3][2]=2, ans[2]=2
came[4][1]=came[3][2]=1, dp[4][1]=2
came[4][2]=came[3][2]-1=0, dp[4][2]=1, ans[4]=1
So the answer is ans[4]=1.

»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

why all winners are div1 participants??