Zlobober's blog

By Zlobober, 13 months ago, translation, In English,

Hi everybody!

Tomorrow at 09:35 UTC there will be Codeforces Round #376 that is dedicated for the second division. At the same time there will be a Moscow School Team Olympiad, and, as a nice tradition, we bring you a CodeForces round based on its problems. Unfortunately, this time we weren't able to come up with a good problemset for a first division contestants, but, as usual, we invite first division to participate unofficially in this round.

Problems were prepared by timgaripov, platypus179, wilwell, Flyrise, ipavlov and gritukan under my control. We would like to thank members of jury of the Team Olympiad: Endagorion, Helen Andreeva and GlebsHP, who also works as a coordinator from the CodeForces side. Also we are very grateful to MikeMirzayanov for a Polygon system that makes problem preparation and coordination of many involved people much simpler, and for a great CodeForces community that we are all part of.

We suggest you 6 problems for 2 hours. Good luck!

UPD The contest is over, results are final, thanks for participating! The editorial will be published later

UPD2 I'm sorry for an editorial delay. It's finally available here.

Congratulations to contest winners:

  1. DmitryBelikov
  2. ljsss
  3. kehKeLenge
  4. dilsonguim
  5. AC_is_ZQC
 
 
 
 
  • Vote: I like it  
  • +226
  • Vote: I do not like it  

»
13 months ago, # |
Rev. 3   Vote: I like it +61 Vote: I do not like it

An automorphic Round (376)

376 * 376 = 141 376

»
13 months ago, # |
  Vote: I like it -32 Vote: I do not like it

Am I the last AC submission ?

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

Most of the schools are open at that time in Iran (and maybe other countries) :(

Missed four consecutive rounds just for the unusual time :(

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

    There would be people who have missed the usual timing rounds because it is "unusual" for them .

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

      I wanted to downvote this, but upvoted instead :p

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

        unusual comments.. unusual comments everywhere

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

      I think there can be a time dicipline all people have usual time!

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

    It's your choice to live in Islamic country

    People believing in Jesus are free at Sundays

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

      you don't have to be rude !

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

        I didn't want to. Just pointed out how ridicilous is this argument, considering the fact that in most countries Sundays are holidays.

        It's impossible to fit in every schedule. That's why contest time changes. To fit other's schedules.

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

          I don't think " People believing in Jesus " is just pointing out !

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

            Actually I don't care much about what you think

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

              Actually you don't have to be rude at all

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

                If truth is too rude for you go meet with your therapist, you have plenty to talk about.

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

      there are too many christians in the middle east and the islamic countries -_-

      Not racist.

      • »
        »
        »
        »
        13 months ago, # ^ |
        Rev. 2   Vote: I like it -25 Vote: I do not like it

        Poor people...

        Also I didn't figure out how is racism relevant here. At my memory religions only fuels it, don't they?

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

      Codeforces should ban all the racist people, whatever their color is.

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

Am I the only one feeling tired of reading comments like "Unusual is the new usual"?

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

    you're not the only one. i can relate to this.

»
13 months ago, # |
  Vote: I like it -156 Vote: I do not like it

downvote me plz

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

I hate this new usual time :(

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

Most of the Middle East universities are open in this time :'(

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

Did anyone notice a sudden increase in contribution points? My contribution went from -30 to -3 in less than 3 days, without any wave of new upvotes.

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

In contest invitation mail Zlobober isn't legendary!

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

The time is very good for Chinese competitor.

But it is a pity that the beginning time of this round is just the ending time of Dalian regional contest.

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

In the registrants list, Div. 1 participants are not marked as unofficial participants. Is that normal?

Update: it's fixed, actually.

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

why div 1 participants are not unofficial ?

Update : fixed

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

    What part of "Unfortunately, this time we weren't able to come up with a good problemset for a first division contestants" do you find hard to understand?

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

The round starts 1.5 hours after Google APAC 1D ends.

Will have to eat quickly, rest in that time and be ready for the round. :D

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

    Oh boy, I literally dieded.

    I almost reached rank 200, but my computer hung at the last second and it costed me 16 points. Shouldn't have submitted the code after the contest, that was freakin painful.

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

      Sorry to hear that you literally dieded.

      Rested in peace.

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

Love the timing of recent contests. Usual timing is 2am for me, so am happy to actually be able to participate in a few contests.

But I understand that others may not agree :)

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

I'll join. It's my first time.

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

Why do rounds these days occur at this unusual time?

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

score distribution?

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

Ok :)

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

6 problems for 2 hours.Hopefully problem set will be easy at least 3.

Best wishes everyone.

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

10 minutes Late:)

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

Start delayed! How unusual!

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

Score distribution?

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

Why Delayed ?

»
13 months ago, # |
Rev. 3   Vote: I like it +29 Vote: I do not like it

I just don't get what is this problem which happens right in the begin of the contest and can be fixed in 10 minutes !

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

could some one say problem B more clear ? ! i cant understanr it : ( pleaseee ...

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

is it possible for sereja not to order any pizza on someday in 2nd problem

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

Problem B, Could He uses both coupons and discount at same time? like if it is 50 pizza, could he use 48 coupon and 1 discount?

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

    Well for B, you can use discount only if you are buying 2 that should solve it :| explanation sucks

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

    If he should buy 3 pizzas, he can buy 2 pizzas with discount and 1 pizza with coupon.

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

My submission for D is in queue for 5 mins. Still waiting.

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

Am I the only one feeling tired of reading comments like "Unusual is the new usual"?

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

    Am I the only one feeling tired of reading repeated comments like this in each contest blog ?

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

i hacked on F with complexity n*n for n=10^5. It failed ! Does the new server support 10^10 ??
Edit: Got it ! My test case wasnt good enough !

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

How to solve C?

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

    Hint: think about DFS

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

    dsu i think

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

      I too thought of dsu, but it kept failing at pretest 5. Any reason why it might not work

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

      Can anyone illustarate smooth dsu solution

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

        build a graph with undirected edges from each l[i] and r[i].now socks at indices l[i] and r[i] must have same color.now use dfs to find the connected components.its just like a normal dfs on undirected graph with edges from l[i] to r[i].each connected component should have same color.after finding components,for each component find the color which exists the most number of times and paint all other socks with this color.this minimizes the required number of paintings.for reference you can see my code.21497227

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

          Damn, I spent about 1.5 hours on this problem and couldnt solve it. How do you guys think up these solutions? I understand it, and it is quite simple, but why does it actually work? "find the color which exists the most number of times and paint all other socks with this color.this minimizes the required number of paintings" — I understand that sometimes you just see the pattern and cant prove it, but how to see this pattern... :( I failed many problems just not being able to see the pattern. How can I improve this skill? Thanks in advance

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

            me too couldn't solve it during contest and i realized it later. I think it all comes with practice.

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

              I hope so. ) Thanks for your reply.

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

            From my practice experience, whenver I think of a strategy in a scenario I go through steps like this:

            1. Come up with preprocessing ways that helps you analyze the situation.

            2. If it's a game then most of the time it is minimax considering it is the most frequent one that pops up.

            3. Go for greedy, enumerate a few test cases that I think that could be tricky to handle. If greedy still works, then go for it.

            4. If not, see if there is a dynamic programming relation between the states. Go for dp if it is available.

            5. If there is still no solution, then you are probably missing some major observation. Dig deeper into the sample cases for inspirations. Also check if the constraints are small enough for more naive solutions to pass.

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

              Thank you a lot! I will try to use this strategy in practice.

  • »
    »
    13 months ago, # ^ |
    Rev. 4   Vote: I like it +6 Vote: I do not like it

    Build a graph like this : If you have socks l[i], r[i], then add undirected edge from l[i] to r[i]. Now for each connected component in this graph, you must have 1 color. So we can solve each component independently. It's optimal for each component to change colours of all nodes in that component to the colour that appears the most in that component.

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

      I used DFS....as u said.. But someone hacked me.. How? here is my solution solution

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

        for(i = 1 ; i <= N ; i++){ if(visited[i] == 0){ for(j = 1 ; j <= K ; j++) countcolor[j] = 0; _max = 0; ll v = dfs(i); ans += (v-_max); } }

        It works only with a few components count. I guess if theres maximum N and M — min, for instance 1, this would be N*K, while N = 2*10^5 and K = 2*10^5, which is TL, obviously.

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

        you are looping through color array every time.here your worst case will be N*K.instead just use a map and you can clear the map every time you run dfs.

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

          shit.... This simple thing !!! I should have thought of that

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

    Consider socks as nodes and pairs as edges. Now in this graph,paint each component with the color which have highest frequency in that component.

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

      Could you tell me how to find the highest frequency in a independent component ?

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

    For input
    5 3 5
    1 1 3 4 5
    1 2
    2 3
    4 5

    You can split all the socks into groups (sets):
    S1 = {sock1, sock2, sock3},
    S2 = {sock4, sock5}

    All the socks in group S1 should be painted in a single color and all the socks in the group S2 should also be painted in a single color (probably, different from the color of S1).

    For the group Si we count the most frequent color among the socks and paint all the rest socks in that group to that color. In my example the socks in the group S1 have following colors:
    S1 = {black, black, red}

    The most frequent color in group S1 is black, so we paint the remaining sock (which is red) to color black. After repainting the set will look like that:
    S1 = {black, black, black}.

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

How to solve F?

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

    Maybe you have to learn how to solve A and B, too early for F ..

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

      It seemed interesting, because for small constraints it works but I got TLE for large ones which means I was doing something really wrong. So I am interested in learning.

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

      Lets not judge just by looking at color of handle :)

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

    I used some prefix array to know in O(1) time how many graphic cards are there with power from i to j.

    Then for each available power of graphics, for example for power 2, i was checking prefix array every 2 (2,4,6,8) and i was increasing max result for this power by (cards in this interval)*(current value/power i was checking(2) ).

    O(nlogn)

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

    Consider every distinct tape as the leading tape and calculate the answer for this using sieve-like technique. Consider tape a[i], then all elements in range i*a[i] to (i+1)*a[i] will be added as i*a[i]. Number of elements between a range can be calculated using a precalculated array since the numbers are less 10^6.

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

please explain C I tried to do it bfs but it doesnt seem to be like that

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

    I did it using bfs, i made disjoint sets, and tried to find out the most repeated color in each disjoint set, and subtracted that value by size of the disjoint set.

    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it -30 Vote: I do not like it
      #include <stdio.h>
      #include <map>
      #include <queue>
      #include <memory.h>
      using namespace std;
      int n, m, k;
      int color[300000];
      map<int, map<int, int> > tree;
      map<int, map<int, int> > sorted;
      int index[300000];
      int index2[300000];
      int visited[300000];
      int cnt[300000];
      int ans, p;
      
      void bfs(int col, int s)
      {
          queue<int> q;
          q.push(s);
          int i;
          while(!q.empty())
          {
              int now=q.front();
              visited[now]=col;
              sorted[col][index2[col]++]=now;
              q.pop();
              for(i=0; i<index[now]; i++) if(visited[tree[now][i]]==0) q.push(tree[now][i]);
          }
      }
      
      int main()
      {
          freopen("input.txt", "r", stdin);
          scanf("%d%d%d", &n, &m, &k);
          int i, j;
          for(i=0; i<n; i++) scanf("%d", &color[i]);
      
          for(i=0; i<m; i++)
          {
              int l, r;
              scanf("%d%d", &l, &r);
              tree[l][index[l]++]=r;
              tree[r][index[r]++]=l;
          }
          int cur=1;
          for(i=1; i<=n; i++)
          {
              if(visited[i]==0)
              {
                  bfs(cur, i);
                  cur++;
              }
          }
          for(i=1; i<cur; i++)
          {
              memset(cnt, 0, sizeof(cnt));
              p=0;
              for(j=0; j<index2[i]; j++)
              {
                  printf("%d ",sorted[i][j]);
                  cnt[color[sorted[i][j]]]++;
                  if(p<cnt[color[sorted[i][j]]]) p=cnt[color[sorted[i][j]]];
              }
              ans+=index2[i]-p;
              printf("\n");
          }
          printf("%d", ans);
      }
      
      

      this was my code, when i realized that it fails sample test 2 please help me what is wrong?

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

        Can u copy send link to your solution instead of copy code ? This seem inconvenience. sory fo my bad E =)

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

    BFS works fine. The input is just not usual. For example, the input li = 10, ri = 42 may be repeated:
    10 42
    ...
    10 42

    this may lead you to insert 42 into adjacency list twice:
    adj[10].push_back(42);
    adj[10].push_back(42);

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

      That's why i prefer map<int, set> for adjacency list.

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

Was anyone else facing problems with opening the site? I couldn't open the site for half an hour during contest.

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

How did people use graph solution for problem C? What if graph is really dense ? It should go out of memory..

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

What is wrong with following approach for D? It gets WA on pretest 5.

Toposort the letters keeping in mind the word constraints. Check for cycle, if so print -1. Also check all nodes in graph are connected. If this is ensured, sort the toposort and check if it is possible at some level to break the sequence into two parts such that they are x, x + 1, x + 2, ...n - 1 followed by 1, 2, 3, 4...., x - 1. Submission: 21492973

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

Was F easy or there are some tricky cases waiting in system testing

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

I will fail b because I declared N to 1e5 and not 2*1e5, horrible mistake but I'm wondering why pretest doesn't cover such case!

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

    Are you sure it was 2*1e5?

    E: :( It was, I thought the max no of elements for A was 10000 but that was for Ai

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

Very interesting round to me !

I saw a lot of random solutions for F and some greedy for E... It will be a lot of WAs.

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

Can F be solved with a fenwick tree, and summing contents of the intervals between each power? I think that is O(n (log n)^2), is that fast enough?

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

    You could use prefix sum from reverse to get the same and hence reduce a logn factor

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

    Oh wait you can just compute the prefix sum. That makes sense.

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

    my O(n log(n) ln(n)) solution passed. so I guess O(n log^2(n)) is fast enough.

»
13 months ago, # |
  Vote: I like it -6 Vote: I do not like it

How to solve F?

I noticed that the main card should be a prime, or 1.

Then I wrote a sieve and a map to insert a number along with its index (in sorted input) in the map for each of its prime factors.

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

    For each i, iterate over its multiples. If you are currently at x*i, all the numbers in the range [(x-1)*i, x*i) will have to be reduced to (x-1)*i. So, simply add the count of numbers in this range * (x-1)*i to current ans. Repeat for all i, and take max of these.

    Code

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

    why should the main card be prime ?

    Case :

    4

    4 6 12 36

    main card : 4

»
13 months ago, # |
Rev. 4   Vote: I like it +9 Vote: I do not like it

D was really interesting. I got AC it using BIT. First of all, ans can be in range [0, c - 1]. For every successive interval, I found what intervals can lead to correct sorting order(handled by L and R), and what intervals cannot(handled by BIT). I maintained the interval [L, R] that contains the answer, and also BIT stores what index cannot be our answer. Finally, for any L ≤ i ≤ R, if BIT allows this to be an answer, print it. Otherwise answer doesn't exists.

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

    But you got WA on system test 27!!

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

      Yups, did not get AC. Test cases aren't available as of now. So cant tell much about the reason.

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

      Most probably I forgot to add "return 0;" when I check whether L > R. So it would print  - 1 twice.

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

    I didn't notice intervals may split during contest. To mark invalid interval [l, r], I think f[l]++, f[r + 1]-- works.

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

Is the following approach for D right? I implemented this algorithm but it doesn't pass some pretests. Where is the mistake in this solution? Take two adjacent words, find the first position where letters are different. If the first letter is greater then we need to turn the wheel by minimum (c-a[i]) so that it becomes smaller than b[i]; if the second letter is greater then we can turn the wheel by maximum (c-b[i]) or else a[i] becomes greater. Store the maximum of the minimums and the minimum of the maximum and if the second value is less than the first then print "-1", else print the first value.

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

    I also did similar. However "if the second letter is greater then we can turn the wheel by maximum (c-b[i]) or else a[i] becomes greater. " This is incomplete. There is another case.

    Eg:

    5 -> 6 -> 7 -> 1

    7 -> 1 -> 2 -> 3

    (c = 7)

    As you see you could also rotate it 3 times and still ordered.

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

    i implemented this too, but there's a catch!

    Suppose n=2 ,c=6 1 2 1 3

    (the numbers are 2 and 3)

    Then according to the above logic you can turn max:3 times but if you turn 5 times it again becomes valid. Hope it clears the doubt!

  • »
    »
    13 months ago, # ^ |
    Rev. 4   Vote: I like it +11 Vote: I do not like it

    You have missed out cases.
    Let a be the char of the first word and b be that of the second word, at the first point of difference.

    If a < b, the valid range is [0, c-b] U [c+1-a, c].
    If a > b, the valid range is [c+1-a, c-b]

    Then from the valid ranges of all the pairs of adjacent words, you can choose any common value. If there is no point which is common to all the ranges, answer is not possible.

    Also, apart from these, if the second word is a prefix of the first one and is shorter than the first word, answer is not possible.

    Code

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

      Shouldn't the valid range for a<b be [0, c-b] U [c+1-a, c-1]. The problem statement expects an ans in [0, c-1] and the changes in c steps in fact reflect those that can be done 0 steps. Seems the test cases are weak.

      Code

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

        It doesn't matter since if [c] is available then [c%c=0] is also available, and the smallest solution always get chose first.

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

I used DSU for DIV2 C but I am getting TLE on pretest 6.http://codeforces.com/contest/731/submission/21488359

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

I solved the C problem with DFS, but I got TLE... How to optimize my code? http://codeforces.com/contest/731/submission/21484127 Or is it just recursive vs queue? XD

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

    If the graph is empty, your codes is O(N2), because of this:

    memset(colNow,0,sizeof colNow);
    
  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The problem isn't in dfs i think. But in

    memset(colNow,0,sizeof col)
    

    Think when there are many connected components, it will get tle.

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

    In the worst case memset would be called 2*10^5 times , which is basically O(N^2) . Use a map instead .

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

    you can save the vertices that you go to them in dfs ,in a vector and after dfs make the colnow of them equal zero or dfs again and do it

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

kudos to the author for such a nice contest!

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

What's the idea for solving E ?

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

    What I did was this.

    Let DP[1][i] be the max score which can be obtained by Petya, if in his next turn he has to choose a prefix of length at least i and let DP[0][i] denote the same for Gena.
    Let S[j] denote prefix sum till j, i.e. arr[1]+arr[2]+arr[3]+...arr[j]
    Petya tries to get the maximum value possible and Gena tries to get the lowest value possible.

    DP[1][i] = max(S[j] + DP[0][j+1]), j>=i
    DP[0][i] = min(-S[j] + DP[1][j+1]), j>=i

    The answer is given by DP[1][2] (1-indexing is used).

    Code

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

    Dynamic Programming on prefix sum array

    check this:

    http://codeforces.com/contest/731/submission/21488865

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

      your solution is pretty good,it's easy for me to understand

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

    Let S[i] be the sum of the numbers from 1 to i.

    Let D[i] be the optimal maximum difference for the current player if the leftmost sticker contains the sum of the numbers from 1 to i.

    Then D[i] = max{S[j] — D[j]} for i < j <= N.

    But since S[j] — D[j] is independent of i, we can just keep track of the maximum S[j] — D[j] and update it at every loop, leading to O(N) solution.

    code: http://codeforces.com/contest/731/submission/21495276

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

      How you are taking account of the two persons , please elaborate?

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

        The best play for one person in a certain configuration is the same as the best play for the other.

        "Then D[i] = max{S[j] — D[j]} for i < j <= N"

        S[j] is what you get from choosing up until the sticker j

        D[j] is the best play on the configuration j

        So you choose the best play possible for every situation.

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

As I see, problem F easier than problem D & E, problem B easier to WA then problem F :)) funny contest

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

This time is so good for chinese competitor.Thank you for your good game.

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

Hopefully become Expert:)

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

I think problem C can be interpreted in 2 ways.
1. Counting cost of colouring of both left and right pieces of i-th pair of socks as 2.(Counting colouring of each left and right sock seperately)
2. Counting cost of colouring of both left and right pieces of i-th pair of socks as 1.

During the contest, I have implemented assuming case:1, which failed on pretest 3.
After the contest, I see that I was supposed to assume the other case.

Here are my submissions with only difference being which assumption was considered among the above.
Assumption-1 : 21492459 Failed
Assumption-2 : 21493466 Accepted

Should have got this clarified during the contest :(

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

    You never have to color both the right and left sock though..

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

can someone identify the mistake in my submission for "C", i keep getting WA on 6.

code = http://codeforces.com/contest/731/submission/21492734

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

    Hope that comment helps.

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

      i tried a testcase with repeated indeces , it is giving correct output for that .

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

        Your code gives negative answer. That means the expression (size - maxi) sometimes is negative, that is sometimes size becomes smaller than maxi. You can try thinking backwards and work out an example when this is true.

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

    You use variable 'i' in two loops that are nested.

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

      i corrected that , it still gives WA on 6 .nevermind , got it !

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

    It would anyways TLE , it is O(N*K)

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

Rating Updated!

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

Got TLE for C at test case 33 mysolution . I tried with DSU. Could somebody help?

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

Finally I'm Cyan !!, and I solved 3 problems from the first submission.
Self confidence is rising here !
thank you Zlobober very much for the nice contest

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

No hacks this time :-)

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

http://codeforces.com/contest/731/submission/21485811 WA in test case 66 :( Can anyone help ?

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

    Someone please point out the bug ... unable to find it ....

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

      In the last loop in main(), the upper bound for i should be m instead of n.

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

    I also unintentionally did the same mistake...Since the values of array may not be distinct. So, we should avoid calculation for same elements , otherwise if we calculate for value say, 1 or 2, for many times, then this will lead to O(n*n)...I had sorted array, then was trying to escape repetition, but forgot to do that while coding,, finally, which causes TLE :( .

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

How do you solve problem B? I wrote "something" which passed the pretests but it doesn't work it some cases. What's the normal solution for this problem?

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

    Iterate from left to right . If arr[i] is even we can use coupons and we are done . But if arr[i] is odd , arr[i+1] should exist and should be positive . If not print NO else do arr[i+1] -= 1 .

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

      Thanks, that's so easy and obvious...I actually thought the same but then was misled by some example which I treated incorrectly.

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

anyone can find my code bug for problem C ????? I'm using DSU , calculating all socks needed minus the largest number of colors for every parent. http://codeforces.com/contest/731/submission/21491376

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

    What does the function join() return?

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

    You are coloring everything with the maximal color, not the color with maximal number in map( because pairs are sorted by the first element, not the second).

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

:'( F gave TLE on 26th test passed just by fast I/O Yeah Life is unfair!

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

I don't know why, but I found Problem B very tough (I solved it somehow though :P). Can anyone suggest a simple solution?

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

    Here is mine:

    • For i = 0...n-2 (skips the last) ---> if a[i] > 2 then a[i] %= 2 ---> after that, if a[i] == 1 and a[i + 1] == 1 then reduce both of them.

    The result is 'YES' if sum of remain elements in a is 0. Otherwise, it is 'NO'. Hope this helps.

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

    Break the array wherever 0 is present. Find sum of each part. Answer is YES if sum of each part is even.

    Code

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

    from 0 to n-1 if a[i] < 0 answer no and break; else if a[i] is odd substract from a[i+1] 1;

    then check last element a[n-1] if its odd or less than 0, answer no;

    otherwise answer yes

»
13 months ago, # |
  Vote: I like it -6 Vote: I do not like it

There is something mystery in this contest for my case. My code for solving problem C returns 2 for Test 5, which is correct, on my computer. But when I upload the code, it became 3, which is wrong answer.

Because it's correct on my computer so that I have no idea where it went wrong. Please take a look: http://codeforces.com/contest/731/submission/21493963

Many thanks. P/S: Picture proof.

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

    Which ide are you using?

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

    Comparator in C++ must return 1 if the first argument is less, then the second. Otherwise 0.

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

Nice round.. I think problem F was overrated ... it should have been a C or a D. however it was an interesting round. thanks

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

3 points from getting blue :C Anyways, can someone please tell me the solution for problem F?

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

    Let f(x) denote the number of integers that are  ≥ x. Then, if we fix a number i as leader, the total sum will be f(i) + f(2i) + f(3i) + ....

    We can precompute f(i) for all i ≤ 200000 by using the same method as sieving primes. The time complexity is .

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

      Interesting, I didn't think about that.

      If you don't precompute f(i) you can use binary search to find it, making the complexity O(n*logn*logn) but without the need to worry about precomputation.

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

      Very nice solution, thank you.

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

      Interesting solution :)

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

      I don't understand even if you precompute f(i) for all i<=200000, then also you have to sum it for i, 2i, 3i, ... (200000/i) elements. Why isn't it O(n^2). Here's my solution along the lines suggested by you, it's getting time limit exceeded and the reason I could think of is the above. Am I missing something.

      http://codeforces.com/contest/731/submission/21516249

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

        Make sure you don't visit the multiples that you have already visited and it should get accepted. You took care of the case with repeated ones but look at the one you got TLE'd (repeated twos)

        Edit: it is worth noting the reason why this is O(nlogn).

        If you don't visit the same number twice, it takes at most N+N/2+N/3+...+N/N.

        That's the same as N(1+1/2+1/3+...+1/N). That sum is bounded by ln (look for the integral of 1/x from 1 to n) so the complexity is O(n*logn).

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

    deleted

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

Spent an hour and 2 wrong submissions on C because I thought you had to color socks dynamically every day and not just all of them at once beforehand. :D

Good thing I went and solved F before realizing how easy C actually was.

Just wondering, how to solve C if you can color socks dynamically?

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

anyone knows why my solution for c fails? http://codeforces.com/contest/731/submission/21498239

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

All the best guys

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

Can someone explain the solution to Problem D?

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

    Here is my approach:

    For each block i (0<=i<n-1), compare them in lexigographical order. It should fall under one of these cases: (Let j be the position where a[i] and a[i+1] differs)

    1. a[i] is a prefix of a[i+1] — Great! We don't have to do anything, a[i] < a[i+1] is always true.

    2. a[i+1] is a prefix of a[i] — Great! Now we are screwed! The door is always locked.

    3. a[i] is currently lexigographical smaller thatn a[i+1] — Then calculate when will a[i] and a[i+1] go through the cyclic shift at j. During the period where a[i+1] has gone through the cycle and a[i] haven't, a[i+1] will be smaller than a[i].

    4. the reverse of case 3 — We will also calculate the cyclic shift time. This time, only the period where a[i] has gone through the cyclic and a[i] haven't will allow us to open the door.

    You can see that there will be intervals where you can open (or not open) the doors. Now all you have to do is check for the earliest moment where you can open the door.

    (You can use the range fill technique to invalidate a time interval. See my code here http://codeforces.com/contest/731/submission/21498917 )

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

      Can u please elaborate the last part of your solution. Means how you are using the chk[] array to check for intervals where we can shift the lock ??

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

        Let's say we are counting the amount of intervals at a certain point. The most naive solution is to increament each of the points within the interval by one — but this takes O(n) time to mark each interval.

        Instead, we can increase the start of the interval by one, and the point near to its' end of it by one, and calculate the prefix sum after we have mark all intervals, and this will tell us how many intervals lie on a certain point. Why does this work? Consider each interval individually, the prefix sum will cause all points on interval [left,right] increase by one, yet since [right+1] has a value -1, therefore it gets canceled and the interval [right,n) remains uneffected.

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

mfw practicing and see F only have the "brute force" tag.

 Dude What

nvm they fixed it. =]

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

I liked how none of the problems used complex data structure and algorithms.

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

quite surprised about the AC number of each problem.
I think E is quite easy, the idea is easy and very easy coding.
D is a little complicated to code, but the idea isn't hard.

F is hard for me, I didn't figure out a way by myself even after contest.

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

I hope for an editorial for this contest, as well as for Technocup.

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

plz upload the editorial!!!

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

I Can't get What is wrong on my solution... Solution I get Pretest Passed at 1:59.. but failed to pass Main test at Test22.

Please Let me know Why my solution is not working on this test case like 19999 10001 10002 10003 10004 ...

I solved The Problem F bruteforce. 1. sort input 2. from the small number to large number in the input, vec[1...n], Iterated if the mainpower key is v[i], if v[j] % v[i] == 0, pass. or not, v[j] -= v[j]%v[i] ( to make secondary power) 3. print the answer

  • »
    »
    13 months ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it
    200000
    100001 100002 ... 101000 200000 200000 ... 200000
    

    The answer is 200000 * 199000

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

      Oh my... Thanks a lot. I realized

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

    You should say, "I submitted The Problem F bruteforce" instead of saying, "I solved The Problem F bruteforce", since all of your submissions for F got WA!

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

      Thanks for giving great advice!!

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

i think there maybe some mistakes of problem F. the two same codes, the first code, define maxn=1000100,it AC;21510847. the second code, define maxn=200100,it WR on31;21510692.

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

21506585 — > What is my off by one error? :(

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

Could anyone comment the Problem E example 2?

input: 1 -7 -2 3
a)
turn 1: A takes 1 -7 -2, puts -8
turn 2: B takes -8 3
totals: A - B = (1 -7 -2) - (-8 + 3) = -3
b)
turn 1: A takes 1 -7, puts -6
turn 2: B takes -6 -2 3
totals: A - B = (1 -7) - (-6 -2 + 3) = -1

Why (a) is corrent answer? (b) is better than (a)!
  • »
    »
    13 months ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    B is not playing optimally in b)

    turn 1: A takes 1 -7, puts -6

    turn 2: B takes -6 -2, puts -8

    turn 3: A takes -8 3, puts -5

    A's score: -6 + -5 = -11

    B's score: -8

    diff = -11 — -8 = -3

    Sometimes you can force a turn on others and thus reducing their scores. >=]

  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Could you dig a bit more please?
    Why -8 in (1) is considered "optimal" but -21000 in (2) is not?
    input 1: 1 -7 -2 3
    input 2: -6000 -5000 -4000 -3000 -2000 -1000
    
    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      optimal moves for input2:

      turn 1: A takes [1,5], S= -20000. turn 2: B takes [1,2], S= -21000.

      Difference in score= +1000

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

When will the editorials be up!?

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

Where is the tutorial?

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

not able to understand why to use DSU for the div2C problem.

Could someone please explain.

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

@Zlobober Please add tutorial to the box names [→ Contest materials] on the righ_bottom of web-pages of the problems. Thank you.