Long contest for CSTE 13 & 14 Editorial (Bengali)

Revision en3, by Sukarna_Paul, 2019-07-22 08:06:01

Contest Link

Password : NSTU_insomnia

[Problems were chosen from different online judges]

A. Unknown Numbers

এই প্রব্লেমে দুই জন একটি গেম খেলবে যেখানে একজন 1 থেকে n পর্যন্ত যেকোনো একটি সংখ্যা অনুমান করবে । দ্বিতীয় জনকে সেই সংখ্যাটি বলতে হবে । এই সংখ্যা বের করার জন্য সে প্রথম জনকে বিভিন্ন প্রশ্ন করতে পারবে । প্রশ্নের ধরন এমন হবে যে , দ্বিতীয় জন একটি সংখ্যা বলবে এবং প্রথম জন তাকে বলে দিবে যে তার অনুমেয় সংখ্যাটি ওই সংখ্যা দ্বারা নিঃশেষে ভাগ যায় কিনা । এক্ষেত্রে দ্বিতীয় জন minimum সংখ্যক প্রশ্নের মাধ্যমে সংখ্যাটি বের করতে চায় । এই জন্য optimal approach হচ্ছে প্রথমে প্রথম মৌলিক সংখ্যা দিয়ে প্রশ্ন করতে হবে, এরপর যদি ওই মৌলিক সংখ্যা দিয়ে অনুমেয় সংখ্যাটি ভাগ যায় তবে ওই মৌলিক সংখ্যার power 2 এর জন্য প্রশ্ন করতে হবে । এবারও যদি উত্তর হ্যাঁ হয় , তবে ওই মৌলিক সংখ্যার power 3 এর জন্য প্রশ্ন করতে হবে এবং এভাবে চলতে থাকবে । যদি কখনো উত্তর না হয় অথবা ভাজকের মান n থেকে বড় হয়ে যায় তবে পরবর্তী মৌলিক সংখ্যার জন্য এভাবে প্রশ্ন করতে থাকতে হবে । এভাবে n থেকে ছোট পর্যন্ত সব মৌলিক সংখ্যার জন্য যেতে হবে ।

ধরুন, n এর মান 16 এবং অনুমেয় সংখ্যাটি 9 . তাহলে প্রশ্ন করার sequence হবে 2, 4, 8, 16, 3, 9, 5, 7, 11, 13 . এখন যেহেতু অনুমেয় সংখ্যাটি 1 থেকে n পর্যন্ত যেকোনোটি হতে পারে , তাই 1 থেকে n পর্যন্ত প্রতিটি সংখ্যাই কোন না কোন অনুমেয় সংখ্যার sequence এ থাকবে । তাহলে আমাদের ultimate answer এর squence হবে, n থেকে ছোট প্রথম মৌলিক সংখ্যার power গুলো , এরপর দ্বিতীয় মৌলিক সংখ্যার power গুলো এবং এভাবে চলেতে থাকবে। 

এবার code implementation এ আসা যাক । আমি প্রথমেই n পর্যন্ত মৌলিক সংখ্যা গুলো generate করে নিব sieve() ফাংশনের মাধ্যমে । এরপর বাকি কাজ প্রতিটি মৌলিক সংখ্যার জন্য তাদের power গুলো generate করে একটি vector এর ভিতর রাখলেই হয়ে গেল ।  [My Solution Link](https://codeforces.com/contest/577/submission/56873852)

B. Total Sum

এই প্রব্লেমের optimal solution হল maximum value এর letter কে প্রদত্ত string এর শেষে k সংখ্যক বার যোগ করতে হবে । এরপর string এর প্রতিটি character এর value কে তার position দ্বারা গুণ করে মোট যোগফলটাই answer হবে ।  [My solution link](https://codeforces.com/contest/447/submission/56880773)

এখানে sum বের করার জন্য উপরের মত bruteforce না math এর logic ব্যবহার করতে পারি আমরা। তাহলে আমাদের solution টি k এর আরও বড় মানের জন্যও কাজ করবে । এক্ষেত্রে আমরা 1 থেকে n পর্যন্ত ক্রমিক সংখ্যাগুলোর যোগফলের সূত্র ব্যবহার করব । 

প্রথমে প্রদত্ত string এর প্রতিটি character জন্য value গুলোকে তাদের নিজ নিজ position দিয়ে গুণ করে sum কে update করব । এখানে string এর length n হলে n+1 থেকে (n+k) পর্যন্ত সংখ্যাগুলোর যোগফল বের করে তাকে letter গুলোর মধ্যে maximum value দিয়ে গুণ করতে হবে । এর জন্য আমরা প্রথমে 1 থেকে (n+k) পর্যন্ত সংখ্যাগুলোর যোগফল বের করব , এরপর তা থেকে 1 থেকে n পর্যন্ত সংখ্যাগুলোর যোগফল বিয়োগ করব । এই বিয়োগফলকে letter গুলোর মধ্যে maximum value দিয়ে গুণ করে আগের sum এর সাথে যোগ করলেই হয়ে গেল । 

My solution link

C. Black and White

এই প্রব্লেমে nXm আকারের একটি chessboard দেওয়া আছে । আমাকে ‘B’ আর ‘W’ দ্বারা ঘরগুলো পূরণ করতে হবে যেন adjacent দুইটি ঘর same color এর না হয় । এখানে প্রদত্ত chessboard এর যে ঘরগুলোতে  ‘-’  চিহ্ন আছে সেই ঘরগুলোতে ‘B’ আর ‘W’ বসানো যাবে না । খুবই সহজ সমস্যা । আমরা bruteforce approach এ ‘B’ আর ‘W’ বসিয়ে যাব , শুধু  ‘-’  চিহ্নওয়ালা ঘরগুলোকে ignore করব ।  [My solution link](https://codeforces.com/problemset/submission/445/56884608)

D. Coprime and GCD

এখানে আমাদেরকে a2 থেকে an পর্যন্ত (n-1) টি সংখ্যা print করতে বলেছে যেন i এবং j coprime হলে ai ≠ aj হয় । এই প্রব্লেমের solution হচ্ছে n পর্যন্ত প্রতিটি সংখ্যার জন্য উত্তর হবে তাদের প্রত্যেকের কোনো না কোনো মৌলিক উৎপাদকের জন্য উত্তরের সমান । এর সমাধানের জন্য আমরা sieve ব্যবহার করব । seive function এ প্রতিবার multiple কাটার সময় answer টা রেখে দিবো । My solution link

E. Towhid's New game

এই প্রব্লেমে আমাকে একটা string s দেওয়া থাকবে আর দুইটা empty string t এবং u দেওয়া থাকবে । আমি দুই ধরনের operation চালাতে পারব ।

১। s এর প্রথম character টি তুলে t এর শেষে যোগ করব । ২। t এর শেষ character টি তুলে u এর শেষে যোগ করব ।

আমাকে এভাবে s এর সব character u তে নিয়ে যেতে হবে এমনভাবে যেন possible u গুলোর মধ্যে আমাদের ultimate answer টি lexicographically minimal হয় । 

একটু খেয়াল করলে আমরা দেখব এখানে string t একটি stack এর মত কাজ করছে । আমরা যে character টি সবার শেষে নিচ্ছি , সেটি সবার আগে u তে যাবে। এখন আমরা প্রথমে string s এর প্রতিটি character কে তাদের position এর সাথে pair করে sort করব । এর জন্য আমরা stl এর set ব্যবহার করতে পারি । 

এবার আমরা s এর character গুলো একটি একটি করে check করব যে সেটি আমাদের set এর শুরুতে আছে কিনা । যদি শুরুতে থাকে , তবে সেটিকে u এর সাথে যোগ করব । অন্যথায় সেটিকে stack t তে push করব । প্রতিবারে এই জিনিসটা check করার আগে , আমাদেরকে check করে নিতে হবে এই character টি stack এর top এর সমান বা ছোট কিনা , যদি হয় তাহলে আমাদেরকে অবশ্যই top of stack কে u এর সাথে যোগ করতে হবে । [My solution link](https://codeforces.com/contest/797/submission/56954879)

F. Result of a game

    দুইটা string এর মধ্যে যে string টা বেশিবার আছে সেটিই উত্তর হবে । কোন string কতবার আছে তা গুনার জন্য আমরা map ব্যবহার করতে পারি । [My solution link](https://codeforces.com/contest/43/submission/56955476)

G. Dim

এখানে আমাদেরকে color গুলকে বৃত্তাকারে এমনভাবে সাজাতে হবে যেন পরপর ৪ টি same না হয় । খেয়াল রাখতে হবে প্রথমটি আর শেষটি adjacent . এখন আমি সম্পূর্ণটাকে ( n/7 +1 ) segment এ ভাগ করব । প্রথম n/7 segment কে “ROYGBIV” দিয়ে পূরণ করব । অবশিষ্ট segment কে প্রয়োজনমত “GBIVGB” দিয়ে পূরণ করব । My solution link

H. Equation

    এই প্রব্লেমে আমাকে একটি অ্যারে দেওয়া থাকবে যেখানে 1 থেকে n পর্যন্ত সংখ্যাগুলোর একটি বিন্যাস থাকবে আর কিছু query থাকবে । প্রতিটি query তে একটি করে সংখ্যা দেওয়া থাকবে , আমাদেরকে প্রথমে ওই সংখ্যাটি প্রথম থেকে কততম পজিশনে সেটা বের করতে হবে এবং দ্বিতীয়ত সেটি শেষ থেকে কততম পজিশনে আছে । এরপর সবগুলো query এর প্রথম থেকে পাওয়া পজিশনগুলোর যোগফল প্রিন্ট করতে হবে এবং শেষ থেকে পাওয়া পজিশনগুলোর যোগফল প্রিন্ট করতে হবে । কোন সংখ্যা কোন পজিশনে আছে সেটা আমি একটা map এ store করেছি । [My solution link](https://codeforces.com/problemset/submission/227/57078173)

I. Team Practise

    এই প্রব্লেমে বলা, হয়েছে , কিছু experienced আর কিছু newbie contestant আছে  ।  আমি তিন জন নিয়ে একটি টিম বানাতে পারবো যেখানে হয় ১ জন experienced আর ২ জন newbie থাকবে অথবা ১ জন newbie আর ২ জন experienced থাকবে । এভাবে আমাকে সর্বাধিক সংখ্যক টিম বানাতে হবে । 

খুব সহজেই আমরা O(n) solution লিখতে পারি । আমি একটি লুপ চালাব যেখানে বেশি সংখ্যক contestant ওয়ালা অংশ থেকে ২ জন আর কম সংখ্যক contestant ওয়ালা অংশ থেকে ১ জন নিব । প্রতিবার নেওয়ার পর উভয় ধরনের contestant এর সংখ্যা এবং বানানো team সংখ্যা update করবো । যদি উভয় ধরনের contestant এর সংখ্যা ২ এর থেকে ছোট হয় অথবা কোন এক ধরনের contestant এর সংখ্যা ০ হয় , তবে আর team বানানো যাবে না । এটিই হবে লুপের breaking point . My solution link

K. Minimum people

    এখানে n জন লোক আছে যারা প্রত্যেকে বছরের একটি নির্দিষ্ট  range এর দিনে আসতে পারবে । প্রত্যেকের জন্য এই range টি ভিন্ন ভিন্ন । Male আর felmale মিলে একটি couple হয় এবং সবাই অনুষ্ঠানে couple আকারেই আসতে হবে । এখন আমাকে বলতে হবে অনুষ্ঠান হলে সবচেয়ে বেশি লোক আসতে পারবে ।

    যেহেতু আমদের লোকের সংখ্যা সর্বাধিক 5000 হতে পারে , তাহলে আমরা brute force approch করবো । আমরা বছরের কোন দিন কত জন পুরুষ বা মহিলা আসতে পারবে তার জন্য একটি অ্যারে রাখব । প্রতিটি মানুষের জন্য তাদের ব্যক্তিগত range এ লুপ চালিয়ে এই সংখ্যা count করবো । কোন নির্দিষ্ট দিনে পুরুষ ও মহিলার সংখ্যার minimum টা হবে ওই দিন আসতে পারবে এমন সর্বাধিক couple সংখ্যা ।  এভাবে সবগুলো দিনের মধ্যে যেটা maximum সেটার দ্বিগুণই হবে answer . [My solution link](https://codeforces.com/contest/629/submission/57099152)

L. Summation

    String ব্যবহার করে সংখ্যাটি input নিতে হবে । এখন প্রতিটি character এর ASCII value থেকে 0 এর ASCII value বাদ দিলেই numerical value পাওয়া যাবে । এভাবে সবগুলো digit traverse করে sum বের করতে হবে । [My soluion link](https://codeforces.com/contest/102/submission/42254743)

M. Difficult Problem

    আমাকে এ প্রব্লেমে n দেওয়া থাকবে । n এর মান 105  ডিজিটের হতে পারে । (1n + 2n + 3n + 4n) %5 এর মান প্রিন্ট করতে হবে । খেয়াল করলে দেখব , n এর দুইটি value এর জন্য যদি (n%4) এর মান সমান হয় তবে answer একই হবে । তার মানে (1n + 2n + 3n + 4n) %5 এর জন্য answer যা, (1n %4+ 2n%4 + 3n%4 + 4n%4) %5 জন্যও answer তা । প্রকৃতপক্ষে , (1n + 2n + 3n + 4n) %5 = (1n%ɸ(n) + 2n%ɸ(n) + 3n%ɸ(n) + 4n%ɸ(n)) %5 লিখা যায় । [My solution link](https://codeforces.com/contest/456/submission/57161296)

N. Easy Problem

    এই প্রব্লেমে আমাকে n সংখ্যক সংখ্যা দেওয়া আছে । আমি এই সংখ্যাগুলোর উপর এক ধরনের অপারেশন যেকোনো সংখ্যক বার চালাতে পারবো । প্রতি অপারেশনে আমি যেকোনো একটি সংখ্যা নিব এবং সংখ্যাটি ak হলে , ak  অ্যারে থেকে delete হবে এবং সাথে সাথে ak-1 এবং ak+1 এর সমান সকল সংখ্যা অ্যারে থেকে মুছে যাবে । আর answer এর সাথে ak যোগ হবে । এভাবে আমাকে answer এর মান সর্বোচ্চ করতে হবে । 

    এইটা Basic DP(Dynamic Programming) problem . আমরা যদি ak নেই তাহলে আর ak+1 নেওয়া সম্ভব না । আবার যদি ak+1 নেই , তবে ak নেওয়া কোনভাবেই সম্ভব না । আমরা এই concept দিয়েই এই প্রবলেমটা solve করবো । প্রথমেই কোন সংখ্যাটি কতবার আছে তা count করে একটি map রাখবো । dp নামে একটি 2D অ্যারে নিবো ।   একটি dimension কোন সংখ্যার জন্য state নির্দেশ করবে । এক্ষেত্রে state হবে দুইটি - হয় আমি সংখ্যাটি নিব, না হয় নিবো না ।  প্রথম dimension এর জন্য 0 দ্বারা element টা নেইনি বুঝাব আর 1 দ্বারা element টা নিয়েছি বুঝাব । যেহেতু আমাদের কোন element এর মান সর্বোচ্চ 105 হতে পারে , তাই আমরা অপর dimension টি এমন size এর নিবো । এখন আমরা দ্বিতীয় dimension এর উপর লুপ চালাবো । প্রতিবার dp[i][0] = max(dp[i-1][0], dp[i-1][1]) হবে , কারণ আমরা যদি i-1 মানধারী element টি নেই এবং না নেই , এই উভয় ক্ষেত্রেই আমরা  i মানধারী element টি নিতে পারবো । আবার dp[i][1] = dp[i-1][0] + i*mp[i] , অর্থাৎ আমি যদি  i মানধারী element টি নিই তবে  i-1 মানধারী element টি নিতে পারবো না এবং  i মানধারী সকল element ই আমি নিতে পারবো । এভাবে সর্বোচ্চ element টি যদি x হয়, তবে max(dp[x][0], dp[x][1]) ই হবে answer . [My solution link](https://codeforces.com/contest/456/submission/57162455)

O. Decimal Digit

    এই প্রব্লেমে দুইটি সংখ্যা a ও b দেওয়া আছে । b!a!এর মানের last digit টি প্রিন্ট করতে হবে । এখানে a≤b . আমরা যদি b! কে a! দ্বারা ভাগ করি , তবে b! এর 1 থেকে a পর্যন্ত গুণনীয়কগুলো কাটা যাবে । এখন প্রথমে ans=1 রাখব এবং a+1 থেকে b পর্যন্ত সংখ্যা দিয়ে একে গুণ করব । প্রতি ধাপে গুণফলকে 10 দিয়ে ভাগ করে ভাগশেষ ans এ রাখব । লক্ষ করলে দেখব ,maximum 10টি ক্রমিক সংখ্যা check করলেই আমরা 10 এর কোন কোন multiple পেয়ে যাব । ফলে last digit 0 হয়ে যাবে এবং একবার 0 হয়ে গেলে পরে যা দিয়েই গুণ করা হোক না কেন 0 ই থাকবে ।  [My solution link](https://codeforces.com/contest/869/submission/57199576)

Q. Army

    প্রথমে আমরা কোন সংখ্যাটি কতবার আছে তা count করার জন্য একটি map use করবো । কোন সংখ্যা একাধিক বার থাকলে অতিরিক্ত বার গুলোর জন্য brute force approch এ check করবো যে পরবর্তী কোন minimum সংখ্যাটি array তে নেই । এই দুটি সংখ্যার বিয়োগফলকে ans এর সাথে যোগ করে update করে এগিয়ে যাব । [My solution link](http://codeforces.com/problemset/submission/546/57484232)
Tags bengali, #tutorial, nstu, cste

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Sukarna_Paul 2019-07-22 08:06:01 840 (published)
en2 English Sukarna_Paul 2019-07-22 07:34:49 4884
en1 English Sukarna_Paul 2019-07-15 13:32:52 5550 Initial revision (saved to drafts)