BledDest's blog

By BledDest, 5 years ago, translation, In English

Hello everybody!

Today, on March 1st, 2020 the final round of Technocup olympiad for Russian-speaking high school students is held. The round starts at 13:00 Moscow time.

For those who want to compete on the same problems, we will host two Codeforces rounds: one for the first, and one for the second division. The rounds will start at 13:05 UTC, don't miss them! The round will start just after the onsite contest ends, so it can be postponed slightly if the onsite event timetable changes.

If you compete in the Final Round today, you can't compete in the Codeforces round #625.

The problems are prepared by MikeMirzayanov, Endagorion, tourist, Roms, vovuh, voidmax, adamant and me. Many thanks to KAN, AndreySergunin, antontrygubO_o, kuviman, MrPaul_TUser, Stepavly, artsin666, Pavs, AdvancerMan, Stresshoover, Peinot, geranazavr555, defolaut, nuipojaluista, cannor147, PrianishnikovaRina and Pavlova for testing the problems!

P.S. Because of the onsite contest, some Codeforces features may be disabled today.

Good luck!

UPD: The editorial is here.

Congratulations to the winners of the round:

Div1

1) ksun48

2) maroonrk

3) jijiang

4) Radewoosh

5) Um_nik

Div2

1) DraqonLore

2) DishonoredRighteous

3) 99824485311011

4) endbringer

5) cml

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

| Write comment?
»
5 years ago, # |
  Vote: I like it +106 Vote: I do not like it

Good luck with editorial this time)

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

Good luck everyone!

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

How many problems will be?

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

Who was the last year's winner ?

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

I believe the timing clashes with ABC 157.

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

How many problems there will be? And what's the score for each problem?

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

why The round will start just after the onsite contest ends?

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

So can we still hack in this round?

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

is this a rated contest?

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

    Probably not.

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

    All the rounds containing the name "Codeforces Round #XXX" are rated.

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

      you mean that the round on Mar.03 is not?

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

        Negation of RubenAshughyan's statement : -->Some of the rounds containing the name "Codeforces Round #XXX" are not rated.

        or

        -->Some of the rounds not containing the name "Codeforces Round #XXX" are rated.

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

There might be unethical and ugly behavior! Be prepared to downvote it!

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

will there be an interactive problem?

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

    At Technocup Final Round 2018 and 2019, there was no interactive problem. So probably ...

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

Hope there will be no online analysis of problems during the contest.

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

This contest is "Hello March 2020".

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

May I ask which features will be disabled?

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

Score distribution?

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

what's the score distribution?

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

    Maybe that is what the blog said to be disabled today :D

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

      it is said that problem setters and testers are very busy checking whether their problems are readable, their tests are strong enough etc, and also the score distribution (but I don't believe that :D )

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

Will the difficulty of this two contests equals to usual Div.1 & Div.2 respectively?

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

Two legends MikeMirzayanov and tourist have prepared this contest. It will definitely be a great contest. Thank you codeforces :)

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

as usual, these contests with suffix "based on ..." are always good.

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

Can I get ratting?

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

CF-visualiser doesn't work.

»
5 years ago, # |
  Vote: I like it -20 Vote: I do not like it

Why did administrator block my me ? Now I can't submit in the Round #625 QAQ

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

    P.S. Because of the onsite contest, some Codeforces features may be disabled today. (The last line of the blog post)

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

How to solve Div.1 C (Div.2 E) within TL?

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

    try fast io

    ios_base:: ...

    worked for me.

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

    You can sort them and compute the contribution of each one.Use binary search and segment_tree.

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

    Let's for each armor keep the balance you can achieve (initially it is -cb_i). Sort the weapons according to their attack modifiers, and process them one by one. Each time you process a weapon, add all monsters (also pre-sorted) with defense levels lower than current attack modifier. For each added monster with attack y_i, for all armors with defense modifiers > y_i add the reward for this monster (you can do this in a binary tree). Then just keep track of price of current weapon + maximum of balances for all armors, and remember the best sum.

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

      Just a little curious, why downvotes for all replies? Are they wrong or wtf happened here?

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

    Using lazy segment tree(range-add and range-max), which has 10^6 element

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

This is one of the most boring contests I've participated in.

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

    I wholeheartedly agree. Nothing interesting at all in ABCE (div1) and F almost made me rage quit. D had some potential but it was lost in a sea of boredom.

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

      What is wrong with F? (Except a quite long statement)

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

        A culmination of uninterestingness? Its statement aside, the task itself feels very repulsive to me. Maybe it would be even okay if it went together with some other problemset, but this felt like a "cherry" on the "cake".

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

How to solve Div-2 B problem? :)

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

    Each place can only be in a tour with other places that have the same value of j — b[j]. Just count the frequencies for each value of j — b[j] and output the highest one.

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

      This solution is beautiful. What thought process is leading to it? I mean how to come to "minus index" idea in the first place?

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 2   Vote: I like it +9 Vote: I do not like it
        $$$b_{i+1} - b_{i} = c_{i+1} - c_{i} \Leftrightarrow b_{i+1} - c_{i+1} = b_i - c_i$$$

        This implies that the $b_i-c_i$ values of all cities in a journey are equal.

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

        If you want to take (x1, y1), (x2, y2) then they belong to the same line with slope (y2 — y1) / (x2 — x1) since (y2 — y1) = (x2 — x1) then slope = 1 using line equation m * x + b = y since m = 1 then x1 + b = y1, x2 + b = y2. You can imagine x is the index in the array and y is the beauty.

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

    I dont know how to say but here it is

    Hint
    pseudo solution
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    for each element in the array we see what is its difference between its index and its value. because if some differences are equal then it means these elements can be used together as a possible answer. just like if the array was: 1 2 3 4 5 since each element's difference between its index and value is 0 they can all be used together to create an answer. map each possible difference and the map's answer would be the sum of all of these values. then print the maximum answer by iterating over the map.

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

    create a array "ans" of size n and intialise it to 0. and also define a map<int,int>mp iterate form 0 to n if the value of a[i]-i not exist in map then ans[i] updated to a[i] and if it exist then update the value of ans[i]=a[i]+ans[mp[a[i]-i]. and also update mp[i]=a[i]-i every time Now print the maximum value of ans.

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

Thanks for the contest <3

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

      Oh, thanks <3

      Is that O(n * k) solution where k = 26 ?

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

      sorry my solution is wrong (i got wrong answer) :(

      i don't know the correct solution

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

        Your idea is correct, probably just an implementation issue

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

    I solved C this way: while there is symbol that can be deleted, I check for all symbols how much symbols going in the alphabet after this symbol is in string(let it be help), and then delete symbol with smallest help.

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

      I did the same but still got WA on pretest 4. Curious to know what went wrong once the test is released! 72197623

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

        i can't see the submission :(

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

        You are not checking edge between path[i — 1] and path[i] before updating max_routing number value in the else part.

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

          No, that is not the reason. I am failing in the 4th test case which has answer is "3 3" where as I output "5 5". The else part just increases the max_builds, it should not effect the min_builds

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

            Another Error which is causing wrong min_routing(and max_routing as well) is that you are comparing dist[path[i]] with K — 1 — i but instead it should be compared with (dist[path[i-1]] — 1). If both are not equal, only then we should increase min_routing.

»
5 years ago, # |
  Vote: I like it -8 Vote: I do not like it

why does even second question of div2 have such hard time contrainst and test cases( tc 8)??

i skipped all repeated elements still it contains test cases where worst case give n^2, case where all elements are different and not included in any series.

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

    include<bits/stdc++.h>

    using namespace std; int main() { int n; cin>>n; int a[n]; for(int i=0;i<n;i++) cin>>a[i]; int ans[n]={0},maxa=0; for(int i=0;i<n;i++) { maxa=max(maxa,a[i]); ans[i]=max(a[i],ans[i]); for(int j=i+1;j<n;j++) { if(a[j]-a[i]==j-i) { ans[j]=max(ans[j],ans[i]+a[j]); } } } for(int i=0;i<n;i++) maxa=max(maxa,ans[i]); cout<<maxa; } I think this solution is good.

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

      You should use

      The Spoiler

      to show your code

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

        In fact I kinda like the first line. So bold and confident with what you should include.

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

Can anybody suggest me what the test is like in test 4 of problem D div 2. :<

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

    Me too, WA on test4 countless times :(

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

    Think is something like

    test

    Because when i solved that, it was WA on test 5

    Then i looked at

    test

    And when i solved that, it was AC.

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

      Are the answers on your tests are 1 1 and 1 2?
      My solution outputs this answers and still fails in Test 5. 72205820
      Don't know, if it was intended, that Test 4 and Test 5 contents are hidden.

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

        We can't see others' submission in this contest. Please try another way to show your code.

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

        A very stupid mistake was found, finally AC.

            for (size_t i = 0; i < k; i++) {
              const size_t v = p[i];
              const size_t currMinDistance = distances[v];
          
              bool canRebuild = false;
              bool mustRebuild = false;
              if (isAmbigous[v]) {
                canRebuild = true;
        -     } else if (i + 1 < k) {
        +     }
        +     if (i + 1 < k) {
                const size_t nextMinDistance = distances[p[i + 1]];
                if (nextMinDistance + 1 != currMinDistance) {
                  canRebuild = true;
                  mustRebuild = true;
                }
              }
              if (canRebuild) {
                maxCount += 1;
              }
              if (mustRebuild) {
                minCount += 1;
              }
            }
        
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for your data, even though I also made another stupid mistake :(

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

Pls help how to solve D div 2 (B div 1)

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

Is it only me that E was straightforward and D was undoable?

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

    I just read E after the competition after being stuck at D, and immediately regretted not doing so earlier. I reckon the main reason D is solved more is just the (questionable) order.

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

    For me it's the opposite shrug

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

How to solve Div 1 C?

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

    You can read the comment above.

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

    it seems that creating events for the second stuffs and the third sorting by their first entry and using segment tree to maintain the answer is enough for this task. (Though it may involves some details I guess)

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

About problem D1C. I came with this approach. First use only useful weapon and defense. (Higher attack cost more money). Then sort all monsters on their defense and lets add them one by one. When we are adding monster we should increase our attack to kill him, and find minimal needed defense to kill him(using upper bound). Then for all defenses higher then found we will get reward for him also. Lets maintain segtree on the array $$$a$$$, where $$$a_i$$$ = amount of money you get using i-s defense item. Firstly $$$a_i = -d_i[cost]$$$ Then when adding a monster k we add $$$z_k$$$ on the segment $$$[pos, m - 1]$$$ (pos is minimum defense needed). And update ans. So the question is, has someone submitted solution using same approach? Or whats wrong with this approach? Code: https://pastebin.com/jZyVajPi

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

How to solve problem D div2?

pls give me sone hint....

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

    Dijkstra(O(mlogm)) Count the number of minimum paths as well.

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

    When standing in an intersection a, if the direction ploycarp is going, is not on the shortest path within the neighbours of a to the work, then we have to rebuild no matter what. If the shortest path from the way polycarp is going is the shortest path within all paths from neighbours of a to work, then if there are no other paths as short, we dont need to rebuild, and if there are other paths as short, then the maximum number of rebuilds should go up by one, but the minimum should stay the same

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

It's quite weird that my solution can't pass sample test(Runtime error), since it passes sample test on my laptop, and I didn't do anything may lead to RE. (Since I have a WA 3 submission)

And when I just changed my modulo, and it passed sample test, but get RE on test 2.

72201472 72202006

Can anyone explain why?

Here are my many other submissions:

Link

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

    ppow has maxn size, which is 2e5+7. And on line 99 you run loop on 4e5 elements, so it is out of bounds access to array. You can easy catch such errors if you compile your code with -fsanitize=address

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

      Thank you!

      It seems that I have never gotten rid of those stupid mistakes :(

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

Thanks mr. Endagorion for letting this problem from your past contest into this contest.

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

    What's the same?

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

      div1E, it's not 100% the same but after building the virtual tree it's trivial.

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

        It's not the same problem, it's the same technique. I'd argue it's not interesting and doesn't deserve to be an E, but it's definitely not the same problem.

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

          Agree with Encho, it's just the same technique.

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

          Fair enough, I don't remember what the problem is about. For me this problem all about the technique and the rest is not important/easy.

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

        It is trivially similiar.

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

    Ugh, I would definitely not call it the same problem. Compressing the induced tree is very common trick and that is basically whole intersection of solutions.

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

    I don't see how this is the same problem as E.

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

why the system tests didn't start ?

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

How to solve div1 D?

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

    You can remove "11" substring. Then reduced strings should be the same.
    To find a reduced string of a substring I used rolling hash along with the segment tree.

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

      Why this is enough?

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

        You can imagine that '0' stands for a coin and '1' stands for an empty position. So for each move, a coin is moved across two empty positions backward or forward. In this move, for every two adjacent coins, the parity of distance between them will not change. So you can keep moving the coins to the left, and finally you will find the sequence that no two adjacent coins have a distance greater than one. That's the same as the result of removing all '11' substring.

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

Why can't I submit a task during system testing?

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

How to solve div2 E (div1 C)?

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

    Sort armor by incresing b. Create segement tree and update it with -cb for every armor piece.

    Then do a sweep on monsters(by their x) and weapons(by their a):

    • if current event is weapon, update solution to sol = max(sol, -ca + (max element in segment tree))

    • else find first armor set with b > y (denote it as pos) and update interval [pos, m - 1] in segement tree with +z

    You can implement additions in segement tree with lazy propagation, and finding first armor set with binary search or lower_bound

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

I can't seem to understand why am I getting RE in [problem:https://codeforces.me/contest/1321/problem/A] on pretest 5.

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

    We cant read your code now.

    Use this `Spoiler`
  • »
    »
    5 years ago, # ^ |
    Rev. 5   Vote: I like it 0 Vote: I do not like it
    //if it is test case 5 then you have divide by 0.
    //for example may be you have calculated 
    int count_r = if(r[i] == 1 && b[i] == 0);
    int count_b = if(r[i] == 0 && b[i] == 1);
    and for answer you may have done 
    cout << (count_b/count_r) + 1;
    //here count_r can be zero 
    
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh yes! Can't believe I didn't think of that case. :/

      Thanks!

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

        i wasted nearly 20 min looking at my code and then looked at the result and released it was runtime error rather than wrong answer :(

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

How to solve div2 B?

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

    Let's say you want to go from $$$i$$$ to $$$j$$$ such that $$$i < j$$$.

    The given condition is that $$$j - i = b[j] - b[i]$$$

    So rearranging that: $$$j - i = b[j] - b[i] \Leftrightarrow$$$ $$$ j - b[j] = i - b[i]$$$.

    So now for every equal value of $$$i - b[i]$$$, get the maximum sum of all $$$b[i]$$$ (you can do that using a map).

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

Hi! The tests, practice and some functionality are hidden because of the onsite event. We will open it after the official award ceremony in Moscow. Please be patient a little!

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

It's possible to have O(log) in div1 D only because of one modular division (and have no segment trees at all).

We know that we can move two adjacent ones. Due to the statement, we can swap them with an adjacent zero and of course, we can imagine swapping them with an adjacent one.

So, when we have a string, let's imagine turning it into its canonical form — let's pull all the pairs of adjacent ones to the left: 011101111010->111111010010. This new string has a prefix which consists of an even number of ones and then some suffix which has no neighboring ones (but can start with a one).

As we are asked if two string of the same length are reachable from each other, we can assume that we want to compare only these two suffixes. If these two strings have different number of mentioned pairs, then the suffixes will have different lengths, so we'll know that they are not reachable from each other. If the suffixes have the same length, we'll just compare them as strings.

So, we need some hash function, which will "skip" adjacent pairs of ones. I'll use linear functions as the hashes of zeroes and ones, let's call them $$$f_0$$$ and $$$f_1$$$. The hash of a concatenation of two strings will be the composition of the two functions. The only condition is that $$$f_1(f_1(x))=x$$$ must hold for every possible $$$x$$$. Let's then set $$$f_0=random \cdot x+random$$$ and $$$f_1=-x+random$$$.

The composition is associative, so we can calculate the composition for every prefix and then calculate the function for an interval with one modular division.

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

    I think you can calculate more straightforward hash for each prefix, for example, consider a string: the number of ones modulo 2 before the fixed zero. And after that you should binary search for each query, to find the set of zeroes. Then you should check that two substrings are equal (or check that one substring is inverse of another one, if parity is different).

    Also you can change binary search to some straightforward linear time precalc, and solve the problem in linear time.

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

      Yea, there are different solutions, but I think that mine is quite educational, so I've described it.

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

    It is possible to have O(1) in div 1 D.

    I couldn't find the observation that we need to remove pairs of 11 during the contest. Instead of it, I found other pairs of observations:

    1) numbers don't change the parity of their positions

    2) If one zero was before another zero, they should store the order.

    It is actually identical to removing 11.

    But these lead to the solution, that because the number can change their position, but can't change the parity of position. Let's just compare the parity of positions where zeros are located.

    101011 -> 2 4 -> 0 0

    010111 -> 1 3 -> 1 1

    Now let's just remove all ones from the initial string, and just store the parity of positions of zeros. And build hash over this string.

    To answer query just compare hashes of this new string in compressed positions. To solve the problem of different parity of initial start, we need to build hashes of two string, where second just inverse of first.

    I had O(log) just to find the position of beginning new interval in the compressed string. But it can be done in O(1) with O(n) preprocessing just store position of start for each index.

    P.S. my code is a bit messy, because I wrote another solution and only then added this idea. Better refer to the text.

    72206443

    Better version of code here -> 72212662

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

      Do you have a solid proof for why just comparing parities of zero positions works?

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

        Yes, I would try to explain.

        it can be easily transformed into removing 11 and comparing the rest of the string by equality.

        What information we are losing, the pairs of 11 between zeros. Because removing 11 didn't change the parity of positions.

        0110 -> 0 1 and 00 -> 0 1

        But as it was described above it is redundant information, it didn't change anything.

        Then we can lose some lonely ones :

        010 01010,

        But actually we are not losing because knowing the parity of two consecutive zero, we can understand if it was 1 between them

        010 -> 0 0

        00 -> 0 1

        0010 -> 0 1 1

        000 -> 0 1 0

        So storing the parity of zero's position is the same as storing the whole string of 0s and 1s (where there is no two consecutive 1)

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

    Yep, one of solutions we had for this problem works in a similar manner, but we substitute $$$0$$$ and $$$1$$$ by some matrices $$$A$$$ and $$$B$$$ such that $$$B^2=k \cdot I$$$ for some number $$$k$$$ and unit matrix $$$I$$$. We check that matrix products on corresponding segments are equal, which may be done in $$$O(1)$$$ per query with a bit of prefix and suffix products. You may also solve this problem in a similar manner.

    Though I still think that one should solve this problem in a deterministic way.

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

    Hey! Don't quite understand how to "inverse" the prefix for the substring in that case. So, as I understand $$$ prefix_i = f_{s_i}(prefix_{i-1}) $$$. Having that, we need to take $$$prefix_r(prefix_{l-1}^{-1}(0))$$$ and this requires to maintain the polynomial. Probably I got it wrong. Could you elaborate please on that?

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

    Really cool! Do you know how to reason about the probability of error?

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

did anyone think to solve C div 2 using 0/1 dp? i was trying to solve it like knapsack but didn't get it right..any suggests will be highly appreciated

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

    For C you could've just used basic greedy solution that uses bfs. Just try some cases and see that greedy solution works all the time and try to implement it with bfs.

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

    remove biggest possible option until you run out of options.

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

    Using knapsack DP is invalid because your state has to indicate which indices have been deleted (using bit-masking or similar) which can't be done given that the size is 100, same principle applies to back tracking or any permutation technique I can think of.

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

Achievement unlocked: Place last in a Codeforces round

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

round is rated or not ?

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

shit! I misread the sentence is div.2 C. Because the title contains the word "Adjacent" I thought it is allowed to remove character not only the adjacent in position but also in the alphabets. I am so sad.

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

    Me too :(

    But any idea on how to solve this version of the problem?

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

      What I tried to do is firstly devide-and-conquer approach: If we know range [l,r) is deletable then l-1 and r becomes adjacent now and may be deletable. Secondly, I thought it is graph something. The alphabetical adjacency can be expressed as graph and it is obvious that at some moment, a node with degree one should be higher priority than those with higher degrees. After these thinkings however, I couldn't find the way out. Regret is that I should test the sample 1 so I could find myself misunderstood the problem sentence.

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

one of the weirdest and most boring rounds I've ever participated . I hope next round will be more exciting and fun XD

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

    For me the problems where not that bad. The fact that others solved them much faster than me was :/

    However, I think Div2 B and C where kind of math problems, since once the key observation is clear, it is more or less trivial implementation.

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

When will ratings get updated?

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

cool and nice div1 contest :)

»
5 years ago, # |
  Vote: I like it -8 Vote: I do not like it

My (correct) div2 D solution timed out using py3 in post contest tests but when I resubmit I pass based on random variation in timing... Anything I can do or is it just what I get for using python?

»
5 years ago, # |
  Vote: I like it -8 Vote: I do not like it

why im getting runtime error and tle at test case 5 of div2 A..?

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

How to solve Div 2 Problem C: "Remove Adjacent" ?

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

    I did this. submission

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

    I started at the maximum value in the string and kept deleting elements before and after it until I there are no elements which satisfy the given condition and do it all over again while decreasing the maximum value. I hope that makes sense.

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

Where can I find Editorials of these questions..?

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

Became a Candidate Master ~ Happy happy day >__<!

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

Final round rated?

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

Ummmm..... I cannot find the solution, editorial please help me

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

The pretests in this contest is too weak :( I have dropped my rating because of this too many time. I hope this is the last :(

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

When will be the editorial?