By pikmike, history, 8 months 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 Ne0n25 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 kefaa2 7 135
2 MiFaFaOvO 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 MiFaFaOvO 0:33
G gisp_zjz 0:31

UPD: Editorial is out

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

»
8 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Good luck everyone!

»
8 months ago, # |
  Vote: I like it -47 Vote: I do not like it

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

  • »
    »
    8 months 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

    • »
      »
      »
      8 months 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).

      • »
        »
        »
        »
        8 months 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

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

    thanks for the information :(

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks a lot..pikmike

»
8 months 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.

  • »
    »
    8 months 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.

»
8 months 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.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Seems more like a Speed Test.. XD

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

thanks for so many upvotes :)

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

.

»
8 months ago, # |
  Vote: I like it -9 Vote: I do not like it

Hope to get blue today!

»
8 months 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?

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the imaginary scoring distribution

»
8 months ago, # |
  Vote: I like it +55 Vote: I do not like it

»
8 months ago, # |
  Vote: I like it +14 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it -27 Vote: I do not like it

speedforces

»
8 months 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

»
8 months 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

  • »
    »
    8 months 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;
    }
    
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it -28 Vote: I do not like it

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

      • »
        »
        »
        »
        8 months 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.

        • »
          »
          »
          »
          »
          8 months 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

      • »
        »
        »
        »
        8 months 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?

        • »
          »
          »
          »
          »
          8 months 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.

»
8 months 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)

  • »
    »
    8 months 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 ((

  • »
    »
    8 months 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?

  • »
    »
    8 months 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?

    • »
      »
      »
      8 months 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.

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

    [Deleted]

»
8 months ago, # |
  Vote: I like it +6 Vote: I do not like it

How to solve E?

»
8 months ago, # |
  Vote: I like it +4 Vote: I do not like it

How to solve D problem?

  • »
    »
    8 months 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)$$$.

    • »
      »
      »
      8 months 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?

      • »
        »
        »
        »
        8 months 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.

      • »
        »
        »
        »
        8 months 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.

        • »
          »
          »
          »
          »
          8 months 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

    • »
      »
      »
      8 months 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)
      
    • »
      »
      »
      8 months 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`

      `

      • »
        »
        »
        »
        8 months 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).

    • »
      »
      »
      8 months 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.

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

        The correct way to do division is using modular inverse.

    • »
      »
      »
      8 months 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.

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

      Helped alot!! Thanks.

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

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

  • »
    »
    8 months 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}$$$.

»
8 months ago, # |
  Vote: I like it +1 Vote: I do not like it

What was test case 4 of problem C??

»
8 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    8 months 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 ).

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

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

      • »
        »
        »
        »
        8 months 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.

»
8 months 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?

  • »
    »
    8 months 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.

»
8 months 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

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

    Whether AMAX matters a lot?? I pass the pretests in O(n^3) .

»
8 months 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?

  • »
    »
    8 months 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.

    • »
      »
      »
      8 months 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).

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

I found G much easier than E and F

  • »
    »
    8 months 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.

    • »
      »
      »
      7 months 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.

  • »
    »
    8 months 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?

»
8 months 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

»
8 months 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;
}
»
8 months ago, # |
  Vote: I like it +4 Vote: I do not like it

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

  • »
    »
    8 months 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
»
8 months 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 :-(

»
8 months ago, # |
  Vote: I like it +15 Vote: I do not like it

No Screencast? tmwilliamlin168

»
8 months 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?

»
8 months 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.

»
8 months 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 ?

  • »
    »
    8 months 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

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

    Try 1 1 1 2

  • »
    »
    8 months 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.

»
8 months ago, # |
  Vote: I like it -14 Vote: I do not like it

SpeedForces.

»
8 months 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

  • »
    »
    8 months 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.

    • »
      »
      »
      8 months 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}$$$

      .

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

    i did the same

»
8 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Missed E by 2 minutes

»
8 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    8 months 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.

»
8 months 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.

»
8 months 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).

  • »
    »
    8 months 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 :)

»
8 months 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.

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

    Apparently, to get 3 you need to type 'i', 'q' and then use autocompletion

»
8 months 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.

  • »
    »
    8 months 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.

    • »
      »
      »
      8 months 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

      • »
        »
        »
        »
        8 months 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 :)

        • »
          »
          »
          »
          »
          8 months 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.

»
8 months 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 :((

»
8 months ago, # |
  Vote: I like it +11 Vote: I do not like it

What is Unexpected verdict in Hacks?

»
8 months 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

»
8 months 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.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    yes same here

  • »
    »
    8 months ago, # ^ |
    Rev. 3   Vote: I like it +1 Vote: I do not like it

    because maybe the checker itself fails for that test case like some sort of TLE or RE.

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

    Try to hack it for multiple number of test cases(more than 1)

»
8 months 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

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

    Could you please explain your solution

  • »
    »
    8 months 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?

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

      No, I don't know the proof

    • »
      »
      »
      8 months 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.

    • »
      »
      »
      8 months 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...)

»
8 months 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

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

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

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

      No Its not Russian.

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

        YPFARROLCS obviously means sexy llama in Russian

        • »
          »
          »
          »
          »
          8 months 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

    • »
      »
      »
      8 months 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

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

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

»
8 months 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.

»
8 months 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.

»
8 months 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.

  • »
    »
    8 months 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)

  • »
    »
    8 months 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 ?

    • »
      »
      »
      8 months 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.

»
8 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Can anybody suggest similar equation-finding problems as D.

  • »
    »
    8 months 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.

»
8 months 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?

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

Hack my C if you're cool

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

On E Will time n^3 hack?

»
8 months 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.

»
8 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Why are so many solutions for C failing?

»
8 months 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

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem E ?

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can sb hack my C?

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem D ?

  • »
    »
    8 months 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}$$$

»
8 months 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

»
8 months ago, # |
  Vote: I like it -7 Vote: I do not like it

Can anyone hack my C ?

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem D? Explain please

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

there should be marks for successfully Hacking.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I wonder if there is any official editorial or somrthing

  • »
    »
    8 months 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.

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

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

  • »
    »
    8 months 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

»
8 months 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?

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

    Select [Division 2] in top right

    • »
      »
      »
      8 months 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.

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

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

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    8 months 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.

    • »
      »
      »
      8 months 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

»
8 months ago, # |
  Vote: I like it +9 Vote: I do not like it

When will the editorials be released?

»
8 months ago, # |
  Vote: I like it +20 Vote: I do not like it

Please somebody tell the editorial releaser to do his job!

»
8 months ago, # |
  Vote: I like it +7 Vote: I do not like it

pikmike when are the editorial gonna be published?

»
8 months 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)

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it +10 Vote: I do not like it

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

»
8 months 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.

»
8 months 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

»
8 months 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?

»
8 months 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.

»
8 months ago, # |
  Vote: I like it +5 Vote: I do not like it

why all winners are div1 participants??