By BledDest, history, 4 months ago, In English

Hello Codeforces!

On Dec/18/2023 17:35 (Moscow time) Educational Codeforces Round 160 (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 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Adilbek adedalic Dalabaev, Mikhail awoo Piklyaev, Maksim Neon Mescheryakov, Roman Roms Glazov, Artem Ferume Ilikaev, Ruslan AcidWrongGod Kapralov and me. Also, huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

The problemset partially intersects with the Open KFU Olympiad, so if you participated in it, please avoid taking part in the round.

Good luck to all the participants!

Our friends at Harbour.Space also have a message for you:

Harbour.Space
WORK & STUDY OPPORTUNITY IN BARCELONA @ HARBOUR.SPACE UNIVERSITY

Harbour.Space University has partnered with Giga (Unicef) to offer Master’s degree scholarships in the fields of Data Science, Computer Science and Front-end Development, as well as work experience.

We are looking for various junior to mid-level candidates:

Data Scientist:

  • Strong ML knowledge
  • Experience with Data Visualization Tools like matplotlib, ggplot, d3.js., Tableau that help to visually encode data
  • Excellent Communication Skills – describing findings to a technical and non-technical audience is essential
  • Strong Software Engineering Background
  • Hands-on experience with data science tools
  • Problem-solving aptitude
  • Analytical mind and great business sense
  • Degree in Computer Science, Engineering or relevant field is preferred

Data Analyst:

  • Cleansing and preparing data
  • Analyzing and exploring data
  • Expertise in statistics
  • Analyzing and visualizing data
  • Reports and dashboards
  • Communication and writing
  • Expertise in the domain
  • Solution-oriented

Front-end Developer:

  • Solid understanding of HTML, CSS, and JavaScript
  • Familiarity with front-end frameworks and tools such as React or Vue.js.
  • Strong problem-solving skills, attention to detail, and a passion for creating intuitive user interfaces are essential

Full-stack Developer:

  • Interest and experience in web application development, data products and OpenAPIs
  • Comfortable with on-cloud deployment services (preferably Azure), Git and CI/CD pipeline and deployment processes
  • Experience with open-source projects is highly preferred
  • Strong ML knowledge
  • Experience with data visualization tools like matplotlib, ggplot, d3.js, Tableau that help to visually encode data
  • Excellent communication skills, — it is incredibily important to describe findings to a technical and non-technical audience
  • Strong software engineering background
  • Hands-on experience with data science tools
  • Problem-solving aptitutde
  • Analytical mind and great business sense
  • Degree in computer science, engineering or relevant field is preferred

All successful applicants will be eligible for a 100% tuition fee scholarship (29,900 €/year) provided by the partner company.

CANDIDATE’S COMMITMENT

Study Commitment: 3 hours/day

You will complete 15 modules (each three weeks long) in one year. Daily class workload is 3 hours, plus homework to complete in your own time.

Work Commitment: 4+ hours/day

Immerse yourself in the professional world during your apprenticeship. You’ll learn from the best and get to apply your newly acquired knowledge in the field from day one.

REQUIREMENTS:

  • Industry experience
  • International exposure
  • Eager to learn
  • Sustainability is a key topic for you
  • You want to work for an NGO
Apply here →

UPD: The editorial can be found here.

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

»
4 months ago, # |
  Vote: I like it -68 Vote: I do not like it

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

i wish, i can solved the C no problem in this round ...!

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

    i want to know the end of the story how many problem did you solve ?

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

      i had done problem A is after 1 times trying and problem b is after 3 time trying.... and didn't touch problem C ...cause i had maybe 7 to 10 minute left after solving A & B... and i got maybe -37 ratings after this contest (According my standing on this contest).

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

        sad but i become grey from green in this round...although ratings is nothing i still very sad

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

          no issue brother..please don't be sad...the last div 3 contest (in the past night)...i can't solved the problem A in 1 hours 10 minute and then i ditch the contest...it's hurts me a lot yesterday...but i am okay today...somewhere, i had read..."A master has failed much times that a newbie doesn't even try"...this line inspired me a lot...so don't be sad brother...i hope...one day we will became RED coder...just keep trying brother...!

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

            in fact,i solve 6 problem last night(i never do it before) you do not solve A maybe because you just do not see this kinds of question before. Try to solve more question!

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

Gl for everyone!

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

Hope the questions are not confusing.

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

I'm back with one more post-contest discussion stream
I will discuss the problems I solve in this contest.

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

Educational rounds are always exciting, don't know what they surprise.

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

hope i get positive delta :D

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

For some reason I didn't get the notification that the round would be unrated for me (rating must be between 0 and 2,099), and there is no unrated marking on the registrants list. Is this intended (or am I misremembering)?

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

Sometimes the educational rounds being hard for me But I feel this one will be interesting ☺️

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

Hope to become specialist this round!!!

»
4 months ago, # |
  Vote: I like it -16 Vote: I do not like it

Is it rated?

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

Hoping to perform better than my previous contest.

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

What's the difference bwtween normal rounds and educational rounds? It really bothers me.

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

    Different scoring type and usually educational rounds are supposed to be "education" so you might encounter more standards.

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

      So educational rounds have less ad-hoc problems and require us to use standard algorithms more?

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

        Not necessarily. It might have more standard but still needs ad hoc and similar. Tbh not too different from a normal . For example last round had ad hoc problems but problem E was standard problem.

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

USACO bronze annually is clashing with this contest :(

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

let's make it Cyannnnnn

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

Hope to become an expert after this round.

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

What is the difference between edu and general round?

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

goodluck everyone!

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

Speedforces

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

C <<<< D

i think there is huge gap between them

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

    I couldn't able to come up with an solution for this problem tried using bit manipulation but got wa on testcase 3 do we have to solve this using any other approach.

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

      you mean problem C?

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

        yes

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

          My solution for problem C

          To count how many we have for each power use vector or just ordinary array with 30 elements for each power of 2 that could be entered (0 to 29).

          For the first type of operation, just increment that value in the vector.

          For the second type of operation, go through from 29 to 0 and subtract until the values are finished(refer to the first vector for how many you have with that power of two) or v which was input has less value than the power of 2 we want to subtract. At the end, check if v is 0 or not, if it is answer is "YES", otherwise it is "NO"

          You can refer to my submission here: 237768705

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

            Great approach,thanks for sharing your approach. according to you what will be the rating of this problem

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

            Thank you for sharing

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

            Another approach....

            while (n--)
                {
                    ll a, b;
                    cin >> a >> b;
                    if (a == 1)
                    {
                        v[b]++;
                    }
                    else
                    {
             
                        vector<ll> tm = v;
                        ll carry = 0;
                        bool flag = true;
                        for (ll i = 0; i < 30; i++)
                        {
                            tm[i] += carry;
                            if ((b & (1ll << i)))
                            {
                                if(tm[i] == 0)
                                {
                                    ctn;
                                    flag = false;
                                    break;
                                }
                                tm[i]--;
                            }
                            carry = (tm[i] / (ll)2);
                        }
                       if(flag) cty;
                    }
                }
            

            So to calculate we can get w from out list or not , i just started traversing each bit of w , if at ith bit is 1 in w then we will look that we have ith bit or not in hashmap.If No then we print NO , If yes then decreament ith bit from our hashmap. if there is still some remain in ith bit then we can push it ahead , like we have m[2] = 3 and we have used it one from it so now we had 2 that is (2^2 + 2^2) we can write this as 2^3 so we can increament m[3] by 1. so in genral we have count extra for ith bit then we can increament m[i+1] by floor(count/2.0).

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

good contest

»
4 months ago, # |
  Vote: I like it +40 Vote: I do not like it
After doing ABC
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to do E?

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

    Using Flows

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

    I guess, Flows with Demands should satisfy the problem. Just throwing in some virtual nodes for outflow from each node and inflow to each node should do the job. Here, a node is a row/column, and edges are delta-based flows on flipping cells. Note that we know the original sum across rows/columns, and only care about needed deltas through flipping. This delta determines the demands on inflow/outflow virtual nodes.

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

      Agree. I'm about the same.

      Use minimum cost maximum flow. Specifically, create a node x[i] for each row i and a node y[j] for each column j.

      For each cell in the i-th row and j-th column, create an edge (x[i], y[j]) with a flow of 1. Flow represents filling the cell with 1. If the cell originally contains 1, calculate the cost in advance with a unit cost of -1 to offset the premature calculation cost. If the cell originally contains 0, the unit cost is 1.

      Connect the source node to x[i] with an edge of flow a[i] and cost 0. Connect y[j] to the sink node with an edge of flow b[i] and cost 0. If you understand that flow is “1”, this step will be quite natural.

      Finally, run the maximum flow algorithm. If the flow is equal to sum(a[i]) = sum(b[i]), it indicates that the assignment is valid, and the answer is the minimum cost; otherwise, it is invalid.

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

is rating change delta which shows during contest accurate?

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

    Usually the actual rating change is higher than what is shown in by carrot extension, especially in edu rounds. Unless you get FST

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

How to solve E? Is it related to graphs somehow?

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

    Make a flow network with n+m+2 edges. One is sink, one is source and n vertices for rows and m for columns. Make edges with capacity r[i] to all rows from source and edges of capacity c[j] and cost 0 from columns to sink. Also make edges from row i to column j with capacity 1 and cost 1-a[i][j]. Your answer is minimum cost max flow plus the number of a[i][j] == 1 where the i -> j edge was not taken.

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

E reduces to this CSES problem: Grid Puzzle II

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

I couldn't able to come up with an solution for C problem tried using bit manipulation but got wa on testcase 3 do we have to solve this using any other approach.

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

Speedforces for someone

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

Unbalanced Contest,

A,B,C were too easy and D is too hard.

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

Wrong answer on test 24 in E — Matrix Problem ,, can any one give a test case sorry for my bad English

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

    This test fails

    4 4
    0 0 0 1 
    0 1 1 0 
    0 1 1 0 
    1 1 0 0 
    1 3 1 2 
    2 0 2 3 
    

    Also this

    3 3
    0 0 0 
    1 0 1 
    1 0 0 
    1 1 2 
    1 3 0 
    

    And this

    2 2
    1 1 
    0 1 
    1 2 
    1 2 
    
    
»
4 months ago, # |
  Vote: I like it +11 Vote: I do not like it

D is somewhat monotonic stack and dp, I thought so

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

    I tried the formula dp[i] = Sigma(dp[j-1]) with a[j] >= a[i] and j <= i result is the product dp of 2 sequences a[0] ... . a[minimum_index] and a[n-1] ... a[minimum_index] but wrong, do you have any other solution

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

.

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

D fucking boggled my mind. I thought I had it like, 3 or 4 times, only to fail sample, find out that my method is wrong, come up with new method, rinse and repeat. I wrote everything from monotonic stack to segtree today 🤡

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

    A to C is trash btw, but D made the contest worth giving I think (even though I still cannot get it)

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

      Yup, C isn't that bad but A and B are just trash and the round is unbalanced AF

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

knew D was div-conquer with min but couldn't implement 😭

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

How to solve D?

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

What's the idea behind D

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

    DP on suffixes, maintained with a monotonic stack.

    Compute for each index how many arrays you can reach that start with it, ignoring elements before it. You can delete any prefix starting from it that contains no smaller values (the monotonic stack is for this) or delete a prefix immediately after it to reach smaller elements further away. I handled this part with a set but upon further inspection it’s really just a copy of my stack ;)

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

      Could you explain the part "or delete a prefix immediately after it to reach smaller elements further away", it's a bit ambiguous for me.

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

        The first case, where we delete until some index before the next smaller value, does not cover cases where the element immediately after the first one is smaller than it. Consider for example the following case:

        4 3 2 1

        The array 4 2 1 can be obtained by operating on [2, 3], but since 2 comes after the next smaller value after 4, we would not have counted this case. Arrays where the second element is smaller than the first will be obtained by operating on [2, j], if we want the j-th element (smaller than the first) to become the second. And it's only possible if a_j = min(a_2, ..., a_j). So we maintain the set of possible indices j, and remove elements from the set over time.

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

    The problem is quite similar to Indonesian NOI contest here

    I think the approach should be quite similar. Assume $$$dp_i$$$ is the number of ways that the array ends with $$$p_i$$$, then we can consider that for a range $$$(l, r)$$$ we can calculate number of ways when $$$p_l$$$ or $$$p_r$$$ is the minimum

    For each $$$r$$$, there are two possibilities :

    • find conditions for all values $$$l < r$$$ where $$$p_l$$$ is the minimum from $$$(l, r)$$$ then $$$dp_l$$$ is a contributing factor to $$$dp_r$$$

    • find conditions for all values $$$l < r$$$ where $$$p_r$$$ is the minimum from $$$(l, r)$$$. To do this, find an index $$$i$$$ such that $$$i$$$ is the previous smaller element of $$$r$$$. Then $$$dp_{i+1}, dp_{i+2}, ..., dp_{r-1}$$$ are contributing factor of $$$dp_r$$$

    For the first case, we can maintain a monotonic stack and maintain the sum of all dp within the stack

    For the second case, we can use a monotonic stack to maintain previous smaller elements for each index and to find the sum of the dp we can use a prefix sum of dp

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

    you can do it with DnC on the minimums of the array, split the array on the minima and calculate recursively for the left and the right part and merge those results

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

      Which data structure for the splitting would be better than the Linked list or the segment tree?

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

      Can you explain your approach, what would be the base case and the merging condition?

      • »
        »
        »
        »
        4 months ago, # ^ |
        Rev. 3   Vote: I like it +80 Vote: I do not like it
        • Solve the problem for the whole array $$$[1, n]$$$. Let $$$m$$$ the position of the minimum. Note that you cannot delete the minimum, and the moves on the left and on the right are independent. So the answer is the product of the answers on $$$[1, m-1]$$$ and $$$[m+1, n]$$$.
        • How to solve for a generic interval $$$[l, r]$$$? Note that you can either keep $$$m$$$ (the position of the minimum value in $$$[l, r]$$$) "alive", or use the elements in positions $$$l-1$$$ and $$$r+1$$$ (if they exist) to delete $$$m$$$.
        • Let $$$a$$$, $$$b$$$ be the answers in the intervals $$$[l, m-1]$$$ and $$$[m+1, r]$$$. In any case, we can keep $$$m$$$ "alive" (in $$$ab$$$ ways). If $$$l \neq 1$$$, we can delete $$$m$$$ (actually, all elements in $$$[l, m]$$$) in $$$b$$$ ways. If $$$r \neq n$$$, we can delete $$$m$$$ (actually, all elements in $$$[m, r]$$$) in $$$a$$$ ways. If both $$$l \neq 1$$$ and $$$r \neq n$$$, we are overcounting the case where we remove every element in $$$[l, r]$$$, so we must subtract $$$1$$$ back.
        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks for such a neat explanation.

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

          Thanks!

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

          Thanks for explaining the approach.

          There is just a correction that:

          If both l≠1 and r≠n, like you said we are overcounting the case where we remove every element in [l,r], therefore we must subtract 1 instead of adding it back.

          ll recur(int l,int r,SparseTable &st,map<ll,int> &map1)
          {
            if(l>r) return 1LL;
            
            int ele=st.query(l,r);
            int m=map1[ele];
          
            ll a=recur(l,m-1,st,map1);
            ll b=recur(m+1,r,st,map1);
          
            ll res=(a*b)%mod;
          
            if(l!=0) res=(res+b)%mod;
            if(r!=n-1) res=(res+a)%mod;
          
            if(l!=0&&r!=n-1) res=(res-1)%mod;
          
            return res; 
          }
          
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

another speedforces round!

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

I think Problem D is same as this, Except the constraints are tighter.

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

    The hardest step of problem D is to come up with a correct DP. Optimizing it from $$$\mathcal O(n^2)$$$ to $$$\mathcal O(n)$$$ is easy.

    Luckily no one submitted this problem during the contest :(

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

Speedforces lol

»
4 months ago, # |
  Vote: I like it -77 Vote: I do not like it

Easiest D ever seen

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

How to solve E?

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

    mincost maxflow on a bipartite graph

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

    With flow min cost, I didn't manage to create a net during the contest sadly ;d

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

any hints for D? also can someone try to hack my C?

about c
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why C failed at test case 5?237765289 Could anyone point out what i missed ?

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

speedforces moment

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

Today is my birthday, and I wrote this round.lol

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

I have just upsolved problem C and I like it the most!

Thank you guys for the great contest!

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

I think problem F is quite similar to this problem.

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

    Well the proof is not obvious. It only works for set of numbers where all smaller numbers divide each element in the set, for example here it is powers of two. It wouldnt work in cases like {1,3,5}

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

      I would say it's pretty obvious considering it's rated *1200~1300 on clist...

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

I don't understand why there is such a large gap in difficulty between C and D.

»
4 months ago, # |
  Vote: I like it -15 Vote: I do not like it

if i had an hour more, i can definitely solve D.knew it was some dp and related with monostack stuff.nice problem anyway

»
4 months ago, # |
  Vote: I like it -79 Vote: I do not like it

F has appeared before: coi15p2. And no, it wasn't like the idea coincided or something, this is the exact same problem. I mean, problem-setters could just avoided this by literally search their problem up, but they didn't, which I don't really get.

As a result, an unusual number of consistently low-rated contestants AC F, which are solved by like, what, 30 people, LGM included. A person whose skill are around Expert — Candidate Master level should not be able to pull that off in a 2 hours contest.

If enough people complain about this, the contest could probably get unrated, or... since F is solved by so few people, and these guys solved so few problems that it shouldn't matter. I don't know. Personally, I want the contest to get unrated to punish these MF

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

    I'm getting +ve delta so :noo:

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

    It doesn't effect larger group of people so it should not be unrated

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

    It has been said before. Problems will repeat, but the round will not be unrated if not done intentionally.

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

    lol cry about it

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

Very interesting contest, for me problem " C " was super easy even easier than " B " as I love math problems , Thanks for authors <3

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

    Could you share ur intuition for C? C got a lot of ACs . Everybody figured it out so quickly except me

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

      Sure, we know that pow(2,n) it's binary representation is 100.. ( 1 followed by zeroes )

      now for any number X it's binary representation is ones and zeroes for example " 1011 "

      we can write it as 1000 + 10 + 1 which all of them are in the form of pow(2,n) .. So, if we subtract the maximum pow(2,n) less that X form X we will reach to X = 0.

      in this problem we just add one condition that pow(2,n) must be inserted, also we subtract this number from x until it's frequency in the vector or until X become less that it

      // operation 2
      // cnt is temporary freq
      // ar is the freq
      vector<int>cnt = ar;
      cin >> t;
      for(int i = log2(t); i >= 0; --i)
      {
         int mx = pow(2,i);
         if( mx <= t && t && cnt[i])
         {
             // t = constant(k)*mx
             // k musn't exeed cnt[i]
             int k = min(cnt[i],t/mx);
             cnt[i]-=k;
             t -= k*mx;
         }
      }
      

      Wish you got it

»
4 months ago, # |
  Vote: I like it -12 Vote: I do not like it

C got accepted 30 seconds after the contest :(

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

what is the brute force solution for problem-D?

Is it to check for all subarrays something.

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

That problem D was just so hard!!!

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

Hi! How long does it usually take for the editorial to be published? Thank you :)

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

Can someone please hack my C? It's O(n^2) in some cases and I think it should TLE. But I tried the case of 50000 1 0 queries followed by 50000 2 50000 queries and it didn't TLE.

UPD: I resubmit it to judge it on the new test cases and it passes in 1013 ms. So I may have gotten away with it this time. I'll take it as a learning experience.

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

    Seems unhackable. C++ compiler optimization too OP

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

    The complier understand what you are doing with

    while (sum >= p && stock[i]) sum -= p, stock[i]--;

    And convert it to a O(1) operation.

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

      I don't think this is true reading the assembly on godbolt

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

        You are right. I carefully checked the assembly on Compiler Explorer and I can see the loop even on -O2.

        So maybe because everything is in CPU L1 cache so the loop runs super fast.

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

          Yeah. The loop is also very short, the branch predictor is also probably never failing.

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

    currently trying near $$$48000$$$ add queries, and I don't quite know why it isn't getting hacked (or why the setters even set limits too loose)

    seriously what the f
»
4 months ago, # |
  Vote: I like it +2 Vote: I do not like it
»
4 months ago, # |
  Vote: I like it +9 Vote: I do not like it

why this get so much downvotes?? just for D was too hard?

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

Folks, why in the problem C the greedy approach for the queries of type 2 works? For example, in the normal coin change problem the greedy approach won't work afaik, why here it works? Thank you guys, appreciate!

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

    2^n is greater than the summation of 1+2+4+8+...2^n-1 so you can be greedy about using your smaller powers because they can never contribute to be a bigger one

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

can anyone say why greedy 0-1 knapsack working for problem C, 0-1 greedy knapsack don't work for all denominations right. did there is any special properties of 2 powers that is making greedy knapsack work?if yes what is that prroperty

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

    binary representation of a number?

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

      how it is related, please elaborate. i saw your sol. you are taking maximum possible sum from coins of maximum denomination, like why maximum possible sum from coins of maximum denomination is related to binary representation

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

        so practically when we make the binary representation in base 2 of a number we always take the biggest power of two that is smaller than our number and make that bit 1 and apply the same procedure but for a smaller number, this works because every number has an unique binary representation

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

Uh how does rating work? Will I get rating for this round regardless of my score? Someone explain pls

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

    Yes, you always get a new rating for all contests that are rated for you. This contest is rated for anyone under 2100. Considering that you're currently unrated (that's 0 basically), it IS rated for you.

    Rating works as follows — for any rated contest that you give, your rating is updated based on your performance. If you perform well, it increases, else, it decreases. Anyway, rating is just one factor to competing, in the long run, the experience results in a net positive anyhow. Have fun! :)

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

      Ayo thanks for the reply. Okay so this is a pretty cool system. I did very badly, but eh it's just for fun. It's actually kinda refreshing to compete in programming just for the heck of it.

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

Can anyone suggest me a more optimal solution for C? My Submission

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

Problem C was much easier than i thought TT

solve()
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What's the worse time complexity of your approach? Isn't it O(m^2)?

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

      It is O(m^2) without compiler optimization.

      The compiler understand the loop

      while(sum+(1<<i)<=x and aux[i]>0 )sum+=(1<<i), aux[i]--;

      and generate a better O(1) code to achieve the same result.

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

        That's cool. I had never known that.

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

        Yes! It's o(m^2) and I've noticed a bit late so i received a hack XD. But I resubmitted with a binary search optimization and got ac too with O(mlogm).

        I'd like to see that O(1) code.

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

          Wasn't aware that your code was hacked. Curious what the test case was. I try using

          100000
          1 0 (repeat 50000 times)
          2 1000000000 (repeat 50000 times)
          

          and it does not work

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

            if you find the test case i would appreciate if share it plz. Also I think of the most obvius test case like that one but no get hacked

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

          What is your binary search approach?

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

            In this line:

            while(sum+(1<<i)<=x and aux[i]>0 )sum+=(1<<i), aux[i]--;

            Instead of adding one by one, do a binary search over lo =0, hi =aux[i] and check if sum+mi*(1<<i) <=x

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

              Alright got it now. Thanks

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

              The binary search can probably be replaced with division.

              $$$desirable$$$ = $$$(sum - x) / (1 « i)$$$

              $$$available$$$ = $$$aux[i]$$$

              $$$taken$$$ = $$$min(desirable, available)$$$

              $$$sum$$$ -= $$$taken * (1 « i)$$$

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

    good one !

    can you explain your approach how the index of element is helping you to construct the ans

    as you stored (element,index) in root , what is the contribution of left ans and right ans

    correct me if Iam wrong

    even I thought of the contribution of minimum index but couldn't proceed:D

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

      for each segment l..r i am getting min value and it's index, let it be (mI). then making a call to its left and right excluding the index. left = l..(mI-1) right = (mI+1)..r

      now, there can be two cases, case 1: when we include element with index mI in our required final array: if that is the case answer is simply leftAns*rightAns.

      case 2: when we don't include element with index mI, this case is difficult in my implementation:

      in this case we have to know whether is there a smaller element than mI on left side and/or right side. thus bools isL and isR

      if isL, then we have to remove all left side including mI, then ans will be added is right side. similarly, left side might be added. note: left side and right side includes empty array also, then there can be case where both isL and isR, then empty would be added twice thus remove isL&isR.

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

    Nice One!

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

Speedforces

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

Plese explain D

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

Can anyone understand the code for problem D of tourist? I can't understand what dp_nxt and dp_sub mean.

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

    you need to be true sigma ioi enjoyer to understand this code

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

Honey, I love you too.

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

How to solve Problem C using bitset.

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

Won't we get solutions?

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

Will we get extra rating only by successful hacking or also by submitting correct solutions?

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

Where can I find editorial?

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

Is there a reliable rating predictor available as of today? This one doesn't seem to be working accurately any more.

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

    The hacked case is not considered in the original test cases yet

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

    bruh...you literally submitted it in practice

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

Hello.Why ratings hasn't come yet?

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

how to solve D ????

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

What about the editorials and rating changes?

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

Can anyone tell when will the rating of this contest release. It's already more than 21hrs...hoping soon.

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

did they forget to update the ratings? Div 3 contest will start soon. How will the ratings be given if they dont update it today lmao.

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

When will this contest rating update and where is the editorial

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

Problem C was terrible for its place.

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

    not gonna lie, I couldnt solve it in the contest cuz i overcomplicated it but once i saw the correct idea, the code was easy af.

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

Please add the editorials.

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

Since no tutorials have been provided yet (as well as my rating change), here are my short hints of problems D, E, F.

Hint of problem D
Hint of problem E
Hint of problem F
»
4 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Anybody mind taking a look at my C and giving some insights as to why it is incorrect? After looking at the test case, it seems that there is an iterator position for a map that is before begin, but I do not know how to properly handle that case. Link to code 237787623

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

When will the rating of this round be updated? I was hoping to become specialist and then give today's div3 as a rated round.

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

40 min left for next contest to begin and no change in ratings so far. Uneasy situation.

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

Problem C

Hey can anyone tell the error in this solution 237781165. I am getting runtime error.

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

    I managed to pin point the issue.

    You can see these two submissions:

    238078175 Accepted

    238078130 Runtime error on test 3

    The only difference is that the loop variable i being int or long long

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

    I think I figure this out.

    The issue of your code is that, when you vector v has no element, i.e. for type 2 query, b is 0, v.size() is 0 and v.size() - 1 should be -1.

    However, v.size() actually returns unsigned integer, so v.size() - 1 becomes really big (underflow) and it pass the for loop condition i >= 0. Then accessing v[i] will cause a segmentaion fault.

    I am not sure why this doesn't happen to test1 and test2 though,

    To solve this bug, you can simply push back a 0 to the vector v to make sure that underflow never happened. See 238078855 for added lines.

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

Why are the ratings not out yet?

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

    There is an announcement telling that ratings will be updated after the div.3 contest due to technical reasons. See div.3 post for reference

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

      Thanks for bringing it to my notice.

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

Please upload the editorial and new ratings. Also, please try to elaborate on the concepts used instead of the method.

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

Is the contest unrated?

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

Attention!

I received the following message from system: Your solution 237799004 for the problem 1913B significantly coincides with solutions mayank246/237799004, Naytive_Ritninja/237800400. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://mirror.codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

As that was the approach used by most of the candidates and the candidate is unknown to me. It's just a matter of coincidence that my code matches with other person. Kindly review it. and give me my rating back. BledDest

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

    Your last div3 submissions are also skipped. Coincidence there too?

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

I got a codeforces system message that my solution for problem C coincides with other people, but I haven't done anything and it is a sheer coincidence that my code matches with others, please give my rating back.

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

I am sorry for my mistake, before the contest that day I had mistakenly logged into my old (SAZIBUR)account. I mistakenly submitted the solution to the contest without logout of that account before the contest. So later when I see it's my old account so I logout it then change some code and submit with my main account. And rest of the time I complete this contest with my main(Sazib204061) account. I apologize for my mistake. I promise I won't make this mistake again. So please don't block my account.

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

My solution to Problem A was rejected in the hacking round. Where was the problem?

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

Wait what.

I thought it was rated for Div.2
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What the difference between "Edufcatinal" with nomal?

Is it easier or it have more rules?